B - せんべい AtCoder Regular Contest 055

問題概略
長さNの順列があり、一枚ずつ順に渡される。
自分は具体的な数字を知ることは出来ないが、選ぶ前に今までの中で最大かどうかを知ることが出来る。
K回選べるとして、最適な行動をした時に最大の数を選べる確率を求めよ。

解法
状態があまりないので、DPを使いたい。
memo[i][k] := i個目を見ていて後k回選べる時に最適な行動をした時に、勝つ確率。
最低限の戦略について考えると、大きくない数は選ぶ必要がない。
よって[i][k]について２つの選択が出来る
・数が大きければ選び、小さければ選ばない。（2つあるのが不自然に感じるかも知れないが、後者は何もしないという意味なので問題ない）
・数の大小に関わらず選ばない。

１つ目の期待値について考えるため、そもそも今までよりも大きい数が出る確率を知りたい。
結論から言うと、i枚目を見ている時 1/i で出る。

より大きい数が出る確率をbigpとすると
大きい数の候補は上よりi等分されていることからN/i個数であり、そのどれかにNがあるため1/(N/i)
それに今回食べて、今後にNが出る確率を足す。 後ろは大きい数が出なくて今回見送った時に今後出る確率
bigp (1 / ( N / i ) + f(i+1,k-1) ) + (1-bigp) (f(i+1,k))
↑
より大きい数が出た場合は選ぶ => Nが現れたら必ず選べる => 1 / N の確率で今回Nが取れることから
1 / N + bigp ( f(i+1,k-1) ) + (1-bigp) (f(i+1,k))ともかける

2つ目の期待値はf(i+1,k)

static int N, K;
    static double[][] memo;//[i][k]:=i枚目を見ていて、残りk枚食べれる時の「今後の」最大期待値

    public static void solve() throws Exception {
        //longを忘れるなオーバーフローするぞ
        N = ni();
        K = ni();
        memo = new double[N + 1][K + 1];
        fill(memo, -1);
        System.out.println(dfs(1, K));
    }

    public static double dfs(int i, int k) {
        if (i == N + 1 || k == 0) return 0;
        if (memo[i][k] >= 0) return memo[i][k];
        //今まで選んだものが1つの時、次にそれより大きい数が出る確率は1/2である。
        //なぜならすべての数が出た場合について考える事は平均の数が出た時について考えることと同じだからである。
        //以降も今まで2つ選んでいたら、2つで平均を取るように3等分された状態について考えればいいので1/3
        //同様に1 / i
        double bigp = 1.0 / i;//今回今までよりも大きい数が出る確率

        //今までより大きい数が出たら食べ、小さければスルーする場合の期待値
        //(1.0 / (N / i) 今までより大きい事とi等分されていることから、残りの個数はN/i その中の一つ
        //bigp の外に出して1/Nとしてもよい
        double eat = bigp * (1 / (N * 1.0 / i) + dfs(i + 1, k - 1)) + (1 - bigp) * (dfs(i + 1, k));
        double not = dfs(i + 1, k);
        return memo[i][k] = max(eat, not);
    }