「答えを決め打つ」タイプの二分探索を使いこなそう

ゴールデンウィークの有志コンテストなどで多く出題され、話題になったので記事を書こうと思います。

対象レートはだいたい緑～水色（最後のほうは青くらいまで）です。実際のAtCoderの問題を使って説明していくので、ネタバレになる点はご了承ください。

「答えを決め打つ」タイプの二分探索とは

この記事で扱うのは、以下のような問題＆解法です。

「○○という条件を満たす $X$ の最小値を求めよ」という問題において、
「ある値 $X$ が与えられたとき、○○を満たすことはできるか？」という判定問題を考え、
その判定問題を繰り返し解くことでYesになる $X$ とNoになる $X$ の間の境界を特定し、元の問題の答えを求める解法。

もちろん最小値ではなく最大値である場合もあります。実際にいくつか問題を見ていきましょう。

問題例1：花束（ARC050-B）

B - 花束

解法

持っている花から2種類の花束を作り、その合計数を最大化する問題です。制約が大きく、正攻法で取り組むのは難しいです。

ここで「ある値 $X$ が与えられたとき、合計 $X$ 個の花束を作ることはできるか？」という判定問題を考えます。唐突ですね。騙されたと思って考えてみましょう。

花束の個数を決めると、この判定問題は以下のように解くことができます。

全ての花束は赤青少なくとも1本ずつの花を含むので、まずは $X$ 個分の花束の赤青1本ずつを確保する。
すると残りは赤 $x-1$ 本または青 $y-1$ 本で花束を1個作ることができるので、赤青それぞれ独立に作れる花束の個数を計算する。
合計が $X$ 個以上であればYes、そうでなければNo。

この判定問題を利用して、元の最大化問題を以下のように解くことができます。

判定問題がYesになることが明らかなの値を ok という変数に、判定問題がNoになることが明らかなの値を ng という変数に代入して初期値とする。
- 例えば、0個の花束は明らかに作れるので ok = 0 とし、花の本数の半分を超える個数の花束は明らかに作れないので ng = (R+B)/2 + 1 とする。
以下の処理を、ok と ng の差が1になるまで繰り返す。
- ok と ng の平均 mid = (ok+ng)/2 を取る。（小数点以下は切り捨てて良い）
- $X$ を mid としたときの判定問題を解き、結果がYesなら ok に、Noなら ng に mid を代入する。

そうです、二分探索です。この処理で ok と ng の差が1になるまで繰り返せば、そのときの ok の値が求めたい最大値になっているのです。

単調性の確認

さきほどの解法は何故成立するのでしょうか？この解法の正しさを保証するための重要な性質が「単調性」です。

この問題の判定問題では、 $X$ の値が大きいほうが条件が「厳しく」なります。そして、答えがYesとなる $X$ の範囲とNoとなる $X$ の範囲は数直線上のある境界で綺麗に分かれている、と言うことができます。これが単調性です。

f:id:betrue12:20190511141733p:plain

別の言い方をすると、

Noと判定される $X$ からより厳しいほうに変化させても、必ず答えはNoのままである。
Yesと判定される $X$ からより甘いほうに変化させても、必ず答えはYesのままである。

という性質を両方満たすこと、と理解することもできます。

問題で問われている「条件を満たす最大値」は、図を見ると境界を挟んだYes側の値であることが分かります。そして先ほどの解法では、変数 ok が常に境界よりYes側に、変数 ng が常に境界よりNo側にある状態を保ちながら距離を縮めていくことができます。そのため差が1になったときには自動的に境界が求まっていて、正しい答えを求めることができます。

二分探索を思いつくポイント

この問題では花束の個数をある値 $X$ に固定することで、赤青独立に考えるための道筋ができました。このように「正攻法で解くのが難しそう」「でも、値を固定することで何か嬉しいことがある」という特徴を持つ最小化/最大化問題は、二分探索を使うチャンスです。

ACコード（C++）

Submission #5333144 - AtCoder Regular Contest 050

問題例2：Boring Sequence（CPSCO Session4-D）

D - Boring Sequence

解法

