AtCoder Regular Contest 055 B - せんべい

難しすぎる…

問題

arc055.contest.atcoder.jp

解法

鹿の立場に完全に寄り添って考えます。今回は問題の性格からして動的計画法な気がします(ゲームの流れ(状態)に応じて戦略を変えるというような感じになるはずなので)。ということで dp を考えるのですが, まず 「今何枚目のせんべいを考えているか」「今食べたせんべいの枚数」というのは状態に入れそうです。

基本的な戦略としては, 「今考えているせんべいが今までに食べたせんべいの中で最大だったら選ぶか選ばないか考える」「そうでなかったらそのせんべいは絶対選ばない」というものです。これで確率をきちんと求められればうれしいんですが, 上の状態しか考えないと計算は不可能です。

鹿の立場になって考えてみると, 「最大のものを食べているか」ということは最後までわからず, わかるのは「今までのせんべいの中で最大のものを食べているか」ということだけです。ただ, これを使うと dp[N][*] の時点で「今までのせんべいの中で最大のものを食べている」という確信があれば, 全体で最大のものを食べている, と結論づけることはできます。そこで, 上の状態にさらに「今までのせんべいの中で最大のものを食べているか」という状態を追加します。そうすると, 自然な dp 遷移を作ることができます。遷移は下の dfs を参考にしましょう。

const int MAXN = 1111;
double dp[MAXN][MAXN][2];
int K, N;

double dfs(int n, int ate, int isMax) {
    double& ret = dp[n][ate][isMax];
    if (ret >= 0) return ret;
    if (n == N) return ret = isMax;
    ret = 0;
    // 最大でない
    ret += 1.*n/(n+1) * dfs(n+1, ate, isMax);
    // 最大
    // 選ぶ
    double tmp = 0;
    if (ate < K) tmp = 1./(n+1) * dfs(n+1, ate+1, 1);
    // 選ばない
    tmp = max(tmp, 1./(n+1)*dfs(n+1, ate, 0));
    ret += tmp;
    return ret;
}

int main() {
    for (int i = 0; i < MAXN; i++) for (int j = 0; j < MAXN; j++) for (int b = 0; b < 2; b++) {
        dp[i][j][b] = -1;
    }
    cin >> N >> K;
    printf("%.10lf\n", dfs(0, 0, 0));
    return 0;
}