TopCoder SRM531

300

N曲あって、P曲分の長さのプレイリストを作る。プレイリストには各曲1回以上含まれねばならず、また同じ曲を流す場合は間にM曲以上他の曲がないといけない。何通りのプレイリストが存在するかmodで計算せよ。

見た瞬間「うげっ」ってなったが「各曲1回以上」の部分がなければ自明(先頭から順にプレイリストを構成するとき、各場所では前M箇所に出てきた曲以外を使うことができ、前M箇所の曲も互いに異なるので、その場所に使える曲の数は自然と定まる)
全部使わなくてもいい場合の数が求まれば、包除原理っぽくして求める場合の数も求められる。
ただし、div2medium(600)もこの問題で、div2midにしては明らかに難しすぎる

500

何らかの生物があり、いくつかの種類がある。それぞれの生物は、毎晩種類ごとに定められた1個以上の別な生物に変わる。最初に種類1の生物が1体あるとき、最終的には何体の生物が存在するかmodで/無限に発散するか求めよ。

まず、個数を増やさない変化を繰り返して自分に戻ってくるような種類については収束することが明らかである。さらに、他の収束するものだけを生み出すような種類についても収束が明らかである。この2つによって定義されない種類は発散する。
シミュレートして一定になったらやめるという戦略をとる人がいたらしいが、適切に実装しないと答えがmod値の倍数でどんどん増えていく場合に対処できないらしい。

1000

1列に並んだビル列があり、そのうちの2つを取り壊す。取り壊しは次の手順で行われる。1. どちらかの取り壊すビルの最上階を地上に下ろす。 2. 地上に下ろした階を移転先ビル(取り壊すビル以外のどれか)の手前に動かす。 3. 移転先ビルの最上部にその階を移す。4. 取り壊すビルがなくなるまで続ける。コストは、縦の移動は1階につき上下問わず1、横の移動はビル1マス分につきcostかかる。コストの最小値をもとめよ。

よくわからない

結果

oox 719.38 10位
rating: 2199 -> 2350