[AGC029] C - Lexicographic constraints
[Q] https://atcoder.jp/contests/agc029/tasks/agc029_c
考察
1. 使用する種類数で二分探索する。
2. 種類数が十分かどうか、のシミュレートはどのくらい？
3. N要素をひと舐めする必要がある。mapでO(NlogN)でいけそう。
4. mapでどう管理しよう
(1). 値が減る場合の処理
->末尾を+1する。
->末尾を+1できない場合は桁上げする。
->桁上げが尽きたらfalse
(2). 値が増える場合の処理
->新しい末尾に0を追加する
入力例2
N=5
A:2 3 2 1 2
1. 種類数は 1 ~ 5 まであるので、にぶたん
2. mid = 2 としてシミュレートする
・A[0] = 2
M[2] = 0 (aa)
・A[1] = 3
M[2] = 0
M[3] = 0 (aaa)
・A[2] = 2
M[2] = 1 (ab)
M[2]以降にある要素は全部削除する。
M[2]を1加算する。
・A[3] = 1
M[1] = 1 (b)
M[1]以降にある要素を全部削除する。
M[1]=0を仮置きしたあと、M[1]を1加算する。
・A[4] = 2
M[1] = 1
M[2] = 0 (ba)
末尾に追加するだけなので、M[2] = 0を追加。
これが最短なので2が回答。Q. もしA[]が昇順だったら？
A. a->aa->aaa...とすればいいので、1種類でいける。
実装
ll A[200020];
ll N;
ll binary_search(ll R) {
ll L = 0;
while (R - L > 1) {
ll mid = (L + R) / 2;
map<ll, ll> M;
bool ok = true;
rep(i, N) {
ll a = A[i];
bool is_first = false;
if (M.count(a) == 0) is_first = true;
M[a]; // ないならM[a]=0を生成
auto it = M.find(a);
auto nit = it;
++nit;
// つけたしたのが末端なら、そこでおしまい。
if (nit == M.end() && is_first) {
continue;
}
// 以降を全部0にしておく
while (nit != M.end()) {
M.erase(nit++);
}
// 繰り下げする場合
if (it->second == mid) {
while (it->second == mid) {
if (it->first == 0) break;
M[it->first - 1]; // 1個前の桁がないなら0入れ
M.erase(it--);
}
if (it->second == mid) { // false
ok = false;
break;
}
++it->second;
} else {
++it->second;
++it;
while (it != M.end()) {
M.erase(it++);
}
}
}
if (ok)
R = mid;
else
L = mid;
}
return R;
}
int main() {
cincout();
cin >> N;
rep(i, N) {
cin >> A[i];
--A[i];
}
ll p = -1;
bool is_zero = true;
rep(i, N) {
if (p >= A[i]) {
is_zero = false;
break;
}
p = A[i];
}
if (is_zero) {
cout << 1 << endl;
return 0;
}
cout << binary_search(N) + 1 << endl;
}