解の二分探索

解の二分探索（決め打ち二分探索）とは

直接解を求めるのが厳しい場合、単調性があることを利用して二分探索で解を求められる場合があります。最大値や最小値を求める問題で解を決め打ちして、それが条件を満たすかどうかの判定関数が簡単に実装できる場合はこれが利用できます。
二分探索が利用できることに気が付くまでが大変なので、それが一番のポイントな気がします。
二分探索の実装はこちらのサイトのめぐる式二分探索が個人的に書きやすく感じたので参考にさせていただきました。

例題（CPSCO2019 D - Boring Sequence）

ラスク君は長さ$N$の数列$a$を持っています。
数列の退屈さとは、連続する部分列であってすべて同じ要素からなるものの長さの最大値のことをいいます。
ラスク君は、数列$a$の要素を$K$個まで任意の整数に書き換えて、退屈さをできるだけ小さくしようとしています。
達成できる退屈さの最小値を求めてください。

～制約～
・入力は全て整数である。
・$1≤K≤N≤2×10^5$
・$1≤a_i≤N$

入力例
10 2
3 3 3 3 4 4 4 4 4 4
出力例
3
（例えば、前から1番目の3と7番目の4をほかの数字に変えれば退屈さは3となり、これが最小。）

考え方

1つ目の連続する文字列の文字を1つ変えると退屈さは$1/2$になって、2つ変えると$1/3$になって、2つめの区間では…合計が$K$回までだから…と考えていくとややこしくなって厳しいので他の方法が無いか考えてみます。
退屈さをある数$x$以下にできるかを考えると、$x$が非常に小さいときは不可能で、$x$が非常に大きいときは可能です。最終的な答えを$ans$とすると、$x < ans$のときは不可能で、$ans ≤ x$のときは可能であるという単調性があります。このことから、二分探索が利用できるのではないかと気が付きたいですね。
退屈さを$x$にすることは可能かどうかの判定関数は、数列を前から順番に見ていき連続する区間が$x$を超えれば数字を1つ書き換えて、書き換えた回数が$K$以下かどうかで$O(N)$で簡単に実装できます。
判定関数が実装できればあとは解を二分探索すればいいです。
今回は右側（大きい側）が常に条件を満たすので区間は$(a,b]$となり右側に閉じています。初期値を$low=0$（ありえない値）、$high=N$（大きめの値）として最終的な答えは$high$の方を出力します。

コード

#include <bits/stdc++.h>
using namespace std;
int N,K,a[200000];
bool check(int x){//判定関数
    int count=0,now=1;
    for(int i=1;i<N;i++){
        if(a[i-1]==a[i]){
            now++;
        }
        else{
            now=1;
        }
        if(now>x){
            count++;
            now=1;
            i++;
        }
    }
    if(count<=K) return true;
    return false;
}
int solve(){//二分探索
    int high=N,low=0;
    while(high-low>1){
        int mid=(high+low)/2;
        if(check(mid)) high=mid;
        else low=mid;
    }
    return high;
}
int main(void){
    cin>>N>>K;
    for(int i=0;i<N;i++) cin>>a[i];
    cout<<solve()<<endl;
    return 0;
}

練習問題

二分探索に気が付くがどうかが大事な気がするので、ここで紹介するのはどうなのかなとは思いましたが一応…
ARC050 B - 花束
ABC034 D - 食塩水
ABC144 E - Gluttony