ARC055B : せんべい

http://arc055.contest.atcoder.jp/tasks/arc055_b
良問DP。本番中は誤読死したので解説を見て解きました。
　しかのあっとこでぃあー君がおいしさ1 ~ Nのせんべいを食べます。N番目のせんべいはなんとしても食べたいのですが、あっとこでぃあー君は胃が小さいのでせんべいをK枚しか食べられません。無慈悲な観光客はせんべいをランダムに与え、あっとこでぃあー君は食べてないせんべいも含め、与えられたせんべいの順序関係を比較できます。あっとこでぃあー君最適に行動した時N番目のせんべいを食べられる確率を求めよ、という問題。

　考えるべきなのは
・新しく(i番目に)与えられたせんべいが今までの中で最大かどうか
・最大でないなら食べない
・最大なら、両方試して大きいのを取る
ということ。状態に
・最大のせんべいに出会ったとき、食べたか
を加えると簡潔になります。
　一度わかってしまうとなんてことはないのに、あっとこでぃあー君がせんべいを食べる戦略が一意に決まるものだと思い込んでしまい、まったく解けませんでした……。今考えると、「最適」という時点ではいDPと考えても良かったかもしれません（しかしこういうことをしていると某gle greedy jamで死ぬ）。
メモ化再帰解

int N, K;
double memo[1010][1010][2];
double dfs(int n, int k, bool eat){
    if(k > K) return 0.0;
    if(n == N) return eat ? 1.0 : 0.0;
    double& res = memo[n][k][eat];
    if(res != -1.0) return res;
    res = 0.0;
    double p1 = n / (n + 1.0), p2 = 1.0 / (n + 1.0);
    //次がmaxではない
    res += p1 * dfs(n + 1, k, eat);
    //次がmax
    res += p2 * max(dfs(n + 1, k, false), dfs(n + 1, k + 1, true));
    return res;
}
int main(){
    scanf("%d%d", &N, &K);
    rep(i, 1010) rep(j, 1010) rep(k, 2) memo[i][j][k] = -1.0;
    printf("%.10f", dfs(0, 0, false));
    return 0;
}

DP解。

int N, K;
double dp[1010][1010][2];
int main(){
    scanf("%d%d", &N, &K); K++;
    rep(i, K) rep(j, 2) dp[N][i][j] = j - 0.0;
    for(int i = N - 1; i >= 0; --i) rep(j, K) rep(k, 2){
        double p1 = i / (i + 1.0), p2 = 1.0 / (i + 1.0);
        dp[i][j][k] += p1 * dp[i + 1][j][k];
        dp[i][j][k] += p2 * max(dp[i + 1][j + 1][1], dp[i + 1][j][0]);
    }
    printf("%.10f", dp[0][0][0]);
    return 0;
}

　たいへん良さがあるDPでしたが、自力で解きたかったなあ。