概要

一列に並んだ座席に新たなお客さんを案内する際、連続する3つの座席に人が座る状態を作らないようにしながら、最大何人案内できるかを求める問題。

考察

この問題では、初期状態で連続する3つの座席がすべて埋まっていることはありませんが、新たに案内することでそのような状態を作らないように注意しながら、できるだけ多くの人を座らせる必要があります。

単純に左から貪欲に「空席があれば座らせる」では最適になりません。例えば、000 という並びがあった場合、101 のように間を空けることで後の配置に影響を与えないようにするのが良いです。

このような「これまでの状態によってこれからの選択が変わる」という性質を持つ問題に対しては、動的計画法（DP）が有効です。

DPの状態としては、「今見ている座席の位置」と「直前の2つの座席の状態」を持ちます。これは、次に案内する人が連続3人目にならないようにするために、直前2つを見れば十分だからです。

たとえば、直前の2つがともに1であれば、次の座席には誰も座らせることはできません。そうでない場合は、空席であれば新たに1人座らせることができます。

このようにして遷移を管理することで、条件を満たしながら最大の人数を導き出すことができます。

アルゴリズム

動的計画法（DP）を用いて以下のように状態を定義します：

• dp[(prev2, prev1)] = max_count: 直前2つの座席の状態が prev2, prev1 であるような状態における、それまでの最大の追加人数

遷移は以下のように行います： - 現在の座席 i が既に埋まっている（S[i] == 1）場合： - 必ず T[i] = 1 とするが、直前2つがともに1だった場合は不許可 → それ以外の場合に遷移 - 現在の座席が空席（S[i] == 0）の場合： - T[i] = 0 とする遷移（誰も座らせない） - T[i] = 1 とする遷移（ただし、直前2つがともに1でない場合のみ）

これを最初から最後まで順に行い、最終的な dp の値の最大が答えとなります。

計算量

• 時間計算量: \(O(N)\)
  各座席に対して、直前の状態の組み合わせは高々4通り（\((0,0),(0,1),(1,0),(1,1)\)）であり、定数時間で遷移が可能です。
• 空間計算量: \(O(1)\)
  DPテーブルの状態数も定数個なので、空間も定数オーダーです。

実装のポイント

• DPのキーとして (prev2, prev1) のペアを使用し、遷移時に条件（連続3つが1にならない）をチェックする。

• S[i] == 1 の場合は必ず遷移するが、制約を満たす場合のみ遷移させる。

• 最終的な答えは dp.values() の最大値として得られる。

  ソースコード

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    S = list(map(int, data[1:]))

    # dp[i][a][b][c]: i番目まで見て、直前の3つの状態がa,b,cのときの最大追加人数
    # ただし、連続3つがすべて1になることは禁止なので、そのような状態は無効とする
    # 状態空間が大きいので貪欲法的にシミュレーションする

    # 貪欲に配置する方法を考える。
    # 各空席に対して、「そこに座らせると連続3つが埋まるか？」を判定して配置を決める
    # しかし、単純に左から貪欲では最適にならない。
    # 例えば 000 -> 101 と 110 や 011 などを見比べる必要がある。

    # そこで、動的計画法で考えることにする。
    # dp[i][prev2][prev1] := i番目まで処理して、i-2番目がprev2、i-1番目がprev1のときの最大追加人数
    # ただし、連続する3つが111にならないように遷移する

    # 実装上、i=0,1,2,...,N-1 として、i番目の座席の最終的な状態(T[i])を決める。
    # S[i] == 1 なら T[i] = 1 固定
    # S[i] == 0 なら T[i] = 0 or 1 (ただし条件を守る)

    # 状態数を減らすため、i番目まで見たときに最後の2つの値(prev2, prev1)だけ持つ
    from collections import defaultdict
    dp = dict()
    dp[(0, 0)] = 0  # 最初は(0,0)としておく（便宜上）

    for i in range(N):
        new_dp = defaultdict(lambda: -1)
        for (p2, p1), cnt in dp.items():
            if cnt == -1:
                continue
            # S[i] == 1 なら必ず1
            if S[i] == 1:
                # 次の状態は(p1, 1)、ただし(p2,p1,1)が111にならないようにチェック
                if not (p2 == 1 and p1 == 1):
                    key = (p1, 1)
                    new_dp[key] = max(new_dp[key], cnt)
            else:
                # S[i] == 0 なら0か1を選べる
                # 選択1: 0にする
                key = (p1, 0)
                new_dp[key] = max(new_dp[key], cnt)
                
                # 選択2: 1にする（ただし3連続にならないように）
                if not (p2 == 1 and p1 == 1):
                    key = (p1, 1)
                    new_dp[key] = max(new_dp[key], cnt + 1)
        dp = new_dp

    print(max(dp.values()))

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。