概要

既に埋まっている座席は動かせないまま、最終状態で「連続する \(3\) 席がすべて \(1\)」にならないようにしつつ、空席に追加で座らせられる人数の最大値を求めます。

考察

この制約「\(111\) を作ってはいけない」は、ある席を \(1\) にするかどうかが 直前 2 席の状態に依存することを意味します。
つまり、座席 \(i\) を \(1\) にしてよいのは「最終状態で \((i-2,i-1,i)\) が \(111\) にならないとき」だけです。

• 素朴に「空いているところをできるだけ埋める」ような貪欲は、先の強制配置（もともと \(1\) の席）との兼ね合いで失敗し得ます。
  例えば \(S = [0,0,1]\) のとき、左から「埋められるだけ埋める」と \([1,1,1]\) を作ってしまい不可能です。
  「今の選択が次（次々）の選択可能性を変える」ので、局所判断だけでは最適が保証できません。
• 一方で、この問題の制約は「最後の 2 席の状態」さえ分かれば、次の席をどうするかの可否が決まります。
  そこで 状態数が小さい DP（動的計画法）が有効です。

アルゴリズム

最終状態を \(T_1,\dots,T_N\) とします（\(T_i\in\{0,1\}\)）。
ただし、もともと埋まっている席は必ず \(1\) にする必要があるので、 - \(S_i=1\) のとき \(T_i=1\) は強制 - \(S_i=0\) のとき \(T_i\in\{0,1\}\) を選べる（\(1\) にしたら追加人数 \(+1\)）

DP の状態

左から順に決めていき、直前 2 席の値だけを状態として持ちます。

• \(dp[x][y]\)：今までに処理した席のうち最後の 2 席が \((x,y)\)（\(x,y\in\{0,1\}\)）であるような最終状態を作るとき、追加で座らせた人数の最大値

ここで「最後の 2 席」とは、例えば席 \(i\) まで決めた段階なら \((T_{i-1},T_i)\) を表します。

初期状態はまだ何も決めていないので、便宜上「席 \(-2,-1\) は \(0\)」とみなして - \(dp[0][0]=0\)（他は到達不能）

遷移

席 \(i\)（0-index で code の \(i\)）で選べる \(z=T_i\) は - \(S_i=1\) なら \(z=1\) のみ - \(S_i=0\) なら \(z\in\{0,1\}\)

ただし制約より - \((x,y,z)=(1,1,1)\) は禁止（連続 3 席 \(111\) になる）

許されるなら次状態は \((y,z)\) へ遷移します。追加人数は - \(S_i=0\) かつ \(z=1\) のときだけ \(+1\)（空席に新たに座らせた分）

これを全席に対して行い、最後に \(\max_{x,y} dp[x][y]\) が答えです。

計算量

• 時間計算量: \(O(N)\)
  （各席で状態 \(4\) 通り × 選択肢最大 \(2\) 通りの定数遷移）
• 空間計算量: \(O(1)\)
  （\(2\times2\) の DP を次配列に更新するだけ）

実装のポイント

• 到達不能状態を非常に小さい値（コードでは NEG = -10**18）で初期化し、最大化 DP を安全に書きます。

• 先頭の境界処理を簡単にするために「直前 2 席は最初 \((0,0)\)」というパディングを置く（dp[0][0]=0）のがコツです。

• \(S_i=1\) の席は必ず \(z=1\) に固定し、追加人数にカウントしない（もともと座っている人は増えていないため）。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    S = list(map(int, input().split()))

    NEG = -10**18
    dp = [[NEG, NEG], [NEG, NEG]]
    dp[0][0] = 0  # padding zeros for positions -2, -1

    for i in range(N):
        ndp = [[NEG, NEG], [NEG, NEG]]
        if S[i] == 1:
            choices = (1,)
        else:
            choices = (0, 1)

        for x in (0, 1):
            for y in (0, 1):
                cur = dp[x][y]
                if cur == NEG:
                    continue
                for z in choices:
                    if x == 1 and y == 1 and z == 1:
                        continue
                    add = 1 if (z == 1 and S[i] == 0) else 0
                    if cur + add > ndp[y][z]:
                        ndp[y][z] = cur + add
        dp = ndp

    ans = max(dp[0][0], dp[0][1], dp[1][0], dp[1][1])
    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。