AOJ 2336 Spring Tiles

解法

最適な戦略を取った場合,各マスの移動は確率的に決まるわけではなく,ある基準によってバネに向かうかゴールに直接向かうか定まっているはずです.
問題はなにが基準なのかですが,これは自然に「今いる地点がバネとゴールのどちらにどれぐらい近いか」であるとわかります.
なので,バネを根とする幅優先探索(ゴールを壁とみなす)と,ゴールを根とする幅優先探索(バネを壁とみなす)が必要です.

また,これも大切なことですが,すべてのバネは同一に扱えます.つまり,バネを使ってからゴールに着く期待値を E とすると,これはどのバネでも同じであるということです.

よって以下の式が成り立ちます.
$\displaystyle E = \frac{\sum_{s \in S}gd[s] + \sum_{t \in T}(sd[t] + E)}{H \times W}$
ただし,$S$は直接ゴールに向かうのが最適なマスの集合,$T$はバネに向かうのが最適な集合です.また,$gd$と$sd$はそれぞれゴールからの距離とバネからの距離を表します.
$E$の項を左辺に移行して変形すると,Eの値が求まります.

$S$ と $T$ の集合を決めるのに先程の基準を使いますが,初期状態をとりあえずすべてのマスが $S$ であると定めて,すこしずつ $T$ にうつしていけば良いです.
基準の値は,愚直に -H*W から H*W まで全通り試しても十分間に合います.
sd[i] - gd[i] の値が基準値を下回ったら,そのマスはバネに向かうとして,先の式の各値を更新し,そのたびに E を再計算します.(こういうことをするためには,sd[i] - gd[i] の値をソートしておく必要があります.)

E が求まったら,始点が現在の最適戦略でバネに向かうかゴールに向かうか確認して,前者なら sd[start] + E が,後者なら gd[start] が候補になります.

注意するべき点は,壁などの存在により,そもそもバネにしか行けないマス,どちらにも行けないマス,ゴールにしか迎えないマスを,最初から S と T に決め打ちして入れてしまう必要があるところです.

計算量は,ソートが一番重くて O(HWlogHW) です.

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

constexpr int INF = 1e9;

constexpr int dx[4] = {0, 1, 0, -1};
constexpr int dy[4] = {1, 0, -1, 0};

int main() {
    int W, H;
    cin >> W >> H;
    vector<string> v(H);
    int s, g;
    int fcnt = 0;
    queue<int> que;
    vector<int> sd(H * W, INF);
    for(int i = 0; i < H; ++i) {
        cin >> v[i];
        for(int j = 0; j < W; ++j) {
            if(v[i][j] == 's') {
                s = i * W + j;
            } else if(v[i][j] == 'g') {
                g = i * W + j;
            } else if(v[i][j] == '*') {
                que.push(i * W + j);
                sd[i * W + j] = 0;
            }
            fcnt += v[i][j] == '.' || v[i][j] == 's';
        }
    }

    while(!que.empty()) {
        int y = que.front() / W;
        int x = que.front() % W;
        que.pop();
        for(int i = 0; i < 4; ++i) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 0 || H <= ny || nx < 0 || W <= nx || v[ny][nx] == '#' || v[ny][nx] == 'g' || sd[ny * W + nx] != INF) {
                continue;
            }
            sd[ny * W + nx] = sd[y * W + x] + 1;
            que.push(ny * W + nx);
        }
    }

    vector<int> gd(H * W, INF);
    que.push(g);
    gd[g] = 0;
    double total_gd = 0;
    while(!que.empty()) {
        int y = que.front() / W;
        int x = que.front() % W;
        que.pop();
        for(int i = 0; i < 4; ++i) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 0 || H <= ny || nx < 0 || W <= nx || v[ny][nx] == '#' || v[ny][nx] == '*' || gd[ny * W + nx] != INF) {
                continue;
            }
            gd[ny * W + nx] = gd[y * W + x] + 1;
            total_gd += gd[ny * W + nx];
            que.push(ny * W + nx);
        }
    }

    vector<pll> d;
    int scnt = 0;
    double total_sd = 0;
    for(int i = 0; i < H * W; ++i) {
        if(i == g || v[i / W][i % W] == '*' || v[i / W][i % W] == '#') {
            continue;
        }
        if(gd[i] == INF && sd[i] != INF) {
            scnt++;
            total_sd += sd[i];
        } else if(sd[i] != INF) {
            d.emplace_back(-gd[i] + sd[i], i);
        }
    }
    sort(d.begin(), d.end());

    double res = 1e18;
    auto it = d.begin();
    for(int i = -H * W; i <= H * W; ++i) {
        while(it != end(d) && it->first <= i) {
            scnt++;
            total_sd += sd[it->second];
            total_gd -= gd[it->second];
            it++;
        }
        if(scnt == fcnt) {
            continue;
        }
        double E = (total_gd + total_sd) / (1 - (double)scnt / fcnt) / fcnt;
        if(gd[s] == INF || -gd[s] + sd[s] <= i) {
            res = min(res, E + sd[s]);
        } else {
            res = min(res, (double)gd[s]);
        }
    }

    cout << fixed << setprecision(10) << res << endl;
}

感想

なんとなくいい問題だと思った.
解いてから他の人の解法読んだりしたんですが,double を使って誤差で死んだという人が結構いるらしい.
自分は何も考えずに double で通っちゃったんだけど,実装方針によるのかな?