公式

H - Roulettes 解説 by MMNMM

まず、高橋くんの最適な戦略の中に、ある数列 \((A _ i) _ {i\in\mathbb N}\) によって「これまでの合計獲得ポイントが \(i\) のとき、次にプレイするルーレットは \(A _ i\) 番目のルーレットである」ようなものが存在することを示します。

証明 最適戦略において、\(e _ i\) をこれまでの合計獲得ポイントが \(i\) のとき、\(M\) ポイントに到達するまでに支払う金額の期待値と定めます（ただし、\(i\geq M\) については \(e _ i=0\) とします）。
いま、これまでの合計獲得ポイントが \(i\) のときに選びうるルーレットとして \(x _ 1,x _ 2,\ldots,x _ k\) 番目のものがあるとします。 ここから \(x _ i\) 番目のルーレットを選んだ場合に \(M\) ポイントに到達するまでに支払う金額の期待値は、 \[E _ {x _ i}=C _ {x _ i}+\dfrac 1{P _ {x _ i}}\sum _ {j=1} ^ {P _ {x _ i}}e _ {i + S _ {x _ i,j}}\] です。 ここで \(x\) は \(E _ x\) の昇順に並んでいるとして一般性を失いません。このとき、これまでの合計獲得ポイントが \(i\) のときに \(x _ 1\) のみを選ぶとしても損しないため、示されました。

以下、上の条件を満たす最適な戦略について考えます。

\(e _ i\coloneqq\) これまでの合計獲得ポイントが \(i\) のとき、\(M\) ポイントに到達するまでに支払う金額の期待値 を計算することを考えます（ただし、\(i\geq M\) については \(e _ i=0\) とします）。

\(i\) 番目のルーレットが出しうる目 \(P _ i\) 個のうち \(Z _ i\) 個が \(0\) であるとき、このルーレットの代わりに \(C _ i\dfrac{P _ i}{P _ i-Z _ i}\) 円払ってもとのルーレットから \(0\) の目を取り除いたようなルーレットを用いることにしても結果は変わりません。

説明 高橋くんの戦略のもとで \(i\) 番目のルーレットを回すなら、高橋くんは \(0\) でないポイントを得るまで同じ \(i\) 番目のルーレットを回し続けます。 現在のポイントのまま高橋くんがこのルーレットを回す回数の期待値は \(\dfrac{P _ i}{P _ i-Z _ i}\) 回で、このとき得られるポイントは、\(i\) 番目のルーレットで得られるポイントのうち \(0\) でないもののいずれかが一様ランダムに選ばれるため、上で述べたようなルーレットを使った場合と比べてかかるコストの期待値と得られるポイントの分布が変わりません。

よって、適切な前処理を行うことですべての \(S _ {i,j}\) が正であるとしてよいです。 すると、\(i=M-1,M-2,\ldots,1,0\) の順に \(e _ i\) を求めることができます。 具体的には、次のように \(e _ i\) を求めることができます。 \[e _ i=\min _ {j=1,2,\ldots,N}C _ j+\dfrac 1{P _ j}\sum _ {k=1} ^ {P _ j}e _ {i+S _ {j,k}}\] これの計算は \(1\) つの \(i\) あたり \(O(\sum _ jP _ j)\) 時間でできるため、全体で \(O(M\sum _ jP _ j)\) 時間で答えである \(e _ 0\) を求めることができます。

実装例は以下のようになります。

誤差について

まず、各 \(C _ i\) に誤差がない場合の計算について評価します。 \(e _ j\ (i\leq j\lt M)\) の計算結果に含まれる相対誤差のうち最大の値を \(\varepsilon _ i\) とします（便宜上 \(\varepsilon _ M=0\) とします）。

expected は \(e _ j\) をたかだか \(P\) 個足した結果です。 真の値を \(E\) として、これに含まれる絶対誤差は \(E(\varepsilon _ {i+1}+2 ^ {-52}(P-1))\) 以下です（double を用いて答えが \(k\ (k\geq1)\) になる四則演算を行うとき、たかだか \(2 ^ {-52}\) の相対誤差が生じます）。 これを \(P\) で割って \(C\) に加えているため、\(e _ i\) の計算結果に含まれる相対誤差は \(\varepsilon _ {i+1}(1+2 ^ {-52})+2 ^ {-52}(P+2)\) 以下です。 \(\varepsilon _ {i+1}\leq\varepsilon _ {i+1}(1+2 ^ {-52})+2 ^ {-52}(P+2)\) は明らかなので、 \(\varepsilon _ i\leq\varepsilon _ {i+1}(1+2 ^ {-52})+2 ^ {-52}(P+2)\) がいえます。

ここから、\(\varepsilon _ 0\leq((1+2 ^ {-52})^M-1)(P+2)\leq2.25\times10^{-12}\) となります。

ルーレットから \(0\) が出る場合の調整として \(C _ i\) にたかだか \(2 ^ {-52}\) の誤差が生じているため、実装例のプログラムによって計算された e[0] の値と真の値との誤差はたかだか \(2.5\times10^{-12}\) です。

出力の際に生じるたかだか \(5\times10^{-6}\) の相対誤差とあわせて、このプログラムで AC を得られることが示されました。

#include <iostream>
#include <vector>
#include <tuple>
#include <ranges>

int main() {
    using namespace std;

    unsigned N, M;
    cin >> N >> M;

    vector<tuple<double, unsigned, vector<unsigned>>> roulette(N);
    for (auto&&[C, P, S] : roulette) {
        cin >> C >> P;
        S = vector<unsigned>(P);
        for (auto &&s : S)cin >> s;
    }

    // 0 ポイントが出ないように調整
    for (auto&&[C, P, S] : roulette) {
        C *= P;
        erase(S, 0);
        P = size(S);
        C /= P;
    }

    vector<double> e(M, 10000 * M); // e[i] := 現在 i ポイントの状態からかかる金額の期待値
    for (const auto i : ranges::views::iota(0U, M) | ranges::views::reverse) // i の降順に計算
        for (const auto&[C, P, S] : roulette) {
            double expected = 0;
            for (const auto s : S | ranges::views::filter([i, M](auto s) { return i + s < M; }))
                expected += e[i + s]; // ルーレットをプレイしたあとにかかる金額の期待値

            e[i] = min(e[i], C + expected / P); // C + 1 / P ∑ e[i + s] の最小値が求める e[i]
        }

    cout << e[0] << endl; // e[0] が答え
    return 0;
}

投稿日時:
最終更新: