TopCoder SRM 531 Div1
大敗北。
Result
Challenged / Opened / Unopened
398位 2097 -> 1960
Easy NoRepeatPlaylist
問題
N曲の曲からP曲を重複を許して、以下の条件を満たすよう選ぶ。
選び方は何通りあるか、mod 10^9 + 7で求めよ。
条件:
全ての曲が少なくとも一度以上選ばれる。
同じ曲は間に少なくともM曲のほかの曲を挟む。
制約条件
N,P,M≦100
試行錯誤
300点問題。
てかぱっと見なんか凄い苦手系統の問題に見えるんだけど。
少なくとも一度以上っていう条件どうするんだよ。
しかも間にM曲ほかの曲をはさむとか。
数十分考える。
包除原理だろうか。
全ての曲を一度以上選ばなくてもいいという条件があったら、
場合の数はN*(N-1)*(N-2)*……*(N-M)*(N-M)*(N-M)*…*(N-M)となるはずで。
うーん、N曲を一度以上選ぶ場合と、N-1曲を一度以上以上選ぶ場合と……
と部分集合になっているから包除原理でいける?
あ、いや、ボトムアップに、
1曲だけからなる場合と2曲だけからなる場合と……と計算していけば、
ちょうどk曲からなる場合の場合の数が求まる。
DPか。
書いた。おおすげえサンプルあった。
確認して送信。
もう時間ない。
残り15分。凄く萎えたので不貞寝。
System Test
300M≧Pの場合がコーナーケースになって落ちてるし。
年末年始にかけて猛練習したのに、ためたレートを一気に失った。
もうやだ。ひどい。
苦手っぽい300が一応自力で(コーナーケースの部分以外)解けたことはレベルアップしたとみていいんだろうか。