みんな結構頑張ってるようだ。基本は二分探索的なことをやってる人が多くて、O(n)っぽいアルゴリズムではMAX=10000に対抗するのは難しい。
二分探索だと嘘率が低いうちはかなり効果的だが、前半で嘘をつかれた場合にダメージがでかいというか正真正銘の二分探索でやっているとそれこそすごい計算量になってしまう。のでそれを補正するのに工夫が必要なんだな。
嘘をつかない場合に収束の早いアルゴリズムはある程度範囲を絞り込むのには役に立つが、嘘を疲れるとある一定の範囲以下ではだいぶ遅くなるので、いかに効率よく絞り込むかってのがブレイクスルーになりそうな感じ。
意外と単純なものの方が回数が少ないから曲者だ。
