[解決済み] 窓から猫を放り投げる

質問

あなたが高いビルの中で猫と一緒にいると想像してください。猫は低層階の窓から落ちても大丈夫だが、高層階から投げられると死んでしまう。猫が生き延びることができる最長落下距離を、最少の試行回数で求めるにはどうしたらよいか？

もちろん、猫が1匹しかいない場合は、直線的にしか検索できません。まず、1階から猫を投げます。生き残ったら、2階から投げる。最終的に、f階から投げられた猫は死ぬ。そのとき、f-1階が最大安全階であったことがわかる。

しかし、猫が複数いる場合はどうでしょうか？今度はある種の対数探索を試みることができる。例えば、建物の階数が100階で、同じ猫が2匹いるとします。最初の猫を50階から投げ出して死なせたとすると、50階を直線的に探索すればよいことになります。最初の試みに低い階を選べば、さらに良い結果が得られるでしょう。例えば、20階ずつ問題に取り組むことにして、最初の致命的な階を50階としましょう。この場合、最初の猫は20階と40階からの飛行に耐えられ、60階で死ぬことになります。あとは41階から49階までを個別にチェックすればいいのです。これは、二項消去法を使った場合の50回よりはるかによい試行回数である。

一般に、猫が2匹いるn階建てのビルで、最適な戦略とその最悪の場合の複雑さはどのようなものでしょうか？n階建てで猫がm匹の場合はどうでしょうか？

すべての猫は等価であると仮定する：与えられた窓から落ちても、すべて生き残るか死ぬかである。また、すべての試みは独立である。もし猫が落下して生き延びたとしても、まったく無傷である。

学校の課題で解いたことがあるかもしれませんが、これは宿題ではありません。今日ふと思いついた気まぐれな問題で、解法は覚えていません。この問題の名前や解法アルゴリズムを知っている人がいたら、ボーナスポイントを差し上げます。

解き方は？

階数がn、猫がmの一般的なケースで、ちょっとしたDP（動的計画法）を書くと簡単にできます。

主な計算式です。 a[n][m] = min(max(a[k - 1][m - 1], a[n - k][m]) + 1) : for each k in 1..n ということである。

• 最初の猫がk番目の階から投げられて死んだとすると、次のようになります。 k - 1 をチェックする必要があります（すべて k ) と m - 1 猫 ( a[k - 1][m - 1] ).
• もし猫が生き残ったら n - k のフロアが残っています。 k ) で、まだ m の猫です。
• 2つのうち最悪のケースを選ぶべきであり、したがって max .
• + 1 は、（猫が生き延びたかどうかに関係なく）1回の試行を使っただけという事実からきています。
• 私たちは最良の結果を得るために、可能な限りのフロアを試しています。 min(f(k)) : for k in 1..n .

のGoogleの結果と一致します。 ガウラヴ・サクセナ のリンクは (100, 2) です。

int n = 100; // number of floors
int m = 20; // number of cats
int INFINITY = 1000000;

int[][] a = new int[n + 1][m + 1];
for (int i = 1; i <= n; ++i) {
    // no cats - no game
    a[i][0] = INFINITY;
}

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        // i floors, j cats
        a[i][j] = INFINITY;

        for (int k = 1; k <= i; ++k) {
            // try throw first cat from k-th floor
            int result = Math.max(a[k - 1][j - 1], a[i - k][j]) + 1;
            a[i][j] = Math.min(a[i][j], result);
        }
    }
}

System.out.println(a[n][m]);

一番良いものを保存しておけば、戦略（最初の猫の投げ方）を簡単に見つけることができます。 k を別の配列に格納します。

O(n^3)の計算を伴わない、もっと速い解決策もあるのですが、もうちょっと眠いです。

編集

そうそう。 以前、この問題をどこで見たか覚えています .