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 で通っちゃったんだけど,実装方針によるのかな?