hogecoder

tsutaj 競技プログラミングの記録

AtCoder Regular Contest 038 B: マス目と駒

ちょっと迷ってしまったので。

問題概要

原文を参照してください → B: マス目と駒 - AtCoder Regular Contest 038 | AtCoder

解説

rec[i][j] := (i, j) で手番が回ってきた人は勝つか負けるか? となるような配列を作ります。

あるマス  (i, j) について、この値は以下のように決定できます。

  • 1 ターンで行ける範囲に「負け」を表すマスが少なくとも 1 つある場合、勝ち
  • 上記に当てはまらない場合 (移動先の候補がない時も含む)、負け

少しわかりにくいと思うので解説すると、 (i, j) から 1 ターン動いた先で手番が回ってくる人、つまり「相手」が負け確定になるようなマスがある場合、そこに移動することで自分が勝ち確定になります。反対に、そのようなマスが 1 つもない場合は自分が負け確定になります。あとはこれを右下からメモ化再帰で求めていけば良いです。

ソースコード

int h, w;
char board[110][110];

// rec[i][j] := (i, j) から始めたら勝つか負けるか?
int rec[110][110];

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

int solve(int x, int y) {
    int &r = rec[x][y];
    if(r != -1) return r;
    r = 1;
    rep(i,0,3) {
        int nx = x + dx[i], ny = y + dy[i];
        if(nx == h || ny == w || board[nx][ny] == '#') continue;
        if(solve(nx, ny) == 1) r = 0;
    }
    return r;
}

signed main() {
    cin >> h >> w;
    rep(i,0,h) rep(j,0,w) cin >> board[i][j];
    memset(rec, -1, sizeof(rec));
    cout << (solve(0, 0) ? "Second" : "First") << endl;
    return 0;
}

先攻か後攻かの情報も保持したほうがいいのかな、とか色々考えていたらすんなり書けませんでした。ゲームの問題はもう少し慣れが必要そうです。

Google Code Jam Round 1B 2017 C: Pony Express

想定解法と違う方法で解いたので一応メモ。

問題概要

街が  N  (2 \le N \le 100) つあり、街  i j を結ぶ道路の長さは  D_{ij} (km) (-1 \le D_{ij} \le 10^{9}, ただし  -1 の時は道路がないことを表す) である。

それぞれの街には馬がおり、街  i にいる馬は時速  s_{i} (km/h)  (1 \le s_{i} \le 10^{3}) で移動することができ、最大で  e_{i} (km)  (1 \le e_{i} \le 10^{9}) 移動できる。街と街の移動には馬を利用する (必要ならば途中の街で馬を乗り継ぐこともできる)。このとき、以下のクエリを  Q (1 \le Q \le 100) 処理せよ。

  •  U から  V に向けて、上記の制約を満たした乗り継ぎをしながら馬に乗って行くことを考えたとき、かかる時間の最小値を求めよ。

解説

拡張ダイクストラで求めることができます。

rec[i][j][k] := 街 i を出発時点で、今乗っている馬 j が距離 k を走った時にかかる累計時間の最小値 となるような配列を作ります。この配列を真面目に取ろうとしても  10^{2} \times 10^{2} \times 10^{9} のサイズの配列を取らなければならないので無理ですが、実際はそのほとんどが使われることが無いため、使うところだけ利用できるように map を利用して作ることにします。

 x から  y に行く際には、馬の走れる距離が十分にあると仮定すると以下の  2 つの遷移が考えられます。

  •  y に着いた後も、今乗っている馬に乗り続ける
  •  y に着いたら、街  y にいる馬に乗り換える

別の馬に乗り換えた場合、走行距離の情報がリセットされることに注意して遷移すれば良いです。制約を満たさない動き (たとえば、馬の走行距離の限界を超えるなど) をしないようにすることも重要です。

ソースコード

struct Elem {
    int city, horse, dist;
    double cost;
    Elem(int a, int b, int c, double d) : city(a), horse(b), dist(c), cost(d) {}
};

bool operator<(const Elem &a, const Elem &b) {
    return a.cost > b.cost;
}

int e[110], s[110];
int mat[110][110];
signed main() {
    int t; cin >> t;
    repq(cs,1,t) {
        int N, Q; cin >> N >> Q;
        rep(i,0,N) cin >> e[i] >> s[i];
        rep(i,0,N) rep(j,0,N) cin >> mat[i][j];
        printf("Case #%lld:", cs);
        rep(i,0,Q) {
            // city, horse, dist
            map<int, map<int, map<int, double> > > rec;
            int u, v; cin >> u >> v;
            double ans = DBL_MAX;
            u--; v--;
            priority_queue<Elem> q;
            q.push(Elem(u, u, 0, 0.0));
            while(!q.empty()) {
                Elem pick = q.top(); q.pop();
                int from = pick.city, d = pick.dist, usg = pick.horse;
                if(from == v) {
                    ans = min(ans, pick.cost);
                    break;
                }
                rep(to,0,N) {
                    if(mat[from][to] == -1) continue;
                    if(d + mat[from][to] > e[usg]) continue;
                    int nd = d + mat[from][to];
                    double c = (double)mat[from][to] / s[usg];
                    if(!rec[to][usg].count(nd) || rec[to][usg][nd] > rec[from][usg][d] + c) {
                        rec[to][usg][nd] = rec[from][usg][d] + c;
                        q.push(Elem(to, usg, nd, rec[to][usg][nd]));
                    }
                    if(!rec[to][to].count(0) || rec[to][to][0] > rec[from][usg][d] + c) {
                        rec[to][to][0] = rec[from][usg][d] + c;
                        q.push(Elem(to, to, 0.0, rec[to][to][0]));
                    }
                }
            }
            printf(" %.12lf", ans);
        }
        cout << endl;
    }
    return 0;
}

実はワーシャルフロイドを 2 回やる想定解法をまだ読んでいない・・・ (読もう)