Hatena::Grouptopcoder

hotpepsiの練習帳

2014-06-23

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

ゲスト



トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20140623