AtCoder AGC 026 C - String Coloring (青色, 600 点) - けんちょんの競プロ精進記録

なんかこれは TL で「 $N \le 18$ という制約が意味するものは...！？」という感じの TL を先に見てしまった。。。
とはいえ確かに半分全列挙一択ではあるか...

問題へのリンク

問題概要 (AGC 026 C)

長さ $2N$ の、英小文字のみからなる文字列 $S$ が与えられる。
$S$ の各文字を赤色か青色かに塗り分ける $2^{2N}$ 通りの方法のうち、

赤色に塗られた文字を左から右に読んだ文字列と，青色に塗られた文字を右から左に読んだ文字列が一致する

という条件を満たす塗り分け方は何通りか？

制約

$1 \le N \le 18$

考えたこと

$O(2^{n})$ みたいなやつを減らすテクの 1 つとして半分全列挙による $O(n 2^{\frac{n}{2}})$ にする的なのはよく見かける。ナップサック問題をその計算量で解ける的な話は有名だったり。

今回もそういう方向でエスパーすると自然に解法が浮かぶ。文字列を前と後ろに分けて考えるわけだが、考えやすくするためにちょっと問題を同型変形してみる。

前に塗るやつは赤と青を入れ替える
後ろに塗るやつは赤部分と青部分とでそれぞれ左右反転させておく

とすると例えば

c(赤)  a(青)  b(青)  a(赤)  a(青)  c(青)  b(赤)  a(赤)
↓
c(青)  a(赤)  b(赤)  a(青)  c(青)  a(青)  a(赤)  b(赤)

という感じになり、このような変換を施した世界においては

前と後ろとで、赤部分の文字列と青部分の文字列とがそれぞれ等しくなるような塗り方は何通りか？

という問題になる。こうなるとかなり考えやすくなり、

後ろ文字列から得られる (赤文字列, 青文字列) として考えられるペアを全列挙しておく (重複あり)
前文字列から得られる (赤文字列, 青文字列) それぞれについて、それが後ろに何個含まれるかを加算していく

という感じのオーソドックスな半分全列挙の枠組みで解ける。計算量は map を使うと $O(n^{2}2^{n})$ で、unordered_map を使うと $O(n2^{n})$ になりそう...？？

#include <iostream>
#include <string>
#include <map>
#include <algorithm>
using namespace std;

int main() {
  int N;
  string S;
  cin >> N >> S;
  string mae = S.substr(0, N), ushi = S.substr(N, N);

  // 後ろ文字列たちから得られる反転ペアたちを作っておく
  map<pair<string,string>, long long > ma;
  for (int bit = 0; bit < (1<<N); ++bit) {
    string a = "", b = "";
    for (int i = 0; i < N; ++i) {
      if (bit & (1<<i)) a += ushi[i];
      else b += ushi[i];
    }
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    auto p = make_pair(a, b);
    ++ma[p];
  }

  // 前半文字列から作られるペアが後ろにもあるかどうかを判定する
  long long res = 0;
  for (int bit = 0; bit < (1<<N); ++bit) {
    string a = "", b = "";
    for (int i = 0; i < N; ++i) {
      if (bit & (1<<i)) a += mae[i];
      else b += mae[i];
    }
    auto p = make_pair(a, b);
    res += ma[p];
  }

  cout << res << endl;
}