ARC 003 C - 暗闇帰り道

問題ページ
C: 暗闇帰り道 - AtCoder Regular Contest 003 | AtCoder

考えたこと

• 最小の最大化なので2分探索をする
• 経路の明るさvを達成できるかどうかをO(HW)くらいで判定できればよさそう
• d[y][x] = (座標(y,x)に到達できる最短の時刻t) としてdijkstraをすると判定ができる
• 投げたら通った

解法

経路の明るさvを達成できるような経路が存在するかどうか？というような問題について考える。2次元グリッド上でdijkstraを行う。隣接する地点が移動できる地点であって到達する時刻が縮むのならばその地点に進む。これでこの問題にはO(HWlog(HW)) (多分)で解ける。
(1/2)⁴⁰ <= 1e-12 より40回程度二分探索をすれば精度は問題ない。したがってこの問題は解けた。
注意点としてpow(0.99, t) をその都度計算するとTLEするので前計算しておくべき。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}

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

int h, w, sx, sy, gx, gy;
string s[505];
int d[505][505];
double po[250010];

bool check(double mid) {
  priority_queue<VI, VVI, greater<VI>> que;
  que.push({0, sy, sx});
  REP(i, h) REP(j, w) d[i][j] = INF;
  d[sy][sx] = 0;

  while(que.size()) {
    VI v = que.top(); que.pop();
    int y = v[1], x = v[2];
    if(x == gx && y == gy) break;
    if(v[0] > d[y][x]) continue;
    REP(i, 4) {
      int nx = x + dx[i], ny = y + dy[i];
      if(IN(0, w, nx) && IN(0, h, ny) && s[ny][nx] != '#' && d[ny][nx] > d[y][x] + 1) {
        if(s[ny][nx] == 'g') {
          d[ny][nx] = d[y][x] + 1;
          que.push({d[ny][nx], ny, nx});
        } else {
          double val = (s[ny][nx]-'0')*po[v[0]+1];
          if(val >= mid) {
            d[ny][nx] = d[y][x] + 1;
            que.push({d[ny][nx], ny, nx});
          }
        }
      }
    }
  }

  if(d[gy][gx] == INF) return false;
  return true;
}

signed main(void)
{
  cin >> h >> w;
  REP(i, h) cin >> s[i];
  REP(i, h) REP(j, w) {
    if(s[i][j] == 's') sy = i, sx = j;
    if(s[i][j] == 'g') gy = i, gx = j;
  }
  po[0] = 1;
  FOR(i, 1, h*w+1) po[i] = po[i-1]*0.99;

  double lb = 0, ub = 9;
  REP(i, 40) {
    double mid = (lb+ub)/2;
    if(check(mid)) {
      lb = mid;
    } else {
      ub = mid;
    }
  }

  if(!check(-INF)) cout << -1 << endl;
  else cout << fixed << setprecision(10) << lb << endl;

  return 0;
}