■ [SRM]SRM531 
http://community.topcoder.com/stat?c=coder_room_stats&rd=14724&rm=311335&cr=22744421
- 300
- 「全曲最低1度は使わないといけない」と「同じ曲はM曲以上離す」の両方の条件を考慮するのが難しそうだけど
- 後者が満たされるときにどういうことになるかよく考えてみたら、連続したM個の曲は全て異なる、ということに気づく
- なので、すでにA曲使っている状態の場合、次に未使用の曲を使う場合がN-A通り、すでに使っている曲を使う場合がA-M通り
- という感じになって、dp[現在何曲目か][これまで何曲使ったか] というDPができる
- 「A曲使っている状態」は、具体的にどの曲を使ったかは関係なくて何曲使ったかだけが重要で、それらは同一視して良いと気づくのも1つポイントかも
- 確率の問題で線形性を考慮するときとどこか似ている
- ここまではすぐ思いついたのだけど、変数の取り違えが多発してコーディングに時間がかかってしまった
- たった10行くらいのコードでも1文字変数はだめなものだなあ
- 500
- とりあえず、収束する場合は、Nターンシミュレーションすれば全ての通過しうるノードを通過するので十分なはず
- というわけで、収束するか発散するかを判定するのが本題
- 収束する場合は以下のケースに分かれる
- 1匹しか生まない経路のみを通って自分に帰ってくる
- 複数に分かれて、そのそれぞれが収束のループに入る
- 後者の判定は大変なので、ひとまず前者の簡単なやつを見つけてから、徐々に"収束するノード"を伝搬させていく
- 具体的には、収束性の判定をN個のノードそれぞれに対して行うのをN回繰り返す
- ベルマンフォードっぽく
- こうすることで、後者のパターンでもそのうち分岐先のノードの収束性がはっきりするので収束すると決定できる
- 1000
- 強い人が多数1000から開いていたが、なかなか解かれていないので無理そうだなあと思いつつ一応読む
- やっぱりすぐには何もわからないので閉じて500のテストをやる
- Challenge
- 300で二項係数を計算しようとしてオーバーフローしている人がいたので落とした
- System Test
- 300と500両方通った
- 500で落ちてる人が意外といなくて（4/7がPassed）なかなか優秀な部屋だった
- 264.51 + 319.46 + 0.00 + (50*1-25*0) = 633.97
- 20位/791人
- 2045->2172
自己最高順位。
volatilityがぐんぐん上がる
