[ABC009] C - 辞書式順序ふたたび
[Q] https://atcoder.jp/contests/abc009/tasks/abc009_3
貪欲的に解き始めたが、WAパターンをつぶすごとに重い実装になってしまった。
頭を切り替えて、探索したらあっさり。
考察
1. 先頭文字にaを入れてみる。ダメならbを入れてみる…という探索。
2. ダメかどうか、というのは、この先できるだけSに合わせて配置したとしても、ズレがKを超えてしまうこと。
アルファベットごとに、必要な数 - 残っている数を算出すれば高速判断できる。
N=10 K=3
S="helloworld"
1. アルファベットごとの要素数をカウントする。
d:1
e:1
h:1
l:3
o:2
r:1
w:1
2. 0文字目を探索。
a,b,cは0個なので飛ばす。
d:1個なので、シミュレートしてみる。
S[0] != 'd' なので ズレ1
S[1]以降でどれだけズレるか調べる。
残りS - 残り要素
d:1 - 0 = 1 // d が絶対に不足することになるので、ズレ1見込み
e:1 - 1 = 0
h:0 - 1 = 0 (-1) // 残り要素が多い分にはかまわない
l:3 - 3 = 0
o:2 - 2 = 0
r:1 - 1 = 0
w:1 - 1 = 0
---------------
ずれ1見込み
ans[0] = d を採用した場合
S[0]が違うのでズレ1なのと、S[1]以降でdが不足しているのでズレ1。
あわせてズレ2見込み。
K=3まで許容されるので、dは確定していい。
ans = "d"
S[0] != 'd' なので、ズレ1は確定させておく。
2. 1文字目を探索。
eが最速で、S[1] == eなので、ズレの増加なし。
eが確定して
ans = "de"
ズレ1
そんな感じで
ans = "dehloworll"実装
ll N, K;
string S;
ll elm[26]; // 残ってる要素
ll selm[26]; // Sの要素
void solve() {
// init
rep(i, N) { ++elm[S[i] - 'a']; }
rep(i, 26) selm[i] = elm[i];
string ans(N, '.');
ll pdif = 0;
rep(i, N) {
--selm[S[i] - 'a'];
// a~zまでいったん入れてみる。
for (char c = 'a'; c <= 'z'; ++c) {
if (elm[c - 'a'] <= 0) continue;
ll ndif = pdif + (c != S[i]);
--elm[c - 'a'];
// simulate
rep(j, 26) { ndif += max(0LL, selm[j] - elm[j]); }
// 採用
if (ndif <= K) {
ans[i] = c;
if (S[i] != c) ++pdif;
break;
}
// 復元
++elm[c - 'a'];
}
}
cout << ans << endl;
}
int main() {
cincout();
cin >> N >> K >> S;
solve();
}