mayoko’s diary

プロコンとかいろいろ。

Typical DP Contest J - ボール

解法

dp[state] = (state で表されるものはすでに倒されている場合の, あと必要な投球数)
とします。

ある state においては, どこか 1 つの座標に向かってボールを投げ続けるのが最適です(外れたからやっぱこっち, とかやるより state が変わるまで同じ場所に投げ続けるのが良い)。

state において x にボールを投げ続けるとすると, 考えられる可能性は,

  • 何らかのものにあたって state が変わる
  • 何にも当たらなくて state が変わらない

のいずれかです。前者は dfs(nextState) で期待値が計算できますが, 後者は決まりません。そこで, 二分探索をしましょう。dp[state] の値をある値 med に決めうちして後者の期待値を決めて, dp[state] の値を求めます。これが最初に決めうちしたのより大きかったら high を 下げる, などやれば良いです。

const int MAXN = 20;
const double INF = 1e9;
const int LOOP = 30;
int N;
int X[MAXN], rX[MAXN];

double dfs(int state);

double calc(int x, int state, double med) {
	double ret = 1;
	if (x < 0 || x >= MAXN || rX[x] == -1 || (state&(1<<rX[x]))) ret += med;
	else ret += dfs(state^(1<<rX[x]));
	return ret;
}

double dp[1<<16];

double dfs(int state) {
	double& ret = dp[state];
	if (ret >= 0) return ret;
	if (state == (1<<N)-1) return ret = 0;
	ret = INF;
	for (int x = 0; x <= 15; x++) {
		double low = 0, high = 100;
		for (int i = 0; i < LOOP; i++) {
			const double med = (low+high)/2;
			double tmp = 0;
			for (int j = -1; j <= 1; j++)
				tmp += calc(x+j, state, med);
			tmp /= 3;
			if (tmp < med) high = med;
			else low = med;
		}
		ret = min(ret, (low+high)/2);
	}
	return ret;
}

int main() {
    cin >> N;
    memset(rX, -1, sizeof(rX));
    for (int i = 0; i < N; i++) {
    	cin >> X[i];
    	rX[X[i]] = i;
    }
    for (int i = 0; i < 1<<N; i++) {
    	dp[i] = -1;
    }
    printf("%.10lf\n", dfs(0));
    return 0;
}