hotpepsiの練習帳

SRM 625

23:03

Div1 Easy (250) PalindromePermutations

問題

• 文字列が与えられる
• 文字列をランダムに並べ替えて、左右対称になる確率を求める

方針

• 文字列の長さLが偶数のとき、奇数個の文字があるなら確率ゼロ
• 文字列の長さLが奇数のとき、奇数個の文字がひとつでないなら確率ゼロ
• 対称になる並べ方は、半分の全部の並べ方なので、(L/2)!通り
• 全体はL!通りなので、確率は(L/2)!÷L!
• 同じ文字があるときは、S個あったらS!通りの並べ方が重複
• 分子を(S/2)!で、分母をS!で割っていく
• 誤差死対策として、乗数または除数をカウンタで持っておいて、ひとつずつ乗除算する
• Failed System Test
• 奇数のときの扱いが間違っていた
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_625/PalindromePermutations.cpp

結果

x-- +1 50pts 504th/717 rating 1573 -> 1522 (-51)

2項係数でやると死ぬのはわかっていたのだがチャレンジできず。

方針は合っていたが、サンプルが通る誤答を直すのは時間がかかる。

http://togetter.com/li/682240