u++の備忘録

AtCoder Beginner Contest 124をPythonで解く

予定があったので、リアルタイムでは参加できませんでした。

atcoder.jp

A - Buttons(100点)

  • AとBを1回ずつ取る場合は、A==Bのときのみ
  • それ以外は同じのを連続で取る
A, B = list(map(int, input().split()))

if (A == B):
    print(A + B)
else:
    print(max(A, B) * 2 - 1)

B - Great Ocean View(200点)

  • それぞれの山に対して、自分よりも海に近い山の集合での最大値を考える(最大値が自分自身であれば海が見える)
N = int(input())
H = list(map(int, input().split()))

cnt = 0
for i in range(len(H)):
    if (max(H[0:i+1]) == H[i]):
        cnt += 1

print(cnt)

C - Coloring Colorfully(300点)

  • 「0101010....」か「1010101....」に揃えることになる
  • どちらに揃えるのが良いか比較する
S = input()
N = len(S)
even = S[0::2]
odd = S[1::2]
ptn0 = N - (even.count('0') + odd.count('1'))
ptn1 = N - (even.count('1') + odd.count('0'))
print(min(ptn0, ptn1))

D - Handstand(400点)

  • 以前に解いたABC032C「列」で書いた「尺取り法」のコードを流用した
  • 尺取り法はこの記事などで勉強していた
  • 具体的な処理はコード内のコメント参照
N, K = list(map(int, input().split()))
S = input()

S = S + 'E'   # 終端処理
ans = -1    # 答えの初期値(十分に小さい値)

# 立った人の連続の数
if (S[0] == '0'):
    stand = 1
else:
    stand = 0

L = 0
R = 0

# 尺取り法
while (R < N):
    # 右端を進めることが可能(立った人の連続の数がK以下)なら、右端を進める
    if (stand <= K):
        # 立った人の連続の数が増えるなら1足す
        if (S[R] == '1' and S[R + 1] == '0'):
            stand += 1
        # 答えの更新
        ans = max(ans, R - L + 1)
        R += 1
    # 進められない場合、左端と右端が同じなら両者を進める
    # 左端が右端を追い越さないための処理
    elif (L == R):
        L += 1
        R += 1
    # それ以外は左端のみを進める
    else:
        # 立った人の連続の数が減るなら1減らす
        if (S[L] == '0' and S[L + 1] == '1'):
            stand -= 1
        L += 1
        # 左端のみを進めた場合は答えを更新し得ない

print(ans)