Rabbit Game Playing (AOJ 2383)

AOJ Online Judge

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2383

問題

ステージがN個ある。全てのステージをプレイしたいのだが、以前クリアしたステージの難易度-Tよりも簡単なステージはプレイできない。ステージの並べ方は何通りか？
1<=N,T<=10,000

解法

ステージを簡単な順にソートしておく。ステージiまで並べた時に、ステージi+1を挿入する位置を考える。挿入する位置はそのステージの難易度-T以上の難易度の番号がi未満のステージの個数+1となる。あとは順に計算するだけ。