コンテスト中の考察(AC)
- 長さNの数列中に適当にK個数を置いていい感じにしたい。
- priority queue使えば行けるんじゃね？って思う。
1,2,1,2,3,4,5みたいな配列をランレングス圧縮みたいな感じで2,5みたいにしてキューに突っ込む。そんで、大きい方から順に半分に分割していく。天才か？400をあっさり思いつくとか天才か？ - でもこの方針は間違えていた。天才じゃなかった。この考察では入力例2で落ちる。
2,7→2,3,3→2,1,1,3になるけど、本当は2,7→2,2,4→2,2,2,1になるのが正しい。 - うーん、どーしよーかなー。
- DFS書けば多分行けるけどTLEするしなぁ。メモ化したいけど多分状態持ちきれない。
- お腹が空いたのでご飯を食べる。やはり米はうまい。
- 何も思いつかないので、チートシートを見る。「決め打ち」って単語が目に入ったので、これで解けるのでは？と思う。これ二分探索できるんじゃね？
- 答えを固定して二分探索をしてみる。ACする。やったぜ！
反省
- 時間かけすぎ。二分探索が見えるまでに40分くらいかかってる。
どうすればよかったか
- 直接求めるのが難しそうなら答えの決め打ちを考えてみる。
理想の考察
- 直接求めるの厳しいから答えの決め打ちを考える。答えを決め打って二分探索するやつ
- 単調性があれば二分探索できる。単調性は
xxxxooooooみたいになってればいい（xは条件を満たさない。oは条件を満たす）。今回は、答えに対して単調性がある。答えが小さいほど石の個数は厳しくて、答えが大きいほど石の個数はゆるい。
コード
#include <bits/stdc++.h>
using namespace std;
#define int long long
int N, K;
vector<int> a, v;
bool check(int mid) {
int cnt = 0;
mid++;
for (int i = 0; i < N; i++) {
if (v[i] % mid == 0) {
cnt++;
}
}
return cnt <= K;
}
// 二分探索
int bin() {
int ok = N + 10;
int ng = 0; // -1だとcheck()関数で受け切れないので死ぬ
while (ok - ng > 1) {
int mid = (ok + ng) / 2;
if (check(mid)) {
ok = mid;
} else {
ng = mid;
}
}
return ok;
}
signed main() {
cin >> N >> K;
a.resize(N);
for (int i = 0; i < N; i++) {
cin >> a[i];
}
// 何個連続してるかっていう配列を作る
int old = a[0];
int cnt = 0;
for (int i = 0; i < N; i++) {
if (a[i] == old) {
cnt++;
} else {
old = a[i];
cnt = 1;
}
v.push_back(cnt);
}
int ans = bin();
cout << ans << endl;
return 0;
}
要点
- 答えを直接求めるのが厳しそうな時は二分探索を考える。
- 「f(制約) = 答え」を「g(答え) = 制約」みたいにするイメージ。
- そんで、関数g()に単調性があれば二分探索できる。
- あと、okとngはcheck()関数が受け入れられる範囲の数を入れる。本番中範囲外の値を入れてバグらせた。
- 最大値の最小化は二分探索！！