AtCoder AGC #026 : C - String Coloring

こっちは本番５分で即答できてた。
https://beta.atcoder.jp/contests/agc026/tasks/agc026_c

問題

2N文字の文字列Sが与えられる。
これらの文字をN個ずつ赤と青で塗り分けたとする。
赤く塗った文字を左から読んだ場合と、青く塗った文字を右から読んだ場合に文字列が一致する塗り方は何通りか。

解法

半分全列挙で解く。
Sの前半分のうち、赤く塗る位置を2^N通り総当たりしよう。
この時、条件を満たすためには、Sの後ろ半分のうちSの前半分の赤文字数と同じ数だけ青文字を塗らなければならない。

よって、Sの前半分のうち、赤く塗る位置を2^N通り総当たりし、赤文字を左から、青文字を右から読んだものの登場回数を求め、次にSの後ろ半分のうち、青く塗る位置を2^N通り総当たりし、赤文字を左から、青文字を右から読んだものの登場回数を同様に求める。

前者の両文字列と、後者の両文字列の登場回数の積和を求めれば解。

int N;
string S;
map<pair<string,string>,int> L,R;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	for(int mask=0;mask<1<<N;mask++) {
		string a,b;
		FOR(i,N) {
			if(mask&(1<<i)) a+=S[i];
			else b+=S[i];
		}
		L[{a,b}]++;
	}
	ll ret=0;
	for(int mask=0;mask<1<<N;mask++) {
		string a,b;
		FOR(i,N) {
			if(mask&(1<<i)) a+=S[2*N-1-i];
			else b+=S[2*N-1-i];
		}
		ret+=L[{a,b}];
	}
	cout<<ret<<endl;
	
	
}

まとめ

前回のSoundHound～とこれが同じ600ptとは思えないな。
まぁコンテスト間で配点基準が同じではないなんて話もあるけど。