全探索+二分探索

前回の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)となる。

ここで、二分探索と全探索の順番を入れ替えてみると次のようになる。

int r = INF;
for (State s : allStates) { // 全探索
	int lb = 0, ub = INF;
	while (ub - lb > 1) { // 二分探索
		int mid = (lb + ub) / 2;
		if (check(s, mid)) ub = mid;
		else lb = mid;
	}
	r = min(r, ub);
}
return r;

こうやって書いてみると、二分探索によって求まった最小値ubがそれまでの最小値rを更新するためには、少なくともcheck(s, r - 1)はtrueでないといけないので、次のような枝刈りを入れることができることに気がつく。

int r = INF;
for (State s : allStates) { // 全探索
	if (!check(s, r - 1)) continue; // 枝刈り
	int lb = 0, ub = INF;
	while (ub - lb > 1) { // 二分探索
		int mid = (lb + ub) / 2;
		if (check(s, mid)) ub = mid;
		else lb = mid;
	}
	r = min(r, ub);
}
return r;

これで、時々二分探索が不要になるので高速になるような気がする。
実際、この枝刈りをいれた場合の計算量は見積もることが可能で、1/k番目の状態において、それまでの最適解を更新できる確率は、探索順がランダムならば期待値的に1/kであるので、二分探索が実行される回数の期待値は、1+1/2+1/3+...+1/N=O(logN)となる。
したがって全体の計算量はO(NK+RKlogN)となり、Nが大きければ二分探索の反復回数がほぼ無視できるようになる。

というわけで、二分探索中の全探索は外に出して枝刈りいれると高速になるよっていう話でした。

で、SRM481の900にもどると、全探索してマッチングで判定する場合、N=15C7=6435、K=16^3、R=20くらいなので、全部掛けると危なそうだが、枝刈り入れれば余裕で間に合うと判断できる。