前回のSRMでLayCurseさんの900の解法を見て思い出したので解説。 次のように、二分探索の中で全探索をしているようなプログラムを考える。 int lb = 0, ub = INF; while (ub - lb > 1) { // 二分探索 int mid = (lb + ub) / 2; boolean tmp = false; for (State s : allStates) { // 全探索 if (check(s, mid)) tmp = true; } if (tmp) ub = mid; else lb = mid; } return ub; このプログラムを実行すると、check(s, r)を満たすようなsが存在する最小のrが求まる。 このプログラムの計算量は、状態数N=|allStates|、二分探索の反復回数をR、checkの計算量をKとすると、O(NRK)とな