https://atcoder.jp/contests/cpsco2019-s4/tasks/cpsco2019_s4_d
前提知識
解説
https://atcoder.jp/contests/cpsco2019-s4/submissions/5285258
二分探索で解く。
二分探索系は、二分探索に気づくまでが長くて大変だが、頑張ってとしか言えない。
強いて言うなら、退屈さは連続する長さの最大値であり、それを最小化したいという問題。
最大値の最小化といえば二分探索と言われていたような気がする。
評価関数check(len) := K個以下の置き換えで退屈さlen以下を達成できるか
これは先頭から連続している要素を数えていって、lenより大きくなったら、
その要素を入れ替えるという貪欲を行っていく。
最終的に入れ替えた回数がK回以下であればtrue
int N, K, A[201010]; //--------------------------------------------------------------------------------------------------- bool check(int len) { int need = 0; int cnt = 0, pre = -1; rep(i, 0, N) { if (pre != A[i]) cnt = 1, pre = A[i]; else cnt++; if (len < cnt) { cnt = 0; need++; } } return need <= K; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> K; rep(i, 0, N) cin >> A[i]; int ng = 0, ok = 201010; while (ng + 1 != ok) { int md = (ng + ok) / 2; if (check(md)) ok = md; else ng = md; } cout << ok << endl; }