AtCoder Beginner Contest 124

A - Buttons

a, b = [int(x) for x in input().split()]

c = max([a, b])

if c == a:
    d = max([a - 1, b])
else:
    d = max([a, b - 1])

result = c + d
print(result)

B - Great Ocean View

スケールがしょぼいので超素朴に解く。

計算量

n = int(input())
h = [int(a) for a in input().split()]

result = 0
for i in range(n):
    if all([h[j] <= h[i] for j in range(i)]):
        result += 1

print(result)

C - Coloring Colorfully

• タイルは左右一列に並ぶ
• タイルは 枚
• タイルの色は2種類
• どの隣り合う2枚のタイルも異なる色

という条件を満たすのは、黒と白が交互に並ぶ次の2パターンだけ。

• 0101010...
• 1010101...

したがって解法は

1. 与えられたタイルの並び と上記2パターンを比較し、色が異なるタイルの枚数 p, q をそれぞれ求める。
2. p と q の最小値を取る。

計算量

s = [int(x) for x in list(input())]

n = len(s)

p = [s[i] == i % 2 for i in range(n)]
q = [s[i] == (i - 1) % 2 for i in range(n)]

result = min([sum(p), sum(q)])
print(result)

D - Handstand

最善手では、常に 0 が連続している部分だけを反転させる。

1. 111 00 11 0 1111 000 のように、文字が連続している部分に分割する。
2. 「 1 の間にある 0 を反転させて繋ぐ」ことで、 1 を繋げられる最大の長さを計算。
   1. 文字が連続している各部分の長さを計算。
   2. 移動平均を取る。
   3. 最大値を取る。

import numpy as np

n, k = [int(a) for a in input().split()]
s = input()

def main():
    consecutive_ones = [len(x) for x in s.split("0") if x != '']
    consecutive_zeros = [len(x) for x in s.split("1") if x != '']

    if s[0] == "0":
        consecutive_ones.insert(0, 0)
    if s[-1] == "0":
        consecutive_ones.append(0)
    
    if len(consecutive_zeros) == 0:
        return n
    else:
        cumsum_ones = np.convolve(consecutive_ones, np.ones(k+1), mode='valid')
        cumsum_zeros = np.convolve(consecutive_zeros, np.ones(k), mode='valid')

        z = [x + y for x,y in zip(cumsum_ones, cumsum_zeros)]
        return int(max(z))

print(main())