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

問題

問題概要

文字列の中で最も左のもの、またはもっとも右の文字を任意の順番で取り出していき、取り出した順番で並べる。何種類の文字列が作れるか。

解法

全探索する。左または右から取る順番をbitを用いて実装した。今回はbit列iのpos番目のbitが立っていれば、左側から文字を取る出し、立っていなければ、右側から取り出すようにした。全探索するためにiを(1 << s.size())の分だけ回した。また重複した文字をカウントしないためにはsetを使えばいい。

ミス

特になし。

コード

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cstring>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

//ビット列iの中で、posビット目が立っているか判定
bool contain(int i, int pos){
    if(i & (1 << pos)) return true;
    else return false;
}

int main(void){
    string s; cin >> s;
    set<string> ans;
    int size = s.size();
    for (int i = 0; i < (1 << size); ++i){
        string ss = s;
        string tmp;
        for (int pos = 0; pos < size; ++pos){
            if(contain(i, pos)){//左側から文字を取る
                tmp += ss[0];
                ss.erase(ss.begin());
            }else{//右側から文字を取る
                tmp += ss[ss.size() - 1];
                ss.erase(ss.end() - 1);
            }
        }
        ans.insert(tmp);
    }
    cout << ans.size();
}