概要

\(N\) 個の座席の初期状態が与えられます。「連続する3つの座席すべてに人が座っている状態」にならないように空席に人を座らせるとき、新たに追加できる人数の最大値を求める問題です。

考察

空席に人を座らせるか（\(1\) にするか）、空席のままにするか（\(0\) にするか）を左から順に決めていくことを考えます。 このとき、「連続する3つの座席がすべて \(1\) になってはいけない」という条件があるため、ある座席に人を座らせることができるかどうかは、直近2つの座席の状態のみに依存します。

もし、すべての空席に対して座らせるかどうかの全探索を行うと、空席の数を \(K\) としたときに \(O(2^K)\) の時間がかかり、最悪の場合 \(O(2^N)\) となってTLE（実行時間制限超過）になります。 しかし、直近2つの座席の状態（\(00, 01, 10, 11\) の4通り）さえ覚えておけばよいことに着目すると、動的計画法（DP）を用いて効率的に解くことができます。

アルゴリズム

動的計画法（DP）を用います。次のようなDPテーブルを定義します。

\(DP[j][k] = \) 「2つ前の座席の状態が \(j\)、1つ前の座席の状態が \(k\) であるときの、新たに案内できた人数の最大値」 （\(j, k \in \{0, 1\}\)）

初期状態として、座席の左側に仮想的な空席が2つあると考え、\(DP[0][0] = 0\)、それ以外を \(-\infty\) とします。

各座席 \(i\) （初期状態は \(S_i\)）について、座席 \(i\) の最終的な状態 \(l \in \{0, 1\}\) をどうするかを考え、以下の条件を満たす遷移を行います。

1. 退席不可の条件: \(S_i = 1\) のとき、すでに人が座っているため \(l = 0\) にすることはできません。
2. 換気ルールの条件: \(j = 1\) かつ \(k = 1\) かつ \(l = 1\) となる場合、連続する3人が座ることになるため遷移できません。

これらの条件を満たす場合のみ、次の状態のDPテーブル \(ndp[k][l]\) を更新します。 このとき、もともと空席（\(S_i = 0\)）だったところに新たに人を座らせた（\(l = 1\)）場合は、案内した人数が \(1\) 人増えるため、遷移元の値に \(+1\) を加算します。

\[ndp[k][l] = \max(ndp[k][l], DP[j][k] + \text{add})\]

（ここで、\(\text{add}\) は \(S_i = 0\) かつ \(l = 1\) のとき \(1\)、それ以外のとき \(0\)）

これをすべての座席について順番に行い、最後にDPテーブルに残った値の最大値を求めれば、それが答えとなります。

計算量

• 時間計算量: \(O(N)\)
  • 各座席について \(j, k, l\) の組み合わせ（\(2 \times 2 \times 2 = 8\) 通り）の遷移を計算するだけなので、座席数 \(N\) に比例した時間で高速に処理できます。
• 空間計算量: \(O(1)\)
  • 常に直前1ステップ分のDPテーブル（\(2 \times 2\) の配列）のみを保持して使い回すため、メモリ使用量は定数となります。

実装のポイント

• あり得ない状態の排除: DPテーブルの初期値を -INF（十分に小さな値）にしておくことで、まだ到達していない状態からの誤った遷移をシンプルに防ぐことができます。

• 配列の更新: 現在のステップの dp と次のステップの ndp を別々の配列として用意し、1つの座席の計算が終わった後に dp = ndp と置き換えることで、計算中に状態が混ざるのを防いでいます。

  ソースコード

import sys

def main():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    S = [int(x) for x in data[1:]]

    INF = float('inf')
    dp = [[-INF] * 2 for _ in range(2)]
    dp[0][0] = 0

    for s in S:
        ndp = [[-INF] * 2 for _ in range(2)]
        for j in range(2):
            for k in range(2):
                if dp[j][k] == -INF:
                    continue
                for l in range(2):
                    if s == 1 and l == 0:
                        continue
                    if j == 1 and k == 1 and l == 1:
                        continue
                    
                    add = 1 if s == 0 and l == 1 else 0
                    if dp[j][k] + add > ndp[k][l]:
                        ndp[k][l] = dp[j][k] + add
        dp = ndp

    ans = max(max(row) for row in dp)
    print(ans)

if __name__ == '__main__':
    main()

この解説は gemini-3.1-pro-thinking によって生成されました。