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; } }
まとめ
回文なので端から埋めていこう、と考えると手こずる。
場所はどこでも良くて、反対側に同じ文字がくればいいと考えると簡単。