ABC124参加記 - 橋梁管理日誌

先日行われたAtCoder Beginner Contest 124に参加した。今回は、全てPython3で解いた。

A問題

問題ページ
解法は、愚直にシミュレーションをした。コードは以下の通り。

a, b = map(int, input().split())

ans = 0
for i in range(2):
	if a > b:
		ans = ans + a
		a = a - 1
	else:
		ans = ans + b
		b = b - 1

print(ans)

B問題

問題ページ
これは、西から順に見ていき、今まで見た中での高さの最大値を保持しておくことで各山について $O(1)$ で判定できる（制約が小さいので2重ループでも間に合うと思われる）。初期値を $H_1$ 以下にしておけば、一番西側も同様に処理できる。コードは以下の通り。

n = int(input())
h = list(map(int, input().split()))

ans = 0
maxi = -1

for i in range(n):
	if maxi <= h[i]:
		ans = ans + 1
	maxi = max(maxi, h[i])

print(ans)

C問題

問題ページ
色の種類が2種類で、隣り合った色が異ならなければならない。よって、最終状態は奇数番目が色0で偶数番目が色1、またはその逆しかありえない。そこで、奇数番目、偶数番目それぞれについて色1の個数を数えておくことで、色を変えなければならない個数を求めることができる。コードは以下の通り。

s = input()
s = list(map(int, s))
n = len(s)

cnt = [0] * 2
for i in range(n):
	m = i % 2
	if s[i] == 1:
		cnt[m] = cnt[m] + 1

ans = min((n // 2 + n % 2 - cnt[0]) + cnt[1], cnt[0] + (n // 2 - cnt[1]))
print(ans)

D問題

問題ページ
$1$ 回の操作での最適解は、0のみが連続する部分を選ぶパターンである。 $K$ 回の操作での最適解も、そのような部分を連続した $K$ 個選ぶのが最適である。実装方針は、まず、与えられたデータから、左から順に連続する同じ数字の個数の配列を作っておく。例えば、入力が110011110ならば、2, 2, 4, 1という具合にする。この配列の累積和の配列を作り、これを $S$ とすると、 $S_i - S_{i - 2K or i - 2K - 1}$ の最大値が答えとなる。 $i - 2K$ か $i - 2K - 1$ かは、 $i$ にあたるのが0か1かによる。よって、偶奇と先頭で場合分けをすれば良い。コードは以下の通りである。max(i - k * 2, 0)等は、配列外参照の防止や、配列長が $2K$ 未満のケースに対応するためである（ちょうど $K$ 回ではなく $K$ 回以下なのでこの書き方でおｋ）。

n, k = map(int, input().split())
s = input()
s = list(map(int, s))

v = []
cnt = 1
for i in range(n - 1):
	if s[i] == s[i + 1]:
		cnt = cnt + 1
	else:
		v.append(cnt)
		cnt = 1
v.append(cnt)
m = len(v)

sum = [0] * (m + 1)
for i in range(1, m + 1):
	sum[i] = sum[i - 1] + v[i - 1]

ans = 0
for i in range(m + 1):
	if s[0] == 0:
		if i % 2 == 0:
			ans = max(ans, sum[i] - sum[max(i - k * 2 - 1, 0)])
		else:
			ans = max(ans, sum[i] - sum[max(i - k * 2, 0)])
	else:
		if i % 2 == 0:
			ans = max(ans, sum[i] - sum[max(i - k * 2, 0)])
		else:
			ans = max(ans, sum[i] - sum[max(i - k * 2 - 1, 0)])

print(ans)

感想

pythonの記法に慣れてきた。後から+=と-=があることを知ったので、次回以降はこう書けると思う。