AtCoder Beginner Contest 124 C,D問題メモ

AtCoder Beginner Contest 124

AtCoder Beginner Contest 124 解説配信 - YouTube

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())

            

        
      