問題概要

二次元マップが与えられて、各マスは

床 ('.')
壁 ('#')
バネ ('*')

の 3 つの属性がある。スタート ('s') とゴール ('g') が設定されていて、いずれも床属性である。

s から g へ最速で行きたい。壁は通れない。バネは踏むと各床 ('g' 除く) の中から一様ランダムの床に飛ばされる。最適戦略をとったときのゴールまでに必要なステップ数の期待値を求めよ。

制約

3 <= H, W <= 500
'g' もバネも存在しない床の連結成分は存在しない

考えたこと

方程式を立てる系に見えた。でもマス数は 250000 にも及ぶので単純に連立方程式とかでは解けなさそう。

1 つ考えたことは、一度バネを踏んだら、状態が初期化されてしまう。すなわちどのバネを踏んでもそこから最短でのゴールまでの期待値は等しくなる。それを $t$ とかおいてみることにする。

そうすると、

$Nt = \sum_{x \in 床} ( \min(x とゴールの距離, x と最寄りのバネとの距離 + t) )$

という方程式が立つ。これは左辺から右辺を引くと、 $t$ について単調増加になっていることが簡単な考察でわかるので、二分探索で解ける。

コード

#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <queue>
using namespace std;

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

int H, W;
vector<string> fi;
using pint = pair<int,int>;

void bfs(queue<pint> &que, vector<vector<int> > &dist) {
    while (!que.empty()) {
        auto p = que.front(); que.pop();
        for (int dir = 0; dir < 4; ++dir) {
            int nx = p.first + dx[dir], ny = p.second + dy[dir];
            if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
            if (fi[nx][ny] != '.' && fi[nx][ny] != 's') continue;
            if (dist[nx][ny] == -1) {
                dist[nx][ny] = dist[p.first][p.second] + 1;
                que.push(pint(nx, ny));
            }
        }
    }
}

int main() {
    cin >> W >> H;
    fi.resize(H);
    for (int i = 0; i < H; ++i) cin >> fi[i];

    pint s, g;
    vector<pint> ss;
    for (int i = 0; i < H; ++i) for (int j = 0; j < W; ++j) {
            if (fi[i][j] == 'g') g = pint(i, j);
            else if (fi[i][j] == 's') s = pint(i, j);
            else if (fi[i][j] == '*') ss.push_back(pint(i, j));
        }

    vector<vector<int> > dpg(H, vector<int>(W, -1)), dps(H, vector<int>(W, -1));
    queue<pint> queg;
    queg.push(g), dpg[g.first][g.second] = 0;
    bfs(queg, dpg);
    queue<pint> ques;
    for (auto p : ss) ques.push(p), dps[p.first][p.second] = 0;
    bfs(ques, dps);

    double low = 0, high = 1LL<<60;
    for (int _ = 0; _ < 100; ++_) {
        double t = (low + high) / 2;
        double sum = 0;
        int N = 0;
        for (int i = 0; i < H; ++i) {
            for (int j = 0; j < W; ++j) {
                if (fi[i][j] != '.' && fi[i][j] != 's') continue;
                ++N;
                double tmp = 1LL<<60;
                if (dps[i][j] != -1 && tmp > dps[i][j] + t) tmp = dps[i][j] + t;
                if (dpg[i][j] != -1 && tmp > dpg[i][j]) tmp = dpg[i][j];
                sum += tmp;
            }
        }
        if (t * N >= sum) high = t;
        else low = t;
    }

    double res = 1LL<<60;
    if (dps[s.first][s.second] != -1 && res > dps[s.first][s.second] + high)
        res = dps[s.first][s.second] + high;
    if (dpg[s.first][s.second] != -1 && res > dpg[s.first][s.second])
        res = dpg[s.first][s.second];

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

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 2336 スプリング・タイル (JAG 夏合宿 2010 day2-G) (600 点)

問題概要

制約

考えたこと

コード