SRM384 に挑戦。結果は、以下の通り。
今回は、500 点問題は正確に確率を求めようとすると、かなり面倒くさいです。何も考えずに、メモつき再帰などで計算しようとすると、「あれ、元の状態に戻ってしまうよ。延々とループしてしまうよね。これ?どーしよ。。」となってしまいます。 私は、これで 30 分くらい悩みました。
うまく場合分けをすれば正確に求めることも可能ですが、そうではなく、強引にシミュレーション(?)で求めてしまうって方法が、一番楽だったようです。ちなみに、このような強引に一定回数ループを回して計算する方法って、なにか名前がついていないんですかね ? シミュレーションって言葉も、ちょっと正しくないような気もするんですけど。
1000 点問題は、ゲームの問題です。ひとつひとつのゲームの結果を求めるのは簡単なんですが、それが複数組み合わさるときの求めかたがわかりませんでした。「なんらかの、Nim のようなゲームの考え方に落ち着くんだろうな。」とは思ってたんですけど。
TopCoder の Forum によりますと、このような複合ゲームの場合の考え方は、以下の論文 (TopCoder のメンバーである raso6sk の学士論文)が参考になります。
http://www.fmph.uniba.sk/fileadmin/user_upload/editors/studium/svk/2007/INF/lenhardt.pdf
しかし、この 1000 点問題を解いた人は、24 人もいるんですよね。みんな、よく知ってますね。さすが。