kmjp's blog

競技プログラミング参加記です

TopCoder SRM 625 Div1 Easy PalindromePermutations

2連続Mediumを凡ミスで落とすという残念な結果。
Easyを早めに解けているのでなんとかレートは微増しているのだけど。
http://community.topcoder.com/stat?c=problem_statement&pm=11856

問題

L文字の文字列Sが与えられる。
この文字列をランダムに等確率で並べ替えたとき、回文になる確率を求めよ。

解法

まずSにおける各文字cの登場回数P[c]をカウントしておく。
この時以下を満たさないなら回文にならないならそもそも確率は0。

  • 文字列長が偶数なら、全ての文字は偶数回登場する。
  • 文字列長が奇数なら、奇数回登場する文字c'は1個だけ。
    • この場合、並べ替え後の文字列の中央はc'でないといけないので、先にそれを計算しておく。
    • c'が中央に来る確率はc'/Lなので、最終的な答えにこの値を掛ける。また、後の処理を行う前にP[c']とLをデクリメントしておく。

後は文字cごとに以下の処理を行う。

  • まだP[c]が残っているなら、そのうち1つがどこかに置かれた場合、回文上それに対応した位置に同じ文字が来ないといけないので、(P[c]-1)/(L-1)を答えに掛け、P[c]とLをデクリメントする。
class PalindromePermutations {
	public:
	double palindromeProbability(string word) {
		int L=word.size(),i,x,y;
		int num[26],od=0;
		ZERO(num);
		FOR(i,L) num[word[i]-'a']++;
		FOR(i,26) if(num[i]%2) od++;
		if(od!=L%2) return 0;
		double ret=1;
		if(od) {
			FOR(i,26) if(num[i]%2) {
				ret = num[i]/(double)L;
				num[i]--;
				L--;
				break;
			}
		}
		FOR(i,26) {
			while(num[i]) {
				ret *= (num[i]-1)/(double)(L-1);
				num[i]-=2;
				L-=2;
			}
		}
		return ret;
	}
}

まとめ

回文なので端から埋めていこう、と考えると手こずる。
場所はどこでも良くて、反対側に同じ文字がくればいいと考えると簡単。