AtCoder ARC #055 : B - せんべい

まさかABC３問解くのが６人とは。今回Bが難しいのでBから書くことにする。
http://arc055.contest.atcoder.jp/tasks/arc055_b

問題

1～Nの数が等確率でランダムな順番にシャッフルされ、順に渡される。
渡される側は、渡された数そのものを知ることはできない。ただしこれまで渡された数との相対的な大小は把握できる。
渡された数のうち最大K個まで選択できるとすると、最適な戦略をとった場合Nを選択できる確率を求めよ。

解法

数が渡されたとき、これまで渡された一連の数の中で最大でないならNではありえないので選択はしない。
逆に最大である場合、選択するケースとしないケースどちらが最終的に正解確率を高められるかDPで考えよう。

公式解説とは異なるが、自分は以下のメモ化再帰で解いた。
dp(s,k) := 次にs個目の数が渡される際、"まだNが渡されていなくて"、あとk回数を選択できるとき、Nを選択する確率

この状態であり得るケースは以下の３通り。これらは独立である。

1. 渡された数がNである確率P(N)は、残り(N+1-s)回数が数が渡される間で等確率なはずなので1/(N+1-s)
2. 渡された数がNでないケース
   1. Nではないが過去最大であるケースの確率P(fakemax)は、Nである確率を除いた(1-1/(N+1-s))のうち1/s (渡された最初のs個のうち最大と考える)
   2. そもそも過去最大でないケースP(notmax)は残り(1-1/(N+1-s))*(s-1)/s

最後のケースはそもそも渡された数がNでないことは確定しているので、その場合選択するのは常に損。
それ以外のケースは、選択するケースとしないケースのうち最大値を取ろう。

まとめると dp(s,k) = P(notmax)*dfs(s+1,k) + max(P(N)+P(fakemax)*dfs(s+1,k-1), P(fakemax)*dfs(s+1,k))
これはメモ化再帰でP(NK)で解ける。

int N,K;
double memo[1010][1010];

double dfs(int step,int k) {
	if(k<=0) return 0;
	if(k>=N-step+1) return 1;
	if(memo[step][k]>=0) return memo[step][k];
	
	int left=N+1-step;
	double yes=1.0/left;
	double fake=(1-yes)/step;
	double no=1-fake-yes;
	
	double take = (yes*1 + fake*dfs(step+1,k-1));
	double nottake = (fake*dfs(step+1,k));
	
	return memo[step][k] = no*dfs(step+1,k) + max(take,nottake);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N>>K;
	
	FOR(x,N+1) FOR(y,N+1) memo[x][y]=-1;
	_P("%.12lf\n",dfs(1,K));
}

まとめ

状態遷移がかなり混乱したが、何とか解けて良かった。