AtCoder Beginner Contest 124 C,D問題メモ
C - Coloring Colorfully
問題
- 左右一列に $N$ 枚のタイルが並ぶ
- 各タイルの色は長さ $N$ の文字列 $S$ によって与えられ、'0'なら黒、'1'なら白
- いくつかのタイルを塗り替えて、以下の条件を満たしたい
- どの隣り合う2枚のタイルも異なる色
- 塗り替える必要のある最小枚数を求めよ
- $1 \le N \le 10^5$
解法
最終的な状態は、'010101…' か '101010…' しかない。（長さは $N$ ）
これが初期状態と違えば塗り替える必要がある。一つずつカウントする。
2種類の最終状態を両方試し、小さい方が答え。
'0', '1'を整数化した上で t に前のタイルの色が入っているとして、t ^= 1 で0と1を反転できる。
def solve(init, s):
t = init
ret = 0
for c in s:
if c != t:
ret += 1
t ^= 1
return ret
s = input()
s = list(map(int, s))
print(min(solve(0, s), solve(1, s)))
D - Handstand
問題
- $N$ 個の'0'または'1'が並ぶ
- 最大 $K$ 回、以下の操作が行える
- 任意の区間 $[l, r]$ を選んで、その区間の'0'と'1'を反転させる
- 最終的に、'1' を最大何個並ばせることが出来るか求めよ
解法
こういう「'0'と'1'を区間で反転させることで要素を揃えていく」問題では、反転という操作は「異なる要素の境界を減らす」ことを意味すると考えると上手くいくことが多い。
111001011100010
~~~~~
111000100000010
↑ ↑ こことここの境界が消えてる
今回、操作は $K$ 回まで行え、左右端とも自由に決められるので、最大 $2K$ 個の境界を無くせる。
無くす境界をどのように選ぶのがよいかというと、'1'を連続させるので、
11111 | 000 | 1 | 0000 | 111
こういう風な、'1'から始まる'1'と'0'交互の連続する境界について無くせばよい。
よって、'1'と'0'の連続する要素毎にカウントして、（連長圧縮）
1110001000000100 ↓ 111 000 1 000000 1 00 ↓ [ 3, 3,1, 6,1, 2, 0] ←便宜上、左右端が'0'だった場合は'1'が0個と考えて0を追加しておく
連続する $2K+1$ 要素の和の中で、最大のものを求めればよいことになる。 ただし両端はもともと '1' だった箇所でなければいけないので、0,2,4,…番目から始まる区間のみ調べる。
K = 2
S = 111 000 1 000000 1 00 11111 00 1 0
[ 3, 3, 1, 6, 1, 2, 5, 2, 1, 1, 0 ]
~~~~~~~~~~~~~~ = 14
~~~~~~~~~~~~~~ = 15 ←答え
~~~~~~~~~~~~~~ = 11
~~~~~~~~~~~~~~ = 9
区間の和は、累積和または尺取法を用いれば高速に行える。
from itertools import accumulate
n, k = list(map(int, input().split()))
s = input()
def solve():
l = []
prev = '1'
cnt = 0
for c in s:
if prev == c:
cnt += 1
else:
l.append(cnt)
cnt = 1
prev = c
l.append(cnt)
if prev == '0':
l.append(0)
w = 2 * k + 1
if len(l) <= w:
return n
acc = [0] + list(accumulate(l))
ans = 0
for i in range(0, len(l) - w + 1, 2):
ans = max(ans, acc[i + w] - acc[i])
return ans
print(solve())
