二分探索について

　実際に二分探索を行う部分について、補足を行います。

　二分探索を行える条件として「単調性」というワードが付きまといがちですが、より噛み砕いて記述すれば、以下のような状況で有効ということです。

• 実数や整数に対して統一的に定義される条件について、ある値 \(x\) が存在して、\(x\) 以上では常に条件が成立する / しない、かつ \(x\) 未満では常に条件が成立しない / する。

　この意識を念頭に置けば、二分探索で求めるものは、最大値や最小値というよりは境界であると表現したほうが、自然に捉えやすいでしょう。

　続いて具体的な過程を説明します。今回のように定義域が整数範囲である場合は、一例として二分探索は次のように進行します。

• 条件をみたすかが一致しないように端の \(2\) 数 \(l<r\) を適当にとる。この時点で \(r-l=1\) ならば、それが境界であるからすることはない。
• \(mid=(l+r)/2\) について条件をみたすか考える。\(l\) と条件をみたすかが一致すれば \(l=mid\) とおきなおし、そうでない場合は \(r=mid\) とおきなおす。
• 上のステップを繰り返せば、最終的に \(r-l\) が \(1\) となるタイミングが存在することがわかる。これが求める境界である。

　境界に向かって左右から幅を詰めていくイメージです。なお \(mid\) として \(l,r\) の平均を取っているのは一つの手段にすぎません。例えば「\(1:2\) に内分する点をとる」などとしても同様に作動させることは出来ます。しかし上のように安直に平均を取っておけば、必ず区間の幅がおよそ半分になるというメリットがあり、かつ最後に境界付近まで来たときに細かいことを気にせずに済むので、単純さと相まってこの方法で実行されるということです。

　今回であれば、整数 \(n>d\) についての条件は公式解説に則れば「\(f(n)\leq M\) であるか」です。上の説明に従えば、最初のステップにおいては端を \(f(l)\leq M<f(r)\) となるように定めることになります。\(r\) は例えば \(M+1\) とすればよいです。\(l\) については、便宜上 \(n\leq d\) となることを許しても \(f(n)\) は問題なく定義できるので、特に \(f(0)=0\) とみなせることから \(l=0\) とすればよいです。このとき、最終的に得られた \(l(=r-1),r\) について \(\max(r-d,0)\) が答えとなります。

　なお実際には、今回は最初に \(l=d\) としても (\(f(d)>M\) である可能性こそあるものの) 同様のコーディングでも矛盾なく作動することが簡単にわかります。しかし、上で述べたような思考プロセスを経ることは、少し遠回りかもしれませんが、二分探索に入門するにあたって混乱しないようにするには、より堅実なのではないかと思います。

\(f(n)\leq M\) の判定について

　公式解説でも言及のある通り、\(f(n)\) を安直に計算すると容易くオーバーフローするので、少し工夫が必要です。

方法1

　真に気を付けるべきポイントを単純化して記述すれば、以下のようになります。

• 正整数 \(a,b,c\) について \(a\times b\leq c\) であるかの判定で \(a\times b\) のオーバーフローに留意する

　これは \(a\leq[c/b]\) と同値であり、これならばオーバーフローの心配なく処理できます 。

　なお今回は気にしなくても済みますが、和について考える場合も、差の条件に直して処理したほうが良い状況も考えられるでしょう。

方法2

　\(M\) を \(n\) 進数で表現しましょう。これを \(X\) と比較したとき、まず桁数を見て、それが一致していれば上の位から順に比較していけばよいです。