C++で解くスーパーエッグドロップ問題 ― 最小手数を求めるアルゴリズム

問題概要

K個の卵と、1階からN階まである建物が与えられます。すべての卵は同じ性能を持ち、一度割れた卵は二度と使用できません。

0以上N以下のどこかに臨界階Fが存在し、Fより高い階から卵を落とすと必ず割れ、F以下の階から落とした場合は割れないものとします。各手番では、卵を1つ選び、1〜Nの範囲内の任意の階Xから落とすことができます。

目的は、Fの値を確実に特定することです。Fの初期値が何であっても対応できるようにするには、最低何回の操作が必要でしょうか。

例えば、入力が K = 2、N = 6 の場合、出力は 3 となります。

解法の考え方

この問題は、動的計画法（DP）と二分探索を組み合わせることで効率的に解けます。ある階midから卵を落としたとき、結果は次の2通りです。

• 卵が割れた場合： 残り卵はK−1個となり、探索範囲はmid−1階以下に絞られます。
• 卵が割れなかった場合： 卵はK個のまま残り、探索範囲はN−mid階に絞られます。

最悪ケースの手数を最小化したいので、各階について「割れた場合」と「割れなかった場合」のうち大きい方（最悪値）を取り、その中で最小となる階を二分探索で探します。さらに、同一状態の再計算を避けるためメモ化で計算結果をキャッシュします。

アルゴリズムの手順

1. 2次元配列dpを定義する。
2. solve(K, N) 関数を定義する。
3. N ≤ 1 の場合は N を返す。
4. K = 1 の場合は N を返す（卵が1個しかない場合は下の階から順に試すしかないため）。
5. dp[K][N] ≠ −1 の場合は dp[K][N] を返す（メモ化済み）。
6. ret := N、low := 0、high := N と初期化する。
7. low ≤ high の間、以下を繰り返す。
   • mid := low + (high − low) / 2
   • left := 1 + solve(K − 1, mid − 1)
   • right := 1 + solve(K, N − mid)
   • ret := min(ret, max(left, right))
   • left = right ならループを抜ける。
   • left < right なら low := mid + 1、そうでなければ high := mid − 1。
8. dp[K][N] = ret を返す。

main関数での処理

• dp を (K + 1) × (N + 1) の2次元配列として作成し、すべて −1 で初期化する。
• solve(K, N) の結果を返す。

以下の実装例を見ると、理解が深まるでしょう。

実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    vector<vector<int>> dp;
    int solve(int K, int N) {
       if (N <= 1)
          return N;
       if (K == 1)
          return N;
       if (dp[K][N] != -1)
          return dp[K][N];
       int ret = N;
       int low = 0;
       int high = N;
       while (low <= high) {
          int mid = low + (high - low) / 2;
          int left = 1 + solve(K - 1, mid - 1);
          int right = 1 + solve(K, N - mid);
          ret = min(ret, max(left, right));
          if (left == right)
          break;
          if (left < right) {
             low = mid + 1;
          } else
             high = mid - 1;
       }
       return dp[K][N] = ret;
    }
    int superEggDrop(int K, int N) {
       dp = vector<vector<int>>(K + 1, vector<int>(N + 1, -1));
       return solve(K, N);
    }
};
main(){
    Solution ob;
    cout << (ob.superEggDrop(2,6));
}

入力

2, 6

出力

3

計算量

• 時間計算量： O(K × N × log N) ― 状態の数は K × N、各状態で二分探索に log N 回の再帰呼び出しが発生します。
• 空間計算量： O(K × N) ― メモ化テーブルdpのための領域が必要です。