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

programming_algorithm/contest_history/atcoder/2019/0413_abc124.txt · 最終更新: 2019/04/13 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0