【Atcoder解法検討】ABC130 A~D Python

A - Rounding

問題ページ : A - Rounding

考察

標準入力、if文による条件分岐、出力でとおります。

コード

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

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

B - Bounding

問題ページ : B - Bounding

考察

　一見するとわかりづらい問題ですが、ボールが跳ねる座標は漸化式から順次求めることができます。その跳ねる座標がX以下ならカウントしていくだけです。

コード

N, X = map(int, input().split())
L = list(map(int, input().split()))

pos = 0     # ボールが跳ねる座標
ans = 1     # 座標X以下でボールが跳ねる回数

# ボールが跳ねる座標を順次求め、X以下ならカウントする
for i in range(N):
    pos += L[i]
    if pos <= X:
        ans += 1

print(ans)

C - Rectangle Cutting

問題ページ : C - Rectangle Cutting

考察

　数学または算数の問題（長方形 二等分でググる）。対角線の交点を通る直線で必ず二等分できます。よって面積は長方形面積の半分。
　また$(x,y)$が対角線の交点と一致する場合は無数の直線で二等分可能ですが、それ以外の場合は単数となります（二点を通る直線は一意に決定されます）。

コード

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

# 面積は必ず長方形の半分
S = W * H / 2

# (x,y)が対角線の交点にあれば複数、その他は単数
if x * 2 == W and y * 2 == H:
    num = 1
else:
    num = 0

print(S, num)

D - Enough Array

問題ページ : D - Enough Array

考察

　まず連続する部分列の和を計算する必要があるので累積和の適用が考えられます。ただし累積和を使用しても起点と終点の両方を探索すると$O(N^2)$となってTLEとなります。
　このような場合、起点か終点どちらかを固定して考えるとうまくいく場合があります。起点を固定して考えると、累積和に対する二分法で部分列の和がKを超える個数を数えることができます。この時計算量は$O(N
\log N)$となります。

コード

from bisect import bisect_left

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

# 累積和
S = [0] * (N+1)
for i in range(N):
    S[i + 1] = S[i] + A[i]

# 部分列の起点をふって各起点に対し累積和への二分法で和がK以上となる個数を数える
ans = 0
for l in range(N):
    pos = bisect_left(S,K+S[l])
    ans += N - pos + 1

print(ans)

E - Common Subsequence

問題ページ : E - Common Subsequence

F - Minimum Bounding Box

問題ページ : F - Minimum Bounding Box

青色diff以上は後日挑戦