この問題では、連続する部分列であってすべて同じ要素からなるものの長さの最大値を「退屈さ」と定義しています。そして数列の要素を $K$ 個まで書き換えることで、この退屈さを最小にしたいです。

何となく「同じ要素がいっぱい連続しているところを切りたい」という気持ちになります。ただ同じ要素が連続しているところが複数ある、長さもバラバラ、そんなときにどのように切っていけば退屈さが一番小さくなるのかを考えるのは難しいです。（一応、正攻法でもできます。公式解説参照）

そこで「ある値 $X$ が与えられたとき、退屈さを $X$ 以下にすることはできるか？」という判定問題を考えます。これはつまり「同じ要素が連続している区間の長さを全て $X$ 以下にできるか？」という問題と同じです。

このようにすると条件を満たすために最適な戦略がハッキリします。

左から順に数列を見ながら連続している要素の個数を数えていき、 $X$ を超えそうになった瞬間に値を書き換えて切る。

$X$ さえ超えなければいくら長くなってもいいけど、どこか1箇所でも $X$ を超えると一発アウトなので、 $X$ を超えそうになるギリギリで値を書き換える権利を使う、という考え方です。

判定問題ではこの戦略をシミュレートし、合計 $K$ 回の操作で連続している要素の個数が $X$ を超えないようにできるかを確かめればよいです。先ほどの問題と同様、「判定問題がYesになることが明らかな値」「判定問題がNoになることが明らかな値」をから始めて二分探索をすることで答えを求めることができます。

単調性の確認

単調性を確認しましょう。ここで言い換えが「退屈さを $X$ 以下にすることはできるか？」だったことを思い出してください。

もしこれを「退屈さを $X$ ぴったりにすることはできるか？」と言い換えてしまうと、この解法は失敗してしまいます。「あまり $X$ が大きいと逆に実現不可能になる」みたいな現象が起こってしまいます。この場合は判定問題も解きにくくなってしまうので散々ですね。

「 $X$ 以下にすることはできるか？」という問題にすることで、 $X$ が大きいほど条件が甘く、小さいほど条件が厳しくなり、単調性を満たすことができます。この判定問題の作り方については、後ほどまた触れたいと思います。

二分探索を思いつくポイント

この問題も、退屈さの値を固定すると嬉しいことがあるタイプの問題です。

特に、「できる操作に自由度があって最適な戦略が分かりづらい」「でも値を固定することで、ギリギリまで粘る・貪欲に取るなど最適な戦略がはっきりする」という点が特徴的で、このような場合には二分探索が有効です。

ACコード（C++）

Submission #5285338 - CPSCO2019 Session4

ここまでのまとめ

ここまでの解説の繰り返しになりますが、「答えを決め打つ」タイプの二分探索を見破るコツをまとめておきます。

「ある値 $X$ が与えられたとき、○○を満たすことはできるか？」という判定問題が解きやすい。値を固定すると何か嬉しいことがある。
単調性がある。 $X$ の値の大小と、条件の「厳しさ」が直結している。

これひょっとして二分探索なのでは？と思う問題があったら、是非この2点を満たしているかどうか確認してみてください。

典型パターン「最大値の最小化」

「Boring Sequence」のように、「○○の最大値を最小化せよ」という問題から「○○の最大値を $X$ 以下にできるか？」という判定問題を導くのは、予め知っていないと難しいかもしれません。このような「最大値の最小化」「最小値の最大化」は二分探索で解けることが非常に多い問題なので、典型パターンとして覚えてしまいましょう。

「○○の最大値の最小化」は、「○○の最大値を $X$ 以下にできるか？」という判定問題を使って二分探索に持ち込むことができます。これは「全ての○○を $X$ 以下にできるか？」という問題と同じです。境界で分けた時に $X$ が大きい方が「Yes」側、小さい方が「No」側で、「Yes」側の境界値が答えです。
「○○の最小値の最大化」は、「○○の最小値を $X$ 以上にできるか？」という判定問題を使って二分探索に持ち込むことができます。これは「全ての○○を $X$ 以上にできるか？」という問題と同じです。境界で分けた時に $X$ が小さい方が「Yes」側、大きい方が「No」側で、「Yes」側の境界値が答えです。