463.1

TopCoderの理念としては結構バランス良いセット。250は90%くらいで500は50%くらいで1000はどうでもいい、とかだった気がする。

250

N個の物体に識別番号を振るとき、それぞれに対して値を振っていい範囲が指定されている。何通りの振り方があるか答えよ、という問題。

取り敢えず範囲が小さい方からソートして、前のヤツまでで使っていないものだけ振れると思えばいいだけ。

500

見てない。

1000

ウサギが3匹、穴が3つという状態で、ウサギが他の一匹だけを飛び越えるという処理を延々と繰り返して、それぞれがどれかの穴に入るように仕向けるのは何通りのジャンプ方法があるか、という問題。

取り敢えず外側のウサギを移動させる方法は一通りで、できる限り内側に全部集める(もしくは指定されたステップ数試行する)。それが終わったら穴とウサギを逆だと思って、同様にウサギを真ん中に集める。これで状態が一致すれば(あるいは途中で同じステートに合流したら)答えがあることになる。後は使っていい余分のステップを適当に割り振る作業をする。

ウサギ状態Uと穴状態AがU[i]とA[j]で最初に合流したとすると、それらのステートだけでやりくりするのと、U[i+1]とA[j+1]を追加してやりくりするのと...という風にやれば、やりくりは真ん中のウサギが外に飛び出すような遷移だけ考えれば良いことになる。つまり、U[i]までa回遊んでから行くのと、A[j]までb回遊んでから行くのと(ゴールしてから遊んでもいいけど)、U[i+1]までc回遊んでから行くのと、A[j+1]までd回遊んでから行くのと...みたいにやればいいんじゃないかなぁ。