https://atcoder.jp/contests/jsc2021/tasks/jsc2021_e
解説
https://atcoder.jp/contests/jsc2021/submissions/21831951
実装が爆発して、実装の手直しをあきらめてしまった。
理論を記しておくので参考程度で。
何から手を付けるか
情報量が多く、何から始めようかという気持ちになるかもしれない。
ステップアップで解く。
ちょうどレベルKの回文を作れるかどうかという部分が重要である。
サンプル2を見てみよう。
2 aabaaaabaa
書き換えた後にレベルKであるかを考えるが、もともとの文字が何であるかはレベル判定には関係がない。
（全部書き換えることができるので）
なので、より柔軟に考えることができるように？にしてみる。
2 ??????????
これでレベル2ということは回文をつなげた形になっているはずである。
同じになってほしい文字に同じ文字を割り当てた。
1 ABCDE EDCBA
これで1つ減ったが、それぞれについてさらにレベル1なので、回文をつなげた形になっているはずである。
0 AB C BA AB C BA
Cはこれ以上変更しようがないので、ABを考えてみると、レベル2なのでA=Bとなってはならない。
よってここで分割ストップである。
ここまで分解して考えると、ABCの文字について等しい必要があり、かつABが回文になっていないことが要求される。
ABCは任意の文字に変更できるので、ここまで分割することでレベル2を実現可能であることが分かる。
この実験から何が分かる？
ここから重要な考察が得られる。
とあるレベル0の文字列Sとその連結過程で必要となるcの文字だけが決定すれば、他はすべてそれによって決定される。
例えばレベル2のacbcaacbcaは、レベル0の文字列acからスタートしている。
レベル0からレベル1へはt,c,rev(t)の操作を行っていて、cとしてbを使うことで、acbcaを得ている。
レベル1からレベル2へはt,rev(t)の操作を行っていて、ここはcがないため一意でacbcaacbcaを得ている。
この考え方が理解できることが重要。
実装
高レベルから低レベルへの分解を再帰関数を使って実装していこう。
f(L,R,level) := レベルがlevelである文字列[L,R)を分解する
例えばt,rev(t)で分解するとf(L,(L+R)/2,level-1)とf((L+R)/2,R,level-1)のように分解できる。
これでlevel=0に達すればその時の文字の範囲がスタートで使用する文字となるし、分解しても最終的にlevel=0を作ることが出来なければimpossible。
これをやりながら、等しくなるべき部分をUnionFindでまとめていこう。
ここまでで、impossibleかどうかの判定はできる。
行間が広すぎて分からなかったごめんなさい。
必要な最小の書き換え回数
例えばabccaを最小書き換えで回文にしてという問題は、回文として対応している位置毎に独立して考えることができる。
a-a, b-c, cという感じなので、b-cを書き換えればいい。
今回だと、同じ文字がペアではなく、複数の箇所が対象となっている。
この場合は、最も多く出てくる文字に合わせるのが最小回数となる。
cの場合はこれでOK。
問題はレベル0の文字列をどうするかである。
上記と同じ方針だと、回文になってしまう恐れがある。
この場合は、ある1箇所のみ別の文字に変えてしまうことで回文を回避する。
これには、そのある一か所について二番目に多く出てくる文字に変更して、コストが最小となるものを探していこう。
最終的に…
考察と実装を分けずに適当にやっていると、自分の実装のようなハウルの動く城ができあがる。
aabaaaabaa
↓ t,rev(t)
aabaa
↓ t,c,rev(t)
aa
↓ t,rev(t)
a
レベルは文字数で一意に定まる
これを見るとどことどこが同じである必要があるかが分かる
int K; string S; int N; //--------------------------------------------------------------------------------------------------- UnionFind uf; int SuperL, SuperR; bool f(int L, int R, int level) { // [L, R) int len = R - L; if (len == 0) { return level == 0; } if (level == 0) { SuperL = L; SuperR = R; return 1 < len; } if (len == 1) { SuperL = -1; SuperR = -1; return level == 1; } rep(offset, 0, len / 2) uf(L + offset, R - 1 - offset); bool res = true; if (len % 2 == 0) { res &= f(L, (L + R) / 2, level - 1); res &= f((L + R) / 2, R, level - 1); } else { res &= f(L, (L + R) / 2, level - 1); res &= f((L + R) / 2 + 1, R, level - 1); } return res; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> K >> S; N = S.length(); uf.init(N); bool res = f(0, N, K); if (!res) { cout << "impossible" << endl; return; } set<int> ng; if (0 <= SuperL) { rep(i, SuperL, SuperR) ng.insert(uf[i]); } map<int, map<char, int>> grp; rep(i, 0, N) grp[uf[i]][S[i]]++; int ans = 0; fore(p, grp) { if (ng.count(p.first)) continue; int tot = 0; int ma = -1; fore(p2, p.second) { tot += p2.second; chmax(ma, p2.second); } ans += tot - ma; } if (1 < SuperR - SuperL) { string s = ""; int cst = 0; rep(i, SuperL, SuperR) { int tot = 0; int ma = -1; char ma_c; fore(p, grp[uf[i]]) { tot += p.second; if (chmax(ma, p.second)) ma_c = p.first; } cst += tot - ma; s += ma_c; } int len = SuperR - SuperL; bool ok = false; rep(i, 0, len / 2) if (s[i] != s[len - 1 - i]) ok = true; if (ok) { ans += cst; } else { int opt = inf; rep(i, SuperL, SuperR) { int tot = 0; map<char, int> v; int ma = -1; char ma_c; fore(p, grp[uf[i]]) { tot += p.second; if (chmax(ma, p.second)) ma_c = p.first; v[p.first] = p.second; } int ii = i - SuperL; int ii2 = len - 1 - ii; if (ii != ii2) { rep(j, 0, 26) { char c = char('a' + j); if (s[ii2] != c) chmin(opt, cst + ma - v[c]); } } } ans += opt; } } cout << ans << endl; }
