PythonでABC130

こんにちは、まっちです。

今回は、PythonでABC130に参加した記事です。
ABC126に続き、2回目の参加となります。

atcoder.jp

最終結果

A,B,C問題の3完で、44:16でした。（B回答ミスのペナルティ含む）

私の回答

備忘と戒めを込めて、クソコードを記載します。

A - Rounding

X, Aを比較し、XがA未満なら0を、XがA以上なら10を出力する。
単純に条件分岐させます。

X, A = map(int, input().split())

if X < A:
	print(0)
else:
	print(10)
 

B - Bounding

要素数Nの数列を順に足し込み、X以下となる回数を求める。
for文でリストの要素を1つずつ足し、毎回Xと比較します。

N, X = map(int, input().split())
S = list(map(int, input().split()))
l = len(S)

ans = 1
num = 0

for i in range(l):
	num += S[i]
	if num <= X:
		ans += 1

print(ans)
 

1度目は、リストの総和がX以下となるケースをケアできておらず、回答ミスとなりました。

C - Rectangle Cutting

xy座標上の四角領域を、座標(x,y)を通る直線で二分する。
そのうち、小さい方の領域面積の最大値とそれを実現する直線の数（1本or複数）を判定する。

回答の方針は、以下としました。

• 領域内の座標(x,y)を通る直線で二分する場合、最大値は全体面積の半分となる。
• 座標(x,y)が領域の中心の場合、直線は複数存在する。

W, H, x, y = map(int, input().split())

S = "{0:.6f}".format(float(W*H/2))

if x == W/2 and y == H/2:
	print(S, 1)
else:
	print(S, 0)
 

D - Enough Array

要素数Nの数列Aから、任意の長さの連続部分列を取り出す。
その和がK以下となる部分列の数を求める。

回答の方針は、以下としました。

• ウィンドウWを設定し、数列Aの中を動かしていく。
• Nまで動かしたら、Wの幅を広げ上記の処理を再度行う。

N, K = map(int, input().split())
A = list(map(int, input().split()))

ans = 0

for W in range(1,N+1):
	for i in range(N+1-W):
		S = sum(A[i:i+W])
		if S >= K:
			ans += 1

print(ans)
 

自信はあったのですが、テストケース14からTLEとなってしまいました。
問題文の記述をケアしてあげないといけなかったのかもしれません。

出力が 32bit整数型に収まらない場合があることに注意してください。

※2019/6/17追記

本問は、尺取り法という解法が有効だったみたいです。
私の解法はいわゆる全数探索だったため、の計算量となっていました。
尺取り法では、の計算量に抑えることができます。

qiita.com

以下のコードで正答できました。

N, K = map(int, input().split())
A = list(map(int, input().split()))

ans = 0
S = 0
j = 0

for i in range(N):
	while S < K:
		if j == N:
			break
		S += A[j]
		j += 1
	if S >= K:
		ans += N - j + 1
		S -= A[i]

print(ans)
 

総評

2回目にしては、割と解けたのではないかという印象でした。
今後の課題としては、以下でしょうか。

• 基本構文を覚え、A,B問題の回答タイムを上げる。
• A,B問題での回答ミスをなくす。
• C問題も運ではなく、実力で回答できるようにする。
• D問題では正答だけなく、処理ウィンドウに収まるよう、コードを工夫する。

当面はD問題まで解けるよう、過去問に触れていきます。

それでは。