Typical DP Contest J - ボール

問題: J - ボール

問題概要

$N (\leq 16)$ 個の障害物が $x$ 軸上に置かれていて，$i$ 番目の障害物の座標は $x_i (0 \leq x_i \leq 15)$ である。

すぬけ君がボールを座標 $x$ めがけて投げると，$x-1$，$x$，$x+1$ にそれぞれ $\frac{1}{3}$ の確率で飛んでいき，当該座標にあった障害物が倒れる。

すぬけ君の目的はボールを投げてこの障害物をすべて倒すまでにボールを投げる回数の期待値を求めよ。

ただしボールを投げる場所は，前に投げたボールの飛んだ場所を見てから決めることができる。

解法概要

制約が bitDP と言っているので，

$dp_{i} = i$ で表される障害物の集合がまだ倒されていないときの，すべての障害物を倒すまでにボールを投げる回数の期待値

とする。

初期値は $dp_0 = 0$ である (ただし $0$ は空集合 $\emptyset$ に対応している)。

次に遷移を考える。Sample Input1 (下記) を使って考える。

2
0 2

${0}$ という集合 ($i=2$ に対応しているとする) から $\emptyset$ への遷移については，ボールを $x$ めがけて投げるときの $x$ を適切に決めたとすると

$$dp_2 = \frac{1}{3} (dp_0+1) + \frac{2}{3} (dp_2+1)$$

という関係式ができる。右辺は，次にとりうる状態に対応する期待値に次の状態に遷移するための操作回数1回を足したものと，その確率をかけて足し合わせたものになっている。求めたい $dp_2$ が左辺にだけ現れるように式変形をすると

$$(1-\frac{2}{3}) dp_2 = \frac{1}{3} dp_0 + (\frac{1}{3} + \frac{2}{3})$$

$$dp_2 = dp_0 + 3$$

$dp_0 = 0$ より

$$dp_2 = 3 \texttt{.}$$

${2}$ という集合 ($i=1$ に対応しているとする) から $\emptyset$ への遷移や，${0, 2}$ という集合 ($i=3$ に対応しているとする) から $\emptyset$ への遷移も同様にして考えることができる。これらを一般化して考えると

$$(1 - \frac{\mathit{cnt}_\mathit{next}}{3}) dp_i = \sum_{j \in \mathit{next}(i, x)} \frac{1}{3} (dp_j + 1)$$

$$dp_i = \frac{3}{3 - \mathit{cnt}_\mathit{next}}\sum_{j \in \mathit{next}(i, x)} \frac{1}{3} (dp_j + 1) = \frac{3}{3 - \mathit{cnt}_\mathit{next}} (1 + \sum_{j \in \mathit{next}(i, x)} \frac{1}{3} dp_j ) \texttt{.}$$

ただし，$\mathit{cnt}_\mathit{next}$ は次の状態としてありうるもの (自分自身は除く) の数であり，$\mathit{next}(i, x)$ は $x$ めがけてボールを投げるときに $i$ の次の状態としてありうる状態の集合である。

ここまで，$x$ を適切に決めたという仮定を置いていたが，$0 \leq x \leq 15$ なので，各状態ペアの遷移について $x$ をすべて試しても間に合う。

ソースコード

#include <iostream>
#include <vector>
#include <iomanip>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;++i) {
        cin >> a[i];
    }

    vector<double> dp(1<<n, 0.0);
    for(int bi=1;bi<(1<<n);++bi) {   // どの障害物が残っているかの状態
        dp[bi] = 10000.0;
        for(int x=0;x<=15;++x) {
            double tmp_dp = 0.0;
            int tmp_cnt = 3;
            for(int i=0;i<n;++i) {
                if((bi & (1<<i)) == 0 or abs(a[i]-x) > 1) continue; // 既にない / 射程距離にいない障害物は墜とせない
                tmp_dp += 1.0/3.0 * dp[bi^(1<<i)];
                --tmp_cnt;
            }
            if(tmp_cnt == 3) continue;
            tmp_dp += 1;
            tmp_dp *= 3.0 / (3-tmp_cnt);
            if(dp[bi] > tmp_dp) dp[bi]= tmp_dp;
        }
    }

    cout << setprecision(10) << fixed << dp[(1 << n) - 1] << endl;
}

所感

Educational DP Contest も J は期待値だったね

J - Sushi