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;
}
};