[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;
}

https://atcoder.jp/contests/agc026/submissions/28633774