Typical DP Contest J - ボール
解法
期待値を求める問題.bitDP か線形方程式を解くところだが,|S| = 1024 なので後者は厳しい.なので bitDP を疑う.ただし、このためには遷移をDAGにしないといけない。
dp[S] := すでに倒れたものが S の状態である時からはじめて,すべてのものを倒すのに必要なボールの数の期待値の最小
とおく.
遷移を,入力例にある,ボールが 0 と 2 にある場合で考える.
もしボールを 1 に投げたら,1/3 の確率で,0に当たる or なにも当たらない or 2に当たるなので,以下の式が成り立つ.
dp[000] = (dp[100] + 1) / 3 + (dp[000] + 1) / 3 + (dp[001] + 1) / 3
式を見れば分かる通り,この遷移には自己辺があるので遷移がDAGでない.
左辺と右辺にともに現れる dp[000] をどうするかだが,実は単純に移行するだけで解決する.
dp[000] * (1 - 1/3) = (dp[100] + dp[001]) / 3 + 1
なので,自身の係数を別に持っておくことで,いつもの bitDP になる.
投げる位置は適当に全部試して,一番期待値が小さいところを選べばOK.
投げる3箇所が全て空なら,その場所は無視する(投げる意味がない).
ソースコード
#include <bits/stdc++.h> using namespace std; constexpr int INF = 1e9; constexpr double eps = 1e-9; int N; double rec(int S, vector<int> const& idx, vector<double>& dp) { if(dp[S] != -1) { return dp[S]; } if(__builtin_popcount(S) == N) { return dp[S] = 0; } double& res = dp[S]; res = INF; for(int x = 1; x <= 14; ++x) { double t = 1; double self = 1; for(int i = -1; i <= 1; ++i) { int j = idx[x + i]; if(j == -1 || (S >> j) & 1) { self -= 1.0 / 3; continue; } t += rec(S | (1 << j), idx, dp) / 3; } if(abs(self) < eps) { continue; } t /= self; res = min(res, t); } return res; } int main() { cin >> N; vector<int> idx(16, -1); for(int i = 0; i < N; ++i) { int x; cin >> x; idx[x] = i; } vector<double> dp(1 << N, -1); cout << fixed << setprecision(10) << rec(0, idx, dp) << endl; }
感想
自己辺の処理をどうするか若干迷ってしまった.
遷移ばかり意識していると,移行という単純な式変形がぱっと浮かばない.