卵落としパズルとは？動的計画法で最小試行回数を求めるアルゴリズムを解説

「卵落としパズル」は、アルゴリズム学習において非常に有名な古典的な問題です。
n階建ての建物とm個の卵が与えられたとき、「卵を割らずに落とすことができる安全な階（臨界階）」を見つけるために必要な最小の落下試行回数を求める、というものです。

問題の前提条件

この問題を解くにあたって、以下の重要なポイントを押さえておく必要があります。

• ある階から卵を落として割れなかった場合、それより低い階から落としても割れることはありません。
• ある階から卵を落として割れた場合、それより高いすべての階から落とした場合にも必ず割れます。
• 割れた卵は廃棄しなければなりません。無事だった卵は再度使用できます。

つまり、卵の耐久性には明確な境界があり、その境界となる階を効率よく探索するのがこのパズルの目的です。

入力と出力

例として、卵が4個、建物の最大階数が10階の場合を考えてみます。

入力:
卵の数: 4
最大階数: 10

出力:
最小試行回数: 4

アルゴリズム（動的計画法）

この問題は動的計画法（DP）を用いて効率的に解くことができます。minTrial[i][j] を「i個の卵とj階の建物があるときの、最悪ケースにおける最小試行回数」と定義します。

k階目から卵を落とすと仮定した場合、結果は次の2通りに分けられます。

• 卵が割れた場合： 残りの卵は i-1 個となり、k-1 階以下を調べればよい → minTrial[i-1][k-1]
• 卵が割れなかった場合： 卵は i 個のまま、k+1 階以上（j-k 階分）を調べればよい → minTrial[i][j-k]

最悪ケースに備えるため両者の最大値を取り、さらに今回の1回を加算します。すべての k について調べ、その最小値が答えとなります。

擬似コード

eggTrialCount(eggs, floors)

入力: 卵の数、最大階数
出力: 最小試行回数

Begin
    サイズ [eggs+1, floors+1] の行列を定義する
    for i := 1 to eggs, do
        minTrial[i, 1] := 1  // 1階なら試行は1回
        minTrial[i, 0] := 0  // 0階なら試行不要
    done

    for j := 1 to floors, do
        minTrial[1, j] := j  // 卵が1個なら線形探索でj回必要
    done

    for i := 2 to eggs, do
        for j := 2 to floors, do
            minTrial[i, j] := ∞
            for k := 1 to j, do
                res := 1 + max(minTrial[i-1, k-1], minTrial[i, j-k])
                if res < minTrial[i, j], then
                    minTrial[i, j] := res
            done
        done
    done

    return minTrial[eggs, floors]
End

C++による実装例

#include<iostream>
using namespace std;

int max(int a, int b) {
    return (a > b)? a: b;
}

// 最悪ケースにおける最小試行回数を求める関数
int eggTrialCount(int eggs, int floors) {
    // i個目の卵・j階における最小試行回数を格納する表
    int minTrial[eggs+1][floors+1];
    int res;

    // 1階からの試行は1回、0階は試行不要
    for (int i = 1; i <= eggs; i++) {
        minTrial[i][1] = 1;
        minTrial[i][0] = 0;
    }

    // 卵が1個の場合、各階について線形に調べる必要があるためj回
    for (int j = 1; j <= floors; j++)
        minTrial[1][j] = j;

    // 卵が2個以上の場合
    for (int i = 2; i <= eggs; i++) {
        // 2階以上の場合
        for (int j = 2; j <= floors; j++) {
            minTrial[i][j] = INT_MAX;
            for (int k = 1; k <= j; k++) {
                // 割れた場合と割れない場合のうち、悪い方（最大値）を採用
                res = 1 + max(minTrial[i-1][k-1], minTrial[i][j-k]);
                // より良い戦略（最小値）を選ぶ
                if (res < minTrial[i][j])
                    minTrial[i][j] = res;
            }
        }
    }

    // 求める卵の数と階数に対する試行回数を返す
    return minTrial[eggs][floors];
}

int main () {
    int egg, maxFloor;
    cout << "卵の数を入力してください: "; cin >> egg;
    cout << "最大階数を入力してください: "; cin >> maxFloor;
    cout << "最小試行回数: " << eggTrialCount(egg, maxFloor);
}

実行結果

卵の数を入力してください: 4
最大階数を入力してください: 10
最小試行回数: 4

まとめ

卵落としパズルは、動的計画法の考え方——部分問題への分割と最適な選択の蓄積——を学ぶのに最適な題材です。時間計算量は O(eggs × floors²) となりますが、卵の数や階数が増えても確実に正解を導き出せる堅牢な手法です。二分探索を応用した発展的な解法もありますので、興味のある方はぜひ比較してみてください。