【Python】隣り合わない条件で全員が座席に着席できるかを判定するアルゴリズム

n 人の人が座席を探している状況を考えます。座席の状態はビットのリストで表され、1 はすでに使用されている座席、0 は空いている座席を意味します。ただし、隣り合う座席に同時に着席することはできません。このとき、n 人全員が座席に見つけられるかどうかを判定するのが本記事のテーマです。

例えば、入力が n = 2、seats = [1, 0, 0, 0, 1, 0, 0] の場合、出力は True になります。インデックス 2 と 6 の空き座席に、互いに隣接しない形で着席できるからです。

解法のアプローチ

この問題は、連続する空き座席（0 の並び）ごとに、条件を満たして着席できる人数を数えることで解けます。長さ gap の連続した空き区間には、隣接しないように最大で (gap - 1) ÷ 2 の切り捨て値の人間が座れます。

具体的な手順は以下の通りです。

• seats の先頭に 0 を挿入し、末尾に [0, 1] を追加します。これにより、リストの両端にある空き区間も確実に処理できるようになります。
• 累積カウンタ res := 0、現在の空き区間の長さ gap := 0 で初期化します。
• seats の各要素 i について、次の処理を行います。
  • i が 0 の場合：gap を 1 増やします。
  • それ以外の場合（i が 1 のとき）で gap > 0 の場合：res に (gap - 1) // 2 を加算し、gap を 0 にリセットします。
• 最後に、res >= n であれば true を返し、そうでなければ false を返します。

実装例

理解を深めるために、以下の Python 実装を見てみましょう。

def solve(n, seats):
    seats = [0] + seats + [0, 1]
    res = 0
    gap = 0
    for i in seats:
        if i == 0:
            gap += 1
        elif gap > 0:
            res += (gap - 1) // 2
            gap = 0
    return res >= n

n = 2
seats = [1, 0, 0, 0, 1, 0, 0]
print(solve(n, seats))

入力

2, [1, 0, 0, 0, 1, 0, 0]

出力

True

コードのポイント

• 番兵（パディング）の活用： 先頭の 0 は「最初の座席が空いているケース」でも正しく数えられることを保証し、末尾の [0, 1] はループ終了後に残った空き区間を確実に集計するために追加しています。
• 効率性： 座席リストを一度だけ走査すればよいため、時間計算量は座席数 m に対して O(m) と非常に効率的です。