Binary Searchの集合への適用について
Binary Searchは、例えばソートされている整数のリストにある値が含まれているかどうかを確認するときに使うと、単純なループでチェックするよりもかなり計算量を抑えることができる。単純にループで確認するやり方は計算量がO(n)になるが、Binary SearchではO(log(n))になる。どのくらい違うかというとO(1)≒O(log(n))≪O(n)くらいに考えれば良い。
このようにBinary Searchでリストから値を検索するためのライブラリは多くの言語で提供されている。ただ、Binary Searchはもっと強力で、ある実数の集合に対する適用が可能だ。対象が一見してシーケンシャルなものである必要はない。これは競プロでは良く使われる手法であり、慣れてくれば問題文を理解した時点ですぐにBinary Searchによる解法が適当だと判断できるようになるらしい。
対象が集合になってもBinary Searchとして考えるのはリストである。ただし、noとyesがそれぞれ連続して現れるように述語(Predicate)を考える必要がある。noとyesの境目は一つであり、その境目に向かってBinary Searchが進んで行くことになる。実装における勘所は以下になる。
- 解答すべき値をLower boundとUpper boundの間で上下に振り、与えられた条件が答えになるような述語を考える
- 与えられた条件の中で、最小値(Lower bound)と最大値(Upper bound)を考える
述語はyesかnoを返却する関数を考えれば良い。ただし、リストに適用した場合の述語は、medianと比較した結果を返すだけ、であるのに比べると、もっと複雑になる。また、与えられた条件の中でboundを導き出すことも非常に重要である。例えば、以下の問題では実際にboundを取り違えて正しい値に収束しない実装を書いてしまった。
Problem Statement for FairWorkload
int getMostWork(int[] folders, int workers){ int low = 0; int high= 0; for(int f: folders){ high+=f; } int mid=0, c=0, t=0, m=0; while(low<high){ mid = low + (high-low)/2; c=t=0; for(int f: folders){ if(mid<f){ break; } if(t+f<=mid){ t+=f; } else{ t=f; c++; } } if(c<workers){ high = mid; } else{ low = mid+1; } } return low; }
この場合、Upper boundは全ての数を足し合わせたもので問題無いが、Lower boundは0以上でかつ十分小さな値、であればなんでも良いわけではない。ここは条件として与えられたリストの中の最大の値を使わなければいけない。
for(int f: folders){ if(low<f){ low=f; } // XXX high+=f; }
ソートされた整数のリストに対するBinary Searchのboundは、そのリストのインデックスの最大値と最小値であることは明白だが、集合に適用する場合はここを考えるのが一つの勘所になる。
このようにしてTopCoderのModerateレベルのBinary Searchで解ける問題を解いてみた。実装は以下。TopCoderは実際に解いた解答者の実装を公開しているので、そちらを参考にする方が良い。
