ブログで書いてほしい内容受付中!! 詳しくはこちら

AtCoder Beginner Contest 130 のDまで解けたので記録【Python3】

きょうは ABC130 がありました。(昨日のコンテストは面倒だったので不参加でした)

サトゥー

ギリギリ緑になったよ

A, B, C, D を久々に全て時間内に解ききることができたので、その記録を書いていきます。

ABC 130 を D まで Python で解いたよ ・D では二分探索というアルゴリズムを利用したよ ・ついに緑コーダーになったよ

ABC130 A – Rounding

\(X, A\) は \(0\) 以上 \(9\) 以下の整数です。
\(X\) が \(A\) 未満の時 \(0\)、\(A\) 以上の時 \(10\) を出力してください。

https://atcoder.jp/contests/abc130/tasks/abc130_a

言われたとおりにコードを書けば OK ですかね。

回答案

Python3 で 23 ms で AC でした。

X, A = map(int, input().split())
if X < A:
	print(0)
else:
	print(10)

ABC130 B – Bounding

数直線上を \(N + 1\) 回跳ねるボールがあり、\(1\) 回目は 座標 \(D_1 = 0\) , \(i\) 回目は 座標 \(D_i = D_{i − 1} + L_{i − 1} (2 \leq i \leq N + 1) \) で跳ねます。
数直線の座標が \(X\) 以下の領域でボールが跳ねる回数は何回でしょうか。

https://atcoder.jp/contests/abc130/tasks/abc130_b

入力で与えられるのが L 、つまり跳ねるごとに進む量(階差)になっているので、順番に和を取ると D が求まることになります。D が求まってしまえば、あとは X 以下の D の個数を求めて完了です。

自分の回答では、D[0] = 0 としています。

回答案

Python3 で 17 ms で AC でした。

N, X = map(int, input().split())
*L, = map(int, input().split())
D = [0] * (N + 1)
for i in range(N):
	D[i + 1] = D[i] + L[i]
ans = len([j for j in D if j <= X])
print(ans)

ABC130 C – Rectangle Cutting

平面上に長方形があり、\(4\) つの頂点の座標は \( (0,0), (W, 0), (W, H), (0, H) \) です。 この長方形の内部または周上の点 \( (x, y) \) が与えられます。\( (x, y) \) を通る直線で長方形を \(2\) つの部分に分割するとき、 面積の大きくない方の面積の最大値を求めてください。また、その最大値を達成する分割の方法が複数あるかも判定してください。

https://atcoder.jp/contests/abc130/tasks/abc130_c

数学的な考察が落ち着いてできれば特に難しさは無い問題かなーという感じです。

大きくない方の面積の最大値としてありえる最大のものは長方形の面積の半分ですが、これは長方形の中心を通る直線でカットすれば常に達成できます。

長方形, ABC130

画像のようにカットしたとき、出来上がる2つの台形は対称性から合同であることが言えますね。

このような直線が複数通り引けるのは \( (x, y) = (\frac{W}{2}, \frac{H}{2}) \) のときだけですね。ある1点を通る直線というのはほぼ無限に考えられますが、異なる2点を通る直線となると1通りしか存在しないからです。

以上のような考察ができれば、次のような回答が得られると思います。

回答案

Python3 で 17 ms で AC でした。

W, H, x, y = map(int, input().split())
if x == W / 2 and y == H / 2:
	print((W * H) / 2, 1)
else:
	print((W * H) / 2, 0)

ABC130 D – Enough Array

長さ \(N\) の正整数列 \(A = a_1, a_2, …, a_N \) と整数 \(K\) が与えられます。\(A\) の連続する部分列であって、以下の条件を満たすようなものは何個あるでしょうか。

(条件) 連続部分列に含まれる全ての要素の値の和は、\(K\) 以上である。

ただし、ある二つの連続部分列が列として同じでも、取り出された位置が異なるならそれらは別々に数えるものとします。
出力が 32bit 整数型に収まらない場合があることに注意してください。

https://atcoder.jp/contests/abc130/tasks/abc130_d

まず問題を見て一番に考えたのは、左端 l と右端 r を動かしながら区間の和を確かめていくようなイメージ。ただ、こうすると \(O(N^2)\) になってしまって TLE になってしまいます。

この TLE を解消するのに今回は手こずりました。

発想としては、次のような流れです。

  • 区間の和は累積和から求められるので累積和でやってみる
  • 正整数列の累積和ってソートされているから、二分探索で右端決めればよいのでは?

二分探索モジュール: bisect

ということで、二分探索を利用するために二分探索モジュール bisect を利用します。実例を見たほうが理解が早いと思うのでこちらを。

from bisect import bisect_left, bisect_right

nums = [1, 2, 3, 5, 6, 7]

# ソート済みのリストに新たな値を入れようとしたときに場所を返してくれる
print(bisect_left(nums, 4))
>>> 3
print(bisect_left(nums, 6))
>>> 4

print(bisect_right(nums, 4))
>>> 3
print(bisect_right(nums, 6))
>>> 5

二分探索は頭いい人が辞書を引くときにやったりするアレです。探すべき対象が半分ずつになっていくので、計算量としては \(O(\log{N})\) になっています。

ソート済みの配列に対して有効であることが多いので、こういうときに武器として思いつけると good ですね。

参考 bisect --- 配列二分法アルゴリズムPython 3.7.3 ドキュメント

回答案

Python3 で 138 ms で AC でした。

from bisect import bisect_left

N, K = map(int, input().split())
*a, = map(int, input().split())
sum_a = [0] * N
sum_a[0] = a[0]
for i in range(N - 1):
	sum_a[i + 1] = sum_a[i] + a[i + 1]

ans = N - bisect_left(sum_a, K)
for l in range(1, N):
	ans += N - bisect_left(sum_a, K + sum_a[l - 1])

print(ans)

正整数列なので、r は条件を満たす最小のものが見つかればそれ以降は全て条件を満たします。なので、N - bisect_left(sum_a, K + sum_a[l - 1]) を足し合わせることでうまくいくことが分かります。

サトゥー

E 以降にも時間内にチャレンジできるだけの実力をつけたいです

1 COMMENT

コメントを残す

メールアドレスが公開されることはありません。

日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)