AtCoder Regular Contest 044 C - ビーム

問題

arc044.contest.atcoder.jp

解法

せっかくなので部分点解法も載せておきます。

d[t][x][y] = (時刻 t に座標 x, y にいるときの最短距離) というようにすると, d[0][x][y] = 0 をスタートにしてダイクストラすれば答えが求まります。

で, 満点解法です。

まず, 実はこの問題では x 座標と y 座標で問題を独立に考えられることに注目します。

つまり, 「x 軸でビームをかわすゲーム」と「y 軸でビームをかわすゲーム」の 2 つのゲームの移動量の合計を答えとすれば良い, ということです。

このように考えると, 少なくとも
dp[t][x] = (時刻 t に座標 x にいるときの最小移動量) という感じで計算量を落とせます。

さらに, 時刻 t に座標 x にビームが来なければ動かなくて良いことに注目すると, 「ビームが来た時右に動く」, 「ビームが来た時左に動く」という 2 つの動きだけを dp に組み込めば良いです。

ビームが複数来る場合, 右に動いたらまたビーム, ということがあるので, まず最初に右に動く場合の最小値を求め, 次に左に動く場合の最小値を求める, としたあとビームが来たところの最小移動量を INF にする, というような感じにすると良いです。

得た知見

• 問題を 2 つにわける発想がなかった
  • 2 次元問題とか 2 つの変数を含む式とか見たら 2 つの部分問題に分けられないか考えよう
• その後の dp も実は最初よくわからなかった
  • 一回の動作で「右行ってやっぱ左」みたいな動作はないときは右決め打ち, 左決め打ちみたいな 2 通りを考える dp で良い

部分点解法

struct edge {
    int v;
    ll w;
    edge() {}
    edge(int v, ll w) : v(v), w(w) {};
};

const ll INF = 1e9;

vector<ll> dijkstra(int n, vector<vector<edge> >& G) {
    vector<ll> d(n, LLONG_MAX/10);
    priority_queue<pair<ll, int> > que;
    for (int i = 0; i < 100; i++) for (int j = 0; j < 100; j++) {
        d[i*100+j] = 0;
        que.push(make_pair(0ll, i*100+j));
    }
    while (!que.empty()) {
        auto p = que.top(); que.pop();
        int u = p.second;
        ll dist = -p.first;
        if (dist > d[u]) continue;
        for (edge e : G[u]) {
            if (d[e.v] > d[u]+e.w) {
                d[e.v] = d[u] + e.w;
                que.push(make_pair(-d[e.v], e.v));
            }
        }
    }
    return d;
}

bool ng[101][101][101];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int W, H, Q;
    cin >> W >> H >> Q;
    assert(W <= 100 && H <= 100 && Q <= 100);
    vector<vector<edge> > G(1011000);
    int maxt = 0;
    for (int i = 0; i < Q; i++) {
        int t, d, x;
        cin >> t >> d >> x;
        x--;
        maxt = max(maxt, t);
        if (d == 0) {
            for (int j = 0; j < H; j++) ng[t][x][j] = true;
        } else {
            for (int j = 0; j < W; j++) ng[t][j][x] = true;
        }
    }
    // 同じ時間との辺
    for (int t = 0; t <= maxt; t++) {
        for (int x = 0; x < W; x++) {
            for (int y = 0; y < H; y++) {
                for (int i = 0; i < 4; i++) {
                    int nx = x+dx[i], ny = y+dy[i];
                    if (nx < 0 || nx >= W || ny < 0 || ny >= H) continue;
                    G[t*10000+x*100+y].emplace_back(t*10000+nx*100+ny, 1);
                }
            }
        }
    }
    // 次の時間との辺
    for (int t = 1; t <= maxt; t++) {
        for (int x = 0; x < W; x++) for (int y = 0; y < H; y++) {
            if (!ng[t][x][y]) {
                G[(t-1)*10000+x*100+y].emplace_back(t*10000+x*100+y, 0);
            }
        }
    }
    auto d = dijkstra(1011000, G);
    ll ans = INF;
    for (int i = 0; i < W; i++) for (int j = 0; j < H; j++) {
        ans = min(ans, d[maxt*10000+i*100+j]);
    }
    if (ans == INF) ans = -1;
    cout << ans << endl;
    return 0;
}

満点解法

const int MAXT = 100000;
const int INF = 5e8;

int dp[MAXT];

int calc(int W, vector<vi> x) {
    for (int i = 0; i < MAXT; i++) dp[i] = 0;
    for (int t = 0; t < MAXT; t++) {
        sort(x[t].begin(), x[t].end());
        int n = x[t].size();
        for (int i = 0; i < n; i++) {
            int nx = x[t][i]+1;
            if (nx < W) dp[nx] = min(dp[nx], dp[x[t][i]]+1);
        }
        for (int i = n-1; i >= 0; i--) {
            int nx = x[t][i]-1;
            if (nx >= 0) dp[nx] = min(dp[nx], dp[x[t][i]]+1);
        }
        for (int i = 0; i < n; i++) dp[x[t][i]] = INF;
    }
    int ret = INF;
    for (int i = 0; i < W; i++) ret = min(ret, dp[i]);
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int W, H, Q;
    cin >> W >> H >> Q;
    vector<vector<int> > x(MAXT), y(MAXT);
    for (int i = 0; i < Q; i++) {
        int t, d, a;
        cin >> t >> d >> a;
        t--; a--;
        if (d == 0) x[t].push_back(a);
        else y[t].push_back(a);
    }
    int ans = calc(W, x) + calc(H, y);
    if (ans >= INF) ans = -1;
    cout << ans << endl;
    return 0;
}