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 個、赤いマーブルがバッグに残っています。
では、どうぞ!
public double winningChance(int red, int blue, int removed) {
...
}
ちなみに
になります。正しく解けたかどうかの検証用にどうぞ。
ちなみに、トップのひとは、この問題を 23 分で解いています。。。