mayoko’s diary

プロコンとかいろいろ。

SRM 695 div1 hard BearEmptyCoin

問題

TopCoder Statistics - Problem Statement

あなたは K 回コインを投げるゲームをする。コインは表裏がそれぞれ 1/2 の確率で出る。ルールは以下のとおりである。

  • コインを投げてまだ何も書いてない面が出たら, その面に好きな数字を書く。
  • 出た面に書かれている数をスコアに加える。
  • これを K 回繰り返して, スコアの合計が S になったら勝ち。そうでなかったら負け。

あなたは最適な戦略をすることで勝率を最大化したい。この勝率は A/2^K という形になるが, この A を求めよ。

解法

本番 med を捨ててこれを考えていたので気になって AC してた人の解答を読んでたらなんとなくわかったので書こうと思います。

まず, S%K == 0 の場合, 両面に S/K を書けば必ず勝つので答えは 2^K です。

これ以外の場合, 少なくとも両面が出ないことには絶対に勝てません(そうしないと K の倍数になるしかないので)。そこで, 最初に書く数を X, 別の数を Y とし, 表の出る回数を A とすると,

A*X + (K-A)*Y = S

となる必要があります。ここで, gcd(A, K-A) が S で割り切れないと, スコアが S になることはありません(A*X + (K-A)*Y は X, Y を好きに取れたとしても gcd(A, K-A) の倍数になるしかない)。

逆に, gcd(A, K-A) が S で割り切れると, ある X, Y が存在して, A*X + (K-A)*Y = S となります。この式を変形すると,

K*Y + A*(X-Y) = S
どうせ X, Y は自由に選べるので, Z = X-Y と Y が自由に選べるのと同じです。つまり,
K*Y + A*Z = S
ちょっと整理するために Y と Z を入れ替えると
K*Z + A*Y = S
となります。最初にうまく Z を選んでやると, gcd(A, K-A) が S で割り切れるような任意の A について, K*Z + A*Y = S が成りたつ, ということが言いたいです。

が, これは一般的な中国人剰余定理により, Z の存在は保証されています。今回の場合は, gcd(A, K-A) が S で割り切れるような任意の A について, S-K*Z の mod A が 0 であるようなものがあれば良いわけですが, この存在は保証されています。
mathtrain.jp

よって, 考えるべきことは,

  • 2 つ目の値を決めるべきタイミングが, 残り何回コインを投げれる時に来たか(残り i 回とする)で場合分け
  • 1 つ目と 2 つ目の値を何回ずつ配分するのが最適かを考えると, 残り i-1 回中 j-1 回 2 回目の値が来るようにする確率は (comb[i-1][j-1] / 2^K)

ということだけです。

ll comb[66][66];
bool ok[66];

class BearEmptyCoin {
public:
    long long winProbability(int K, int S) {
        if (S%K == 0) return 1ll<<K;
        for (int i = 0; i < 66; i++) {
            comb[i][0] = 1;
            for (int j = 1; j <= i; j++)
                comb[i][j] = comb[i-1][j-1] + comb[i-1][j]; 
        }
        S = abs(S);
        memset(ok, false, sizeof(ok));
        for (int i = 1; i < K; i++) {
            int tmp = __gcd(i, K);
            ok[i] = (S%tmp == 0);
        }
        ll ans = 0;
        // 決断すべきところで場合分け
        // 残り回数が i の時に出たらあと振る回数は i-1
        for (int i = 1; i < K; i++) {
            ll tmp = 0;
            for (int j = 1; j <= i; j++) if (ok[j]) {
                tmp = max(tmp, comb[i-1][j-1]);
            }
            ans += tmp;
        }
        return 2*ans;
    }
};