概要

一列に並んだ \(N\) 個の座席に、連続する3席がすべて埋まらないという制約のもとで、空席にできるだけ多くの人を新たに座らせる問題です。動的計画法（DP）を用いて最大人数を求めます。

考察

重要な気づき

この問題のポイントは「連続する3つの座席がすべて \(1\) になってはいけない」という制約です。ある座席 \(i\) に人を座らせるかどうかを決めるとき、その判断は直前の2つの座席の状態にのみ依存します。

具体的には、座席 \(i-2, i-1, i\) がすべて \(1\) にならなければよいので、座席 \(i\) を \(1\) にできるかどうかは座席 \(i-2\) と \(i-1\) の状態だけで決まります。

素朴なアプローチの問題点

空席を全列挙して全パターンを試す方法（\(2^{(\text{空席数})}\) 通り）は、\(N\) が最大 \(2 \times 10^5\) なので到底間に合いません。

解決方針

直前2席の状態のみが関係するため、状態数が非常に少ないDPで解けます。直前2席の状態は \((T_{i-2}, T_{i-1})\) の組で表現でき、各値は \(0\) または \(1\) なので、状態数はたった \(4\) つ（\((0,0), (0,1), (1,0), (1,1)\)）です。

アルゴリズム

1. DP の定義: \(dp[(a, b)]\) を「現在までの座席を処理し終えた時点で、直前2席の状態が \((a, b)\) であるときの、新たに案内した人数の最大値」とします。

2. 初期状態: 座席を処理する前は仮想的な状態 \((0, 0)\) とし、\(dp[(0, 0)] = 0\) で初期化します。

3. 遷移: 座席 \(i\) を処理するとき、

   • \(S_i = 1\)（すでに人がいる）場合：\(T_i = 1\) のみ選択可能。
   • \(S_i = 0\)（空席）の場合：\(T_i = 0\)（空席のまま）または \(T_i = 1\)（新たに案内）の2択。

各状態 \((a, b)\) と選択 \(t = T_i\) について、\(a = 1\) かつ \(b = 1\) かつ \(t = 1\) の場合は制約違反なのでスキップします。違反しなければ、新しい状態 \((b, t)\) に遷移し、追加人数 \(t - S_i\)（\(S_i = 0\) で \(t = 1\) のとき \(1\)、それ以外は \(0\)）を加えます。

1. 答え: 全座席を処理した後の \(dp\) の値の最大値が答えです。

具体例

\(N = 5, S = [0, 1, 0, 0, 1]\) の場合を考えます。

• 座席1: 空席なので \(0\) か \(1\) を選べる → \(1\) にする
• 座席2: すでに \(1\) → そのまま \(1\)
• 座席3: 空席だが、座席1,2 が \((1,1)\) なので \(1\) にできない → \(0\)
• 座席4: 空席、直前が \((1,0)\) なので \(1\) にできる → \(1\)
• 座席5: すでに \(1\)、直前が \((0,1)\) なので OK → \(1\)

結果: \(T = [1, 1, 0, 1, 1]\)、新たに案内した人数は \(2\) 人。

計算量

• 時間計算量: \(O(N)\) — 各座席で状態数は最大 \(4\)、選択肢は最大 \(2\) なので、1ステップあたり \(O(1)\)。
• 空間計算量: \(O(1)\) — DP テーブルのサイズは常に最大 \(4\) エントリ。（入力の格納に \(O(N)\)）

実装のポイント

• DP の状態を辞書 (a, b) -> 最大追加人数 で管理することで、状態数が少ないことを活かしてシンプルに実装できます。

• 仮想的な初期状態 \((0, 0)\) を導入することで、配列の先頭の処理を特別扱いせずに済みます。

• \(S_i = 1\) のとき \(T_i = 0\) にはできない（お客さんを退席させられない）点を忘れないようにしましょう。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    S = [int(input_data[i + 1]) for i in range(N)]
    
    # dp[i][last2][last1] = max number of new people added considering seats 0..i
    # last2, last1 are the states of seat i-1 and seat i respectively
    # We want to maximize the number of 1s we add (T[i] - S[i] for each i)
    
    # States: (prev2, prev1) where prev2 = T[i-1], prev1 = T[i]
    # Transition: for seat i+1, new state is (prev1, T[i+1])
    # Constraint: not (prev2 == 1 and prev1 == 1 and T[i+1] == 1)
    # Also: if S[i+1] == 1, then T[i+1] must be 1
    
    # dp stored as dict (prev2, prev1) -> max added people
    # Initialize with a virtual state before seat 0
    
    NEG_INF = -1
    
    # Before processing any seat, we have no previous seats
    # We'll use prev2=-1, prev1=-1 to indicate no previous seats
    # Better: process seat by seat
    
    # dp[(a, b)] = max added, where a = T[i-2], b = T[i-1] after processing seats 0..i-1
    # For i=0, before processing, state is (0, 0) as virtual seats before the array
    
    dp = {}
    dp[(0, 0)] = 0  # virtual previous states
    
    for i in range(N):
        new_dp = {}
        s = S[i]
        
        if s == 1:
            candidates = [1]  # must remain 1
        else:
            candidates = [0, 1]  # can choose to seat someone or not
        
        for (a, b), val in dp.items():
            for t in candidates:
                if a == 1 and b == 1 and t == 1:
                    continue  # violates constraint
                added = val + (t - s)  # t - s is 1 if we added someone, 0 otherwise (t >= s always)
                key = (b, t)
                if key not in new_dp or new_dp[key] < added:
                    new_dp[key] = added
        
        dp = new_dp
    
    print(max(dp.values()))

solve()

---

この解説は claude4.6opus-thinking によって生成されました。