yukicoder No.52 よくある文字列の問題 解説

問題文

解説

まずは、制約を見てみよう。すると$N\leqq 10$と書いてある。
これを見ると大分bit全探索とかが怪しくなるため、bit全探索が使えるか考えてみる。
ここで、$S$を操作してできた文字列を$T$とする。
今回$T$にpushする方法は$S$の先頭または$S$の末尾。つまり $2$通りある。よってbit全探索の問題だと確定した。
bitの0,1を次のように仮定する。
・bit=0 → $S$の先頭をpushする。
・bit=1 → $S$の末尾をpushする。
こんな感じで$T$を生成していく。
何種類できるかの重複管理はsetを使うのがおすすめ。
こんな感じで操作を行っていき、最終的なsetのサイズを出力すればOK。
実行時間は$O(2^NN)$。
bitによる管理は$S$の何文字目まで行ったかを管理する変数を用いると実装が楽。

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

int main() {
  string s;cin>>s;
  int n=s.size();
  set<string> ans;
  for(int i=0;i<(1<<n);i++){
    bitset<10> bit(i);
    //lおよびrはSのそれぞれ何か所目まで探索したかを表す。
    string t="";int l=0,r=n-1;
    for(int j=0;j<n;j++){
      if(!bit[j]){
        t.push_back(s[l]);
        l++;
      }
      else{
        t.push_back(s[r]);
        r--;
      }
    }
    ans.insert(t);
  }
  cout<<ans.size()<<endl;
}