例の卵の答え
chokudai さん経由で
Googleの入社試験問題ムズすぎい！
— ゆいまーる@ IXTゴリラモナコイナー (@decyuidec) August 22, 2019
私の答えは25回だ！ pic.twitter.com/uqFTp6mQLs
を見て面白そうなので解きました。
解法
考察
- 高さが 2 以下 -> 1 回だけ試せばよい (一番上は確実に壊れるはず)
- 高さが 3 以上の場合下から順番に試していくのは無駄すぎる
- 適当にスキップして試すのだが、ここで以下のようになる
- 壊れる -> そこから下を下から試すしかないので今の階数が max
- 壊れない -> 今の階数を引いたうえでその高さに対して再帰的に同じ手順をふめばよい
実装
上記を愚直に再帰で実装する。ただしメモ化しないと計算量が爆発するのでメモ化も実装する。
結論
14 回。
100 階で割れる場合は 14 27 39 50 60 69 77 84 89 93 96 98 99 と試せばよい。(13 回 で終了)。14 回となるのは 13, 26 ... 階で割れる場合
別解
実は以下のように試行回数と判定可能な高さは以下のように試行回数までの総和 + 1 となるのでそれを直接計算してもよい。
- 1 回で終わる : 2 階まで判定可
- 2 回で終わる : 4 階まで判定可
- 3 回で終わる : 7 階まで判定可
- 4 回で終わる : 11 階まで判定可
