Pitching [第五回 アルゴリズム実技検定 K]

https://atcoder.jp/contests/past202012-open/tasks/past202012_k

前提知識

• bitDP
• 期待値DP

解説

https://atcoder.jp/contests/past202012-open/submissions/22325031

考え始めが難しい問題。

ここがまず重要であるが、全体の状態を考えると2¹⁶通りしかないことが分かる。
かつ、各状態からの遷移を見ると、DAGの形を取っている。
なので、期待値DP的なことができそうである。
なお、状態はbitで保持できるので同時にbitDPともいえる。
この方針で考えてみよう。

期待値DP

DP計算なので、漸化式を考えると、とりあえずどこにボールを投げるかで遷移が決まりそうである。
ボールを投げる場所は的が無い場所もありえるので、すべての的を狙った場合を考える。
一般的なイメージを

(x,y)に投げるとその周辺5マスに弾が当たりうる。
例えば

.#.  
###  
.#.  

という盤面で中心にボールを投げると、
E[msk] = 1 + (E[msk - 中心] / 5 + E[msk - 上] / 5 + E[msk - 右] / 5 + E[msk - 下] / 5 + E[msk - 左] / 5)
となる。
これを計算すればOK。
だが、抜けている場合は状態が変化しない。

.#.  
#..  
.#.  

このような場合で中心にボールを投げると
E[msk] = 1 + (E[msk] / 5 + E[msk - 上] / 5 + E[msk] / 5 + E[msk - 下] / 5 + E[msk - 左] / 5)
のように中心と右はE[msk]みたいになる。
これでは計算ができないので頑張る。

E[msk] = 1 + (E[msk] / 5 + E[msk - 上] / 5 + E[msk] / 5 + E[msk - 下] / 5 + E[msk - 左] / 5)
5E[msk] = 5 + E[msk] + E[msk - 上] + E[msk] + E[msk - 下] + E[msk - 左]
3E[msk] = 5 + E[msk - 上] + E[msk - 下] + E[msk - 左]
E[msk] = (5 + E[msk - 上] + E[msk - 下] + E[msk - 左]) / 3

こういう感じに変形ができる。
なので、周辺5つで的が残っている所の期待値+5をして、残っている個数で割れば答えになる。
この計算を順次やっていこう。

DPを全部作り終えたら最後に入力に合致する物を答える。

string S[4];
double dp[1 << 16];
//---------------------------------------------------------------------------------------------------
int dx[5] = { 0, 1, 0, -1, 0 }, dy[5] = { -1, 0, 1, 0, 0 };
void _main() {
    rep(y, 0, 4) cin >> S[y];
    
    rep(msk, 1, 1 << 16) {
        dp[msk] = 1e9;
        rep(y, 0, 4) rep(x, 0, 4) {
            int cnt = 0;
            double tot = 5;
            rep(d, 0, 5) {
                int xx = x + dx[d];
                int yy = y + dy[d];
                if (0 <= xx && xx < 4 && 0 <= yy && yy < 4 && msk & (1 << (yy * 4 + xx))) {
                    cnt++;
                    tot += dp[msk ^ (1 << (yy * 4 + xx))];
                }
            }
            if (0 < cnt) chmin(dp[msk], tot / cnt);
        }
    }

    int Smsk = 0;
    rep(y, 0, 4) rep(x, 0, 4) if (S[y][x] == '#') Smsk |= 1 << (y * 4 + x);
    
    double ans = dp[Smsk];
    printf("%.10f\n", ans);
}