PythonでJOI難易度6を埋める #3

解説AC．

C - 連鎖

どこの色を変えるかを回調べて，それぞれで何連鎖するか計算します．

from collections import Counter

n = int(input())
p = [int(input()) for _ in range(n)]

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

    if cnt != 3: #同じ要素が3個存在しない→色を変えても消えない
        continue

    #一回目の操作で，最大何個消えるか
    left, right = i - 1, i + 4
    while left >= 0 and p[left] == color:
        left -= 1
    while right < n and p[right] == color:
        right += 1

    ans = min(ans, n - (right - left - 1)) #-1を忘れない

    #連鎖の処理
    while left >= 0 and right < n: #一連鎖ごとに調べる
        cnt = 0
        if p[left] == p[right]:
            color = p[left]
            while left >= 0 and p[left] == color: #左側がどこまで消えるかの確認
                left -= 1
                cnt += 1
            while right < n and p[right] == color: #右側がどこまで消えるかの確認
                right += 1
                cnt += 1

        if cnt < 4: #連鎖なし
            break
        else: #連鎖あり
            ans = min(ans, n - (right - left - 1))

print(ans)

参考にした記事