C++で解く「貧しい豚（Poor Pigs）」問題 ― 毒入りのバケツを見つける最小の豚の数

ここに1000個のバケツがあるとしましょう。そのうち1つだけに毒が入っており、残りはすべて水が入っています。見た目はどれもまったく同じで、区別がつきません。毒を飲んだ豚は15分以内に死んでしまうため、1時間以内に毒の入ったバケツを特定するには、最低何頭の豚が必要でしょうか？

問題の一般化

まず、この問題を一般化してみましょう。条件は次のとおりです。

• n個のバケツがあり、そのうちちょうど1つに毒が入っている
• 毒を飲んだ豚は m 分以内に死ぬ
• p 分以内に毒のバケツを特定したい

このとき必要な豚の最小頭数を求めるのが目標です。例えば n = 1000、m = 15、p = 60 の場合、答えは 5 になります。

解法のポイント：「1頭の豚で複数回テストできる」

この問題を解く鍵は、1頭の豚が1回しか使えないわけではないという点にあります。テスト可能な時間が死亡までの時間の何倍かに応じて、豚は「何ラウンド目で死んだか」「最後まで生き残ったか」といった複数の状態を取り得ます。

具体的には、1頭の豚が取り得る状態の数は次の式で表せます。

状態数 = minutesToTest / minutesToDie + 1

例えば 60分 ÷ 15分 + 1 = 5 状態です。この状態数を「底」、豚の頭数を「指数」とする累乗が、識別可能なバケツの組み合わせの総数になります。したがって、次を満たす最小の ret（豚の頭数）を求めればよいのです。

(minutesToTest / minutesToDie + 1)^ret ≥ バケツの数

アルゴリズムの手順

• ret := 0 で初期化する
• (minutesToTest / minutesToDie + 1)^ret < バケツの数 である間、ret を1ずつ増やし続ける
• ret を返す

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
      int ret = 0;
      while(pow((minutesToTest / minutesToDie + 1), ret) < buckets) ret++;
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.poorPigs(1000,15,60));
}

入力

1000
15
60

出力

5

なぜ答えは5なのか？

この例では、1頭あたりの状態数は 60 ÷ 15 + 1 = 5 です。豚の頭数ごとに識別できるバケツ数を計算すると、

• 4頭の場合：5^4 = 625 → 1000個は識別できない
• 5頭の場合：5^5 = 3125 → 1000個を十分にカバーできる

このため、必要な最小の豚の数は 5頭 となります。各バケツに一意の番号を5進法で割り当て、それぞれの桁に対応する豚がいつ死んだか（あるいは生き延びたか）を観察すれば、どのバケツに毒が入っていたかを正確に特定できます。