JOI難易度６ 連鎖

問題原文

atcoder.jp

問題要旨

個のぷよが縦に並んでいる。ぷよは同色が４つ以上連なると消える。
あるぷよの塊が消えると、その上にいたぷよたちは下に移動し、そのあとも消える条件を満たすのであれば連鎖的に消える。
あるぷよの１つの色を変更することで連鎖を起こす時、最小で最終的に残るぷよをいくつにできるか？

• 
• 最初同じ色のぷよは４つ以上連なっていない。

解法

ある変更を及ぼして連鎖が起きる場合というのは、１１[２２３２２]１１のように消えた塊の隣の色が揃っていて、かつ４つ以上連続するときのみ。
よって、ある塊から左側のどこまで消えるかと、右側のどこまで消えるかを各塊について計算すればよい。
これだけなんだけど、実装は結構気をつける必要がある。

実装

まず、 １１[２２３２２２]１１のような色を変えたことによって消える最初の塊の長さが５以上になる場合に注意。
また、連鎖では左側と右側のマーカーを管理するが、連鎖で実際に消せる（塊の長さが４以上）状態にならないと、更新できないことに注意。

下の実装は割と冗長とはおもうけれど、わかりやすいのでとりあえずこれで。。。

from collections import Counter
N = int(input())
P = [int(input()) for _ in range(N)]

ans = N
for i in range(N - 4 + 1):
    delete = P[i: i + 4]
    color, cnt = Counter(delete).most_common(1)[0]

    # 1 2 1 1, 1 2 1 1, 1 1 2 1, 1 1 1 2 の形でないと色を変えても消せない
    if cnt != 3:
        continue

    # i, i + 1, i + 2, i + 3 は揃っている。色を変えたことで最初に消える塊の長さが５つ以上の場合に対応
    l, r = i - 1, i + 4
    while (l >= 0) and (P[l] == color):
        l -= 1
    while (r < N) and (P[r] == color):
        r += 1

    ans = min(ans, N - (r - l - 1))

    # 連鎖の処理
    while (l >= 0) and (r < N):
        cnt = 0
        if P[l] == P[r]:
            color = P[l]
            while (l >= 0) and (P[l] == color):
                l -= 1
                cnt += 1
            while (r < N) and (P[r] == color):
                r += 1
                cnt += 1

        if cnt < 4:
            break
        else:
            # ４つ以上連鎖するときでないと更新は起こらない！！！
            ans = min(ans, N - (r - l - 1))

print(ans)

感想

連鎖時に動く左と右のマーカーは、未確定状態のマーカーを示す変数を別に持った方がよかったかも。。。
見事にハマってしまった。