はまやんはまやんはまやん

hamayanhamayan's blog

Boring Sequence [CPSCO2019 Session4 D]

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;
}