AtCoder ARC #016 : D - 軍艦ゲーム

本番のアプローチではうまくいかなかったので、結局Editorialの「なんか二分探索するらしい」というヒントをもとに練習。
http://arc016.contest.atcoder.jp/tasks/arc016_4

問題

0～(N-1)番の点があり、数字の小さい方から大きい方に対していくつか有向辺が張られている。
初期状態でHPが与えられ、0から(N-1)番の点に移動することを考える。
各点において、各有向辺を均等な確率で選択し、コスト１を払って次の点に動く。この時、移動先の点iにおいてD[i]の分HPが減少する。

ここで、プレイヤーはこのまま移動を継続するか、減少したHP分のコストを払って0番に戻るかを選択できる。
また、次の移動でHPが0以下になるような場合は次の移動をできず、0番に戻るしかない。

プレイヤーが最適行動をしたとき、コスト期待値を最小化せよ。

解法

現在位置および残りHPを状態として持ち、点(N-1)までのコストをDPをすることを考える。
ここで、答えである「位置=0、残りHP=HP」からのコストを仮にCとする。

以下の手順で各位置およびHPごとにDPを行う。

1. 移動が可能である場合、すなわち有向辺が１個以上あり、いずれも残りHPで移動かのうなら、このまま移動した場合のコストを求める。その値は、移動コストの１に、各移動先状態のコストの平均値を加えたもの。
2. 即座に戻ってやり直す場合のコストは、C+(HP減少分)
3. 1と2のうち小さい方がその状態のコスト。

ここで、上記手順で得られる「位置=0、残りHP=HP」状態でのコストが仮置きしたCより小さいなら、答えはCより小さいと言える。
よって、Cを二分探索して、仮置きしたCがDP後の値より大きくなるようなCの最小値を求めればよい。

DP1回がO(MH)なので、数十回二分探索しても問題ない。
また、どんな大きなCでも条件を満たせないなら、到達不可能なので-1を返せばよい。

int N,M,H;
vector<int> E[101];
int D[101];
double dpdp[101][101];

int okok(double rc) {
	ZERO(dpdp);
	int f,i,j,k,l, x,y;
	
	for(i=N-2;i>=0;i--) for(j=1;j<=H;j++) {
		int ng=0;
		FOR(x,E[i].size()) if(D[E[i][x]]>=j) ng++;
		if(ng || E[i].empty()) {
			dpdp[i][j]=(H-j)+rc;
			continue;
		}
		dpdp[i][j] = 1;
		FOR(x,E[i].size()) dpdp[i][j] += dpdp[E[i][x]][j-D[E[i][x]]]/E[i].size();
		dpdp[i][j] = min(dpdp[i][j], (H-j)+rc);
	}
	return dpdp[0][H]<rc;
}

void solve() {
	int f,i,j,k,l, x,y;
	
	cin>>N>>M>>H;
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
	}
	FOR(i,N) cin>>D[i];
	
	double lo=0,hi=1e9;
	FOR(i,60) {
		double mi=(lo+hi)/2;
		if(okok(mi)) hi=mi;
		else lo=mi;
	}
	if(lo>=1e8) _P("-1\n");
	else _P("%.8lf\n",lo);
}

まとめ

これ二分探索なんて思いつかないわ…。