TopCoder SRM 756 Div1 Medium CrazyCrazy

これ本番出てたら思いつけたかなぁ…？
https://community.topcoder.com/stat?c=problem_statement&pm=15408

問題

N文字の文字列Sが与えられる。
Sを２つの文字列A,Bに分割することを考える。
A=BかつAのi文字目をSから取り出す位置が、Bのi文字目を取り出す位置より前にできるようにできるか判定せよ。

解法

Nが40なので、半分全列挙しよう。
前半分について、Aに割り当てる位置とBに割り当てる位置を2^(N/2)通り総当たりする。
そして各組合せについて、条件を満たすか判定しよう。
Aに割り当てる文字が超過する場合、そのような余った文字列をsetなどで覚えておこう。

後ろ半分についても同様に2^(N/2)通り総当たりする。
この際、後ろから順に見ていって、B[i]がA[i]に先行するか判定していこう。
こちらもBに割り当てる文字が超過するが、その文字列を反転し、先ほどのset内に同じものがあるか判定すればよい。

class CrazyCrazy {
	public:
	string possible(string song) {
		int N=song.size();
		
		int mask;
		set<string> S;
		int i;
		
		FOR(mask,1<<(N/2)) {
			queue<char> Q;
			FOR(i,N/2) {
				if(mask&(1<<i)) {
					Q.push(song[i]);
				}
				else {
					if(Q.empty()) break;
					if(Q.front()!=song[i]) break;
					Q.pop();
				}
			}
			if(i==N/2) {
				string s;
				while(Q.size()) s.push_back(Q.front()),Q.pop();
				S.insert(s);
			}
		}
		reverse(ALL(song));
		FOR(mask,1<<(N/2)) {
			queue<char> Q;
			FOR(i,N/2) {
				if(mask&(1<<i)) {
					Q.push(song[i]);
				}
				else {
					if(Q.empty()) break;
					if(Q.front()!=song[i]) break;
					Q.pop();
				}
			}
			if(i==N/2) {
				string s;
				while(Q.size()) s.push_back(Q.front()),Q.pop();
				reverse(ALL(s));
				if(S.count(s)) return "possible";
			}
		}
		return "impossible";
		
		
	}
}

まとめ

半分全列挙久しぶりかも。