TopCoder SRM 642 Hard

2017-02-15 | [Competitive programming]

概要

N 箇所の区画があるホイールがある．各区画の値は最初は 0．

i = 0, 1, …, k-1 に対して，「ホイールの 1 区画を一様ランダムに選び，そこから続く s[i] 区画の値を 1 増やす」を行う．

その後，Alice がホイールの 1 区画を選ぶ．すると，その区画の値が公開される．次に Bob は，Alice が選んだ区画以外の 1 区画を選ぶ．このとき Alice が選んだ区画の値を参考にしてよい．

最適な戦略をとったとき，Alice と Bob が選んだ区画の値の合計値の期待値を最大化せよ．

解法

ランダム性より，Alice は常に区画 0 を選ぶとしてよい．

区画 0 の値が x になる確率および，区画 0 の値が x である条件下での区画 y の値の期待値，は順次 DP によって計算できる． Bob の最適な戦略は，区画 0 の値を聞いたあと，その値での条件付き期待値を最大化する区画を選ぶことである．

コード

double dp[310][310][310]; // round, score, (expv * prob)

double prob[310][310]; // round, score


int za[310][310], zb[310][310]; // len / idx


class WheelofFortune {
public:
    double maxExpectedValue(int N, vector <int> s) {
		int R = s.size();
		for (int i = 0; i <= R; ++i) {
			for (int j = 0; j <= R; ++j) {
				prob[i][j] = 0.0;
				for (int k = 0; k < N; ++k) {
					dp[i][j][k] = 0.0;
				}
			}
		}
		prob[0][0] = 1.0;

		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				za[i][j] = zb[i][j] = 0;
			}
		}
		for (int i = 1; i <= N; ++i) {
			for (int j = 0; j < N; ++j) { // top

				bool conz = (j == 0) || (j + i > N);
				for (int k = 0; k < i; ++k) {
					(conz ? zb : za)[i][(j + k) % N] += 1;
				}
			}
		}
		for (int i = 0; i < R; ++i) {
			for (int j = 0; j <= i; ++j) {
				prob[i + 1][j] += prob[i][j] * (1 - (double)s[i] / N);
				for (int k = 0; k < N; ++k) {
					dp[i + 1][j][k] += dp[i][j][k] * (1 - (double)s[i] / N) + (double)za[s[i]][k] / N * prob[i][j];
				}
				prob[i + 1][j + 1] += prob[i][j] * (double)s[i] / N;
				for (int k = 0; k < N; ++k) {
					dp[i + 1][j + 1][k] += dp[i][j][k] * (double)s[i] / N + (double)zb[s[i]][k] / N * prob[i][j];
				}
			}
		}

		double ret = 0;
		for (int i = 0; i <= R; ++i) {
			ret += i * prob[R][i];
			double tmp = 0;
			for (int j = 1; j < N; ++j) tmp = max(tmp, dp[R][i][j]);
			ret += tmp;
		}
		return ret;
    }
};