SRM349 に挑戦。

今回は、1000 点問題が、なかなかいい問題でした。 Division1 の人達の多くを見事にひっかけた良問です。超絶アルゴリズムが必要なわけではなく、最初にちょっとしたアイデアに気付くかどうかで、十分に解ける問題と化すという、素晴らしい問題だなと。

世間では FizzBuzz 問題がはやっていたようですが、それに飽きたという方は、この 1000 点問題 「 赤いマーブル問題 」に挑戦してみてください。

中が見えないバッグに、赤いマーブルが red 個、青いマーブルが blue 個、入ってい ます。あなた(A 君)と相手(B 君)は、交互に、バッグから 1 個、あるいは 2 個、ある いは 3 個のマーブルをまとめて取り出します。取り出したマーブルの色は自分だけで なく相手にも教えてあげます。このように交互にマーブルを 1 個から 3 個ずつ取り出 していき、バッグに入っている最後の(ラスト一個の)赤いマーブルを取り出した人が負 けになります。

それでは、ゲームスタートです。といいたいところですが、ここで第 3 者(C 君)が現 れて、ゲームをはじめる前に、バッグからマーブルを、ランダムに removed 個、取り 出してしまいました。 A 君も B 君も、取り出された removed 個のマーブルがそれぞ れ何色だったかは教えてもらえませんでした。

この状態からゲームはスタートします。すなわち、A 君と B 君は、もともとの赤いマ ーブル, 青いマーブルの個数と, C 君が取り出した個数は知っていますが、 現在のバ ッグについては、(red + blue - removed)個のマーブルが入っていることがわかってい るだけで、どの色がそれぞれ何個入っているかはわかっていません。

ゲームスタート。最初に取り出しのはあなた(A 君)からです。お互いが最適な戦略をと る場合、あなたが勝つ確率はいくつになるでしょうか?

という問題です。

red, blue, removed は、以下の条件を満たすものとします。

• 1<= red <= 100
• 1<= blue <= 100
• removed < red

つまり、ゲーム開始時は、少なくとも 1 個、赤いマーブルがバッグに残っています。

では、どうぞ!

public double winningChance(int red, int blue, int removed) {
    ...
}

ちなみに

• red=1, blue=1, removed=0 の場合は、答えは、0.5
• red=1, blue=2, removed=0 の場合は、答えは、0.33333333333333...
• red=2, blue=1, removed=1 の場合は、答えは、0.5
• red=100, blue=1, removed=99 の場合は、答えは、0.9900990099009901...
• red=100, blue=100, removed=50 の場合は、答えは、0.5379240275007613...

になります。正しく解けたかどうかの検証用にどうぞ。

ちなみに、トップのひとは、この問題を 23 分で解いています。。。