[AGC026] C - String Coloring
[Q] https://atcoder.jp/contests/agc026/tasks/agc026_c
[解説] https://img.atcoder.jp/agc026/editorial.pdf
問題の特徴をつかむ解法だった。すごい。種明かししちゃえばすぐわかってしまう。
1. 2N文字並んでるけど、N文字 + N文字に分解する。
2. 前半のN文字を反転させる。
3. それぞれbit全探(2^N)。0の文字だけをつなげた文字列S0と、1の文字だけをつなげた文字列S1を作ってみる。
4. なんと、前半Nの{S0, S1}と、後半Nの{T0, T1} の組み合わせが合致する塗り方が、解を満たしている。すごい。
N = 4
S = cabaacba
1. 4 文字ずつに分ける。
T = caba
U = acba
2. T だけ反転。
< T = abac >
U = acba
3. bit全探索。
たとえば、
T = abac
0110
U = acba
0011
を考える。
T0 = "ac" = U0
T1 = "ba" = U1
T と U で、0 文字列と 1 文字列が一致した場合を復元してみる。
S = cabaacba
01100011
S0 = ca|ac
S1 = ab|ba
前半は0, 後半は1
前半は1, 後半は0
を合致するように塗り分ければ、解答を満たすのがわかる。
なので、
T と U について、2^4 を bit 全探索し、
出来上がった
U の pair<string0, string1> の組み合わせ数、
T の pair<string0, string1> の組み合わせ数をカウントアップすればいい。
T = abac
0000 = M[abac, ""]++
0001 = M[aba, c]++
0010 = M[abc, a]++
0011 = M[ab, ac]++
0100 = M[aac, b]++
...
U = acba
0000 = N[acba, ""]++
0001 = N[acb, a]++
0010 = N[aca, b]++
0011 = N[ac, ba]++
0100 = N[aba, c]++
...
4. 合致するものの積を加算。
ans += M[aba, c] * N[aba, c] // 1
ans += M[ac, ba] * N[ac, ba] // 2
ans += M[ba, ac] * N[ba, ac] // 3
ans += M[c, aba] * N[c, aba] // 4
ans = 4
実装
int main(){
cincout();
ll N;
string S, T1, T2;
cin >> N >> S;
// 半分だけ反転。
for(ll i=0, n=N-1; i<n; ++i, --n){
swap(S[i], S[n]);
}
// 半分ずつ
T1 = S.substr(0, N);
T2 = S.substr(N, N);
map<pair<string, string>, ll> M1,M2;
rep(i, (1LL<<N)){
string t, tt;
rep(j, N){
if (is_pop(i, j)) t += T1[j];
else tt += T1[j];
}
++M1[{t, tt}];
string s, ss;
rep(j, N){
if (is_pop(i, j)) s += T2[j];
else ss += T2[j];
}
++M2[{s, ss}];
}
ll ans = 0;
for(auto m: M1){
ans += m.second * M2[m.first];
}
cout << ans << endl;
}