AGC026-C「String Coloring」



- [問題URL](https://beta.atcoder.jp/contests/agc026/tasks/agc026_c)



# 考察

## コンテスト中の考察

- うーん、なにもわからんからとりま全列挙書くか
- DFS書いたけどなんかバグるからbit全探索書く！！
- さて、計算量が$O(2^{2N})$になるわけだがどうしようかー。
- $O(2^{N})$なら間に合うんだけどなー...
- 探索範囲を絞る奴かも知れない！！赤$N$文字で青$N$文字のパターンしか無いのでは？（アホ）
- 書いたけどなんか遅いぞ...計算量は$O(_{2N} C_N )$くらいか？来世に期待しましょう。
- この後、規則性をがんばって見つけようとするも解けず...にゃーん...
- この考察ぐちゃぐちゃ過ぎてもうダメ...



## 理想の考察

### 方針の考察

- 全探索は$2^{2N}$で間に合わない($N \leq18$)
- なので、法則性を見つけるために考察したり実験してみる。
- 考察しようとするが、解くに何も思いつかないので全探索を書いて実験してみる。
- 全探索によって実験し、法則性を見つけようとしたが見つからない...
- やはりある程度探索する必要がありそう。
- ただ、$2^{2N}$は間に合わない。だが。$2^{N}$くらいなら間に合う
- 長さ$N$の探索、つまり文字列の長さの半分の探索のみでなにかできないかを考えてみる
- とりあえず入力例1を前後半分に切り分けてみる。
- すると、法則性が見えてくる。入力例1について図にすると以下のようになる。ここでは、前半の赤文字列をR、前半の青文字列をB、条件を満たす文字列をSとしている。

<img width="300" alt="strColor.png" src="https://qiita-image-store.s3.amazonaws.com/0/218584/c5a4a929-eadc-9e3c-437f-399e98ce47c4.png">


- 上図から、$R+反転B=S$となることが分かる。
- ただ、このケースだけ偶然そうなるのかもしれない。なので、ちょっとした証明が欲しい。
- 僕の実力的に早解きする必要は無いからちょっとした証明を考えてみることにする。

<img width="450" alt="strColor2.png" src="https://qiita-image-store.s3.amazonaws.com/0/218584/27d39ae9-522e-fffd-5c66-faaa8a5cc0a2.png">


- 上図は、前半部分からSを求めることができることを表している。
- 例えば、一番上のケースについて、赤は`c???`。逆青は`?aba`となっている。
  - 前半の情報だけで考えるため、`?`は未知の文字である。
  - ここで、問題の条件より「赤文字列＝逆青文字列」である事を思い出す。
  - すると、`c???=?aba`という等式が得られる。
  - そして、この等式からSが`caba`である事が分かる。
  - 他の例に関してもこれが言える。
  - よって、前半部分のみでSを求められることが証明できた。

- 以上より、$R+反転B=S$となるのは大体あってそうだと分かる。
- これで方針の考察はおしまい！



### 実装の考察

- 大体の考察が終わったところで、実装に移る。
- 流れとしては、前半全列挙→後半全列挙となる。
- 前半の組み合わせと後半の組み合わせを考慮して計算するため、組み合わせを考える。
- 組み合わせは以下の画像のようになっていれば良い

<img width="300" alt="strColor3.png" src="https://qiita-image-store.s3.amazonaws.com/0/218584/958dc9ac-7ad8-ec37-40fd-19dc0d35ecf2.png">


- つまり、前半のペアが｛R, B｝で後半のペアが｛反転B, 反転R｝となっている組み合わせの数を求めれば良い。
- 前半で求めた組み合わせは、文字列の後半を全列挙するときに使う。
- なので、組み合わせは`map`で保存しておく。組み合わせの種類だけで無く、組み合わせの個数も必要だから`map`を使う方が都合が良い。
- 前半の全列挙の後は、後半を全列挙する。
- 後半の全列挙の結果は、前半に作った`map`と照合して計算する。
- これで実装の考察もおしまい！



## 解法

1. 文字列の前半を全列挙する。
   - このとき、`map`でデータを管理する。
   - 文字列の組み合わせをキー、その組み合わせの個数を値とする。
2. 文字列の後半を全列挙する
   - 前半の全列挙した結果を用いて計算する。

- 計算量はだいたい$O(N\times 2^{N}) $となる。




## [コード](https://beta.atcoder.jp/contests/agc026/submissions/2855280) 

```cpp
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pss = pair<string, string>;

int n;
string s;
map<pss, int> mp;

int main() {
   cin >> n >> s;

   // 前半部分の組み合わせを全列挙
   for (int mask = 0; mask < (1<<n); mask++) {
      string R = "", B = "";
      for (int i = 0; i < n; i++) {
         if (mask & (1<<i)) {
            R.push_back(s[i]);
         } else {
            B.push_back(s[i]);
         }
      }
      mp[{R, B}]++;
   }

   // 後半部分の組み合わせを全列挙
   ll ans = 0;
   for (int mask = 0; mask < (1<<n); mask++) {
      string R = "", B = "";
      for (int i = 0; i < n; i++) {
         if (mask & (1<<i)) {
            R.push_back(s[n+i]);
         } else {
            B.push_back(s[n+i]);
         }
      }
      reverse(R.begin(), R.end());
      reverse(B.begin(), B.end());
      ans += mp[{B, R}];
   }

   cout << ans << endl;

   return 0;
}
```

- もう少し簡潔に書くこともできる。
- だが、考察通りにコードを書かないと頭が爆発する...




## 要点

- **部分を求めることで、それ以外の部分を確定させる**という発想。
  - この発想は計算量を落とすために結構使う気がする。
  - 今回の場合、文字列の半分が探索できれば全体の情報も分かることに気がつけると良かった。
  - ただ、$R+反転B=S$だと気づくには少し時間がかかりそう
- 半分全列挙は$O(2^N)$を$O(2^\frac{N}{2})$にできるということ
  - ただ、半分全列挙＋他のアルゴリズムを組み合わせる場合が多いらしい？
  - 今回の場合は「半分全列挙＋連想配列」の組み合わせだった。
- 前半と後半が独立していることに気がつく
  - 独立していることに気がつくと、余計なことを考えなくてすむので考察が楽になる。
  - 今回の場合、前半の選び方と後半の選び方は独立していることに気がつけば良かった。





## 感想

- これ数分で通せた人なんなんだ？神か？
- まあ、半分全列挙を知れたのは良かった
- なにげに初めて600通した気がする。
- 理論は理解できたが、まだ少しモヤモヤする。寝かせれば解決する...?