【Python】強盗たちは警備員に捕まらずに金庫を奪えるか？判定アルゴリズムの実装方法

問題の概要

N人の強盗がある金庫を襲おうとしているとします。警備員はG時間だけ現場を離れ、その後戻ってきます。各強盗には金庫内で作業するのに必要な時間がそれぞれ決まっており、同時に金庫に入れるのは最大2人までです。

このとき、「強盗たちが警備員に捕まらずに金庫を奪うことは可能か？」を判定するのがこの問題です。判定の際には、次のルールを考慮する必要があります。

• ある強盗が時刻tに金庫へ入り、同じ時刻tに別の強盗が出る場合、2人が同時に金庫内にいたことにはなりません。
• 警備員が時刻Gに金庫に入った瞬間に、強盗がちょうど時刻Gに出たとしても、警備員はその強盗に気づきません。

具体例

入力が N = 3、G = 5、time = [3, 5, 2] の場合、出力は True になります。次のようなスケジュールが成立するからです。

• 時刻 t=0 に強盗1が金庫に入り、t=3 に出る
• 時刻 t=0 に強盗2が金庫に入り、t=5 に出る
• 時刻 t=3 に強盗3が金庫に入り、t=5 に出る

解法のアプローチ

この問題は、部分和問題（Subset Sum）の考え方を応用した動的計画法（DP）で効率的に解けます。ポイントは「全体の作業時間を2つのグループに分け、それぞれの合計がG以下にできるか」を判定することです。同時に2人まで入れるため、実質的に2つのタイムスロットへ振り分ける問題と捉えられます。

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

1. 全強盗の所要時間の合計が 2×G を超える場合は、どう割り振っても警備員が戻る前に終わらないため False を返します。
2. 合計が G 以下であれば、1人ずつ順番に入れば十分なので True を返します。
3. それ以外の場合は、サイズ G+1 のブール配列 valid を作成し、初期値をすべて False、valid[0] のみ True にします。各強盗の所要時間 x について、i を G から 0 まで降順に走査し、i−x ≥ 0 かつ valid[i−x] が True なら valid[i] を True に更新します。これは「片方のグループの合計時間として i を達成できるか」を記録する処理です。
4. 最後に、合計時間から「valid[i] が True となる最大の i」を引いた値が G 以下であれば、残りの作業をもう一方のスロットに収められるため True を返します。そうでなければ False です。

Pythonでの実装例

以下のコードで実際の動作を確認できます。

def solve(N, G, time):
   if sum(time) > 2*G:
      return False
   elif sum(time) <= G:
      return True
   else:
      valid = [False]*(G+1)
      valid[0] = True
      for x in time:
         for i in range(G,-1,-1):
            if i-x >= 0 and valid[i-x]:
               valid[i] = True
      if sum(time) - max(i for i in range(len(valid)) if valid[i]) <= G:
         return True
      else:
         return False

N = 3
G = 5
time = [3,5,2]
print(solve(N, G, time))

入力

3,5,[3,5,2]

出力

True

計算量について

このアルゴリズムの時間計算量は O(N × G)、空間計算量は O(G) です。強盗の人数と警備員の不在時間に対して線形〜擬似多項式時間で判定できるため、実用的な範囲の入力であれば高速に動作します。