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

感想

自己辺の処理をどうするか若干迷ってしまった.
遷移ばかり意識していると,移行という単純な式変形がぱっと浮かばない.