足跡-sokuseki-

りかの日進月歩の記録

数学が苦手な人のための期待値DP AtCoder 第一回PAST O - 持久戦

期待値が苦手すぎるので解説を自分が理解できる粒度まで噛み砕いて書きました。

解法


dp[i] := 直前にiを出したときの残りの回数の期待値とすると
dp[max_number]は1であり、dp[0](サイコロを1度も振っていないとき)が求める値となる。
dp[i] を求める際には  i < j なるdp[j] がわかっていればよいため、 i の降順に計算する。
 i >= j のとき、出目  i のあとに出目  j を出すと操作が終了となり期待値は0なので)


サイコロの出目は 10^9までであるが、出目の個数は高々  6N <= 1.8 \times 10^5 なので、座圧すると配列としてもつことができる。


出目がa_1,a_2,a_3,a_4,a_5,a_6のサイコロを振るとき、出目は a_1,a_2,a_3,a_4,a_5,a_6の6通りあり、それぞれ等確率なので、
期待値は([次にa1を出したときの残りの期待値] + dp[次にa2を出したときの残りの期待値] + dp[次にa3を出したときの残りの期待値] + dp[次にa4を出したときの残りの期待値] + dp[次にa5を出したときの残りの期待値] + dp[次にa6を出したときの残りの期待値])/6に今から振る1回を足した値になる。



サイコロが1つしかない場合、目を a_1,a_2,a_3,a_4,a_5,a_6(a_i < a_{i+1})とすると dp[a6] = 1

dp[5] は、a_1 から  a_5が出ると操作が終了(期待値0)で、a_6が出ると操作は終了しないので、
期待値はdp[a5] = (0 + 0 + 0 + 0 + 0 + dp[a6])/6 + 1

dp[a4]は、 a_1 から   a_4 が出ると操作が終了で、 a_5, a_6 が出ると操作は終了しないので、
期待値はdp[a4] = (0 + 0 + 0 + 0 + dp[a5] + dp[a6])/6 + 1

同様に、
dp[a3] = (0 + 0 + 0 + dp[a4] + dp[a5] + dp[a6])/6 + 1
dp[a2] = (0 + 0 + dp[a3] + dp[a4] + dp[a5] + dp[a6])/6 + 1
dp[a1] = (0 + dp[a2] + dp[a3] + dp[a4] + dp[a5] + dp[a6])/6 + 1
dp[0] = (dp[a1] + dp[a2] + dp[a3] + dp[a4] + dp[a5] + dp[a6])/6 + 1



サイコロが2つ以上あるとき、直前に  i を出した後、次に振ることができるサイコロは2つある。
どちらのサイコロを振るかは選択できるので、期待値がより大きくなる方を選べば良い。
つまり、
1つ目のサイコロを(  a_1,a_2,a_3,a_4,a_5,a_6 )、2つ目のサイコロを(  b_1,b_2,b_3,b_4,b_5,b_6 )とすると
(dp[a1] + dp[a2] + dp[a3] + dp[a4] + dp[a5] + dp[a6])/6 + 1
(dp[b1] + dp[b2] + dp[b3] + dp[b4] + dp[b5] + dp[b6])/6 + 1 の大きい方をdp[i]の値とすればよい。



サイコロが3つ以上のときも同様で、dp[i]はその時点でのすべてのサイコロの期待値のmaxを代入すればよい。



よって、すべてのdp[i]について、 N 個のサイコロの期待値のmaxを計算していけばよいので、
愚直にやると O(N^2) となる。

ここで、 j 番目のサイコロを振ったときの残り回数の期待値をexp[j]とする。
exp[j]は、直前に出した目の値によって変わり、直前に  i を出したときは
 k  i < k をみたすサイコロ  j の出目として exp[j] = sum(dp[k])/6と表記できる。
すべてのサイコロについてexp[j]を適切に計算してあげると、
dp[i]の計算はmax(exp[j])+1で良い。
exp[j]の更新は、dp[i]の計算が終わった後、サイコロ  j に出目  i が含まれている場合、exp[j] += dp[i]/6をする。

max_exp = max(exp[j])という変数を作り、exp[j]が更新されるたびにmax_expを計算し直すことにすると、dp[i] = max_exp + 1と書くことができる。



まとめると、サイコロの出目を座圧し、dp[i] i の降順に計算していきながら、出目  i があるサイコロ  j exp[j]max_expを更新していけばよい。
exp[j]の更新は高々  6N 回で、事前に出目  i があるサイコロを  O(1) で調べられるように配列に入れて管理しておけば、dpテーブルの計算量は  O(N) である。

コード

mainのみ

signed main(void) {
    int n;
    cin >> n;
    vector<vector<int> >  a(n,vector<int>(6));
    vector<int> num;//座圧用配列
    rep(i,n)rep(j,6){
        cin >> a[i][j];
        num.push_back(a[i][j]);
    }

    //座圧
    sort(all(num));
    num.erase(unique(all(num)),num.end());

    int max_number = num.size();
    vector<vector<int> > dice(max_number+1);//dice[i]:=出目がiのサイコロのindex
    rep(i,n)rep(j,6){
        int ind = lower_bound(all(num),a[i][j]) - num.begin();//座圧後のindex
        dice[ind+1].push_back(i);//1-indexedにする
    }

    vector<double> dp(max_number+1,0),exp(n,0);
    double max_exp = 0;
    for(int i = max_number; i >= 0; i--){
        dp[i] = max_exp + 1;
        rep(j,dice[i].size()){
            //サイコロdice[i][j]に出目iが書かれている
            exp[dice[i][j]] += dp[i]/6.0;
            max_exp = max(max_exp, exp[dice[i][j]]);
        }
    }

    cout << shosu(10) << dp[0] << endl;
}

https://atcoder.jp/contests/past201912-open/submissions/12285583