Pythonでn人のプログラマーを隣り合わずに着席できるか判定するプログラムの書き方

この記事では、Pythonを使って「n人のプログラマーを、互いに隣り合わないように会場に着席させられるかどうか」を判定するアルゴリズムを解説します。これは配列の走査と貪欲法（グリーディ法）の基本的な考え方を学べる、定番の練習問題です。

問題の概要

ある数値 n は、会議（コンベンション）に参加しようとしているプログラマーの人数を表します。また、0と1からなるリスト convention が与えられます。

• 1 … その席にすでにプログラマーが座っている
• 0 … 空席である

ここで重要なルールは「2人のプログラマーを隣同士の席に座らせてはいけない」というものです。この条件下で、n人全員が着席できるかどうかを判定します。

例：

• 入力：n = 2, convention = [0, 0, 1, 0, 0, 0, 1]
• 出力：True

この例では、インデックス1と4の空席にそれぞれプログラマーを座らせることで、隣接を避けながら2人全員を着席させることができます。

解き方のアプローチ

この問題は貪欲法で解くことができます。リストを左から順に走査し、「今見ている席・左隣の席・右隣の席」がすべて空席（0）であれば、そこにプログラマーを座らせます。手順は以下の通りです。

1. i を 0 から conv のサイズ - 1 まで順に処理する。
2. 左隣のインデックス a を求める。i - 1 < 0 の場合は 0、それ以外は i - 1 とする（端の処理）。
3. 右隣のインデックス b を求める。i + 1 ≥ conv のサイズの場合はサイズ - 1、それ以外は i + 1 とする。
4. conv[i] == 0 かつ conv[a] == 0 かつ conv[b] == 0 であれば、conv[i] = 1 としてプログラマーを着席させ、n を 1 減らす。
5. すべての席を確認した後、n ≤ 0 なら True、そうでなければ False を返す。

実装例（Pythonコード）

class Solution:
    def solve(self, n, conv):
        for i in range(len(conv)):
            a = 0 if i - 1 < 0 else i - 1
            b = len(conv) - 1 if i + 1 >= len(conv) else i + 1
            if conv[i] == 0 and conv[a] == 0 and conv[b] == 0:
                conv[i] = 1
                n -= 1
        return n <= 0

ob = Solution()
n = 2
convention = [0, 0, 1, 0, 0, 0, 1]
print(ob.solve(n, convention))

入力

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

出力

True

コードのポイント

• 境界処理： リストの両端では隣の席が存在しないため、a や b を自分自身のインデックスに置き換えることで、範囲外参照を防いでいます。
• 貪欲な割り当て： 左から順に座れる場所へ即座に座らせることで、後続の席の選択肢を最大限残す戦略です。この問題設定では貪欲法でも最適解が得られます。
• 計算量： リストを一度だけ走査するため、時間計算量は O(m)（m は席の数）、追加のメモリは不要で空間計算量は O(1) です。

なお、より汎用的な実装としては、両端に番兵（ダミーの0）を追加して走査する方法や、連続する空席の長さから着席可能人数を数式で求める方法もあります。状況に応じて使い分けるとよいでしょう。