E - Throwing the Die

2023年苦手ジャンルがんばって埋めようシリーズ期待値編です。

問題

atcoder.jp

考えてたこと

サンプル2を導出するのに時間がかかって困った。ゲームも組み合わさってる用に見えてかなり時間がかかってしまった。
まずは容易に導出することができる。次のの期待値の求め方がしっくりこなかった。
・最初は出目によって場合分けしてたので、二ターン目以降も出目によって場合わけする？
・各ターンで前のターンの出目より大きい場合だけ列挙する？
・ターン毎に独立ならなんターン目でも* 出目になる？
・最初の出た目に書かわず次の期待値だけどあってるのか？
などなど
最初は出目によって場合分けして、その後の期待値は全部同じじゃん、そんなことある？みたいな気持ちなってた。

解法

だいぶ迷走してしまったが、問題を解くために必要を知識を整理しよう

• ゲームを続行するか終了するかを選択できる
• ゲームを終了する場合は、最後の出目だけがスコアに関係する。途中までのスコアは関係ない
• これをふまえるとスコアの期待値が最大になるように行動するとは、次の試行で今の期待値を超えそうなら続ければ良い。
• スコアの期待値自体は試行回数をNとするとになる。
• スコアが変わらないのに期待値だけ下がり続けるのが直感に反していて答えにたどり着けなかった。論理的に攻めよう

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int N; cin >> N;
    double ans = 3.5;
    
    for(int i = 1; i < N; ++i)
    {
        double tmp{};
        for(int j = 1; j <= 6; ++j)
        {
            tmp += max(static_cast<double>(j), ans);
        }
        tmp /= 6;
        ans = max(ans, tmp);
    }
    
    cout << setprecision(10) << fixed << ans << endl;
}