AtCoder Regular Contest 044 C - ビーム

問題

　 $H\times W$ $(H, W\le 10^5)$ のグリッドにビームが飛んでくる。ビームは時刻 $t$ に縦方向あるいは横方向についてあるマスを通るように飛ぶ。高橋君は任意のマスからスタートして上下左右のマスについて単位時間に任意の回数移動できる。全てのビームについての情報がわかっているとき、全てのビームを避ける最小の移動回数を求めよ。

解法

　 $X$ 軸方向と $Y$ 軸方向はそれぞれ独立に考えて良い。各軸について、それぞれ時刻 $i$ に座標 $j$ にいるときの最小移動回数を求めればよいが、これは愚直にDPで求めると $O(T(H + W))$ かかってしまう。

　各時刻でビームが飛んでくる状況を考えると、そのマスから移動することにより左右のマスに配るようなDPをすればよいことがわかる。隣接マスにもビームが飛んできている可能性があるため、まず各時刻におけるビームが来る座標をソートしておいて、小さい方から見ていき大きい方へ避ける移動、大きい方から見ていき小さい方へ避ける移動をそれぞれ遷移させていく必要がある。これによって各時刻について全ての座標を見る必要がなくなり、飛んでくるビームの本数にのみ依存するようになるので計算量は $O(W+H+T)$ でこの問題が解ける。

反省

　1時間54分(4WA)でAC。1時間考えてもさっぱり歯が立たない感じだったので解説スライドを見た。各軸は独立に考えて良いという発想は、それぞれ行と列を考えてminを取れば全ての座標について求まるのか？くらいには思っていたが、完全に独立に考えて良いというところまでは至っていなかった。

　解説を読んでからもDPの遷移を書くのが結構大変で、WAをたくさん出してしまった。自分の実装だとソートをする(setを使う)要素があるので計算量は $O(W+H+T + Q\log{Q})$ になっているのかな？制約が一段緩くてもこの問題を解けたかどうか……。しかし座標を一つ一つ考えることすらできない制約なわけだから、独立になっていそうと思うのは当たり前なんだろうなぁ。そしてそれを確認するのも上手くできるようにならなくては。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll W, H, Q;
    cin >> W >> H >> Q;

    constexpr ll T_MAX = (ll)1e5 + 1;
    //beams[i][j] := 時刻iに方向jのビームが来る座標
    vector<vector<set<ll>>> beams(T_MAX, vector<set<ll>>(2));
    for (ll i = 0; i < Q; i++) {
        ll T, D, X;
        cin >> T >> D >> X;
        beams[T][D].insert(X);
    }

    constexpr ll INF = INT_MAX;

    ll ans = 0;

    for (ll d = 0; d < 2; d++) {
        //縦方向,横方向それぞれについて考える
        const ll MAX = (d == 0 ? W : H);

        //dp[j] := (時刻iに)座標jにいるときの移動距離の最小値
        vector<ll> dp(MAX + 2, 0);

        //番兵
        dp[0] = dp[MAX + 1] = INF;

        for (ll i = 0; i < T_MAX; i++) {
            //順方向に避ける
            for (auto itr = beams[i][d].begin(); itr != beams[i][d].end(); itr++) {
                dp[*itr + 1] = min(dp[*itr + 1], dp[*itr] + 1);
            }
            //逆向きに避ける
            for (auto itr = beams[i][d].rbegin(); itr != beams[i][d].rend(); itr++) {
                dp[*itr - 1] = min(dp[*itr - 1], dp[*itr] + 1);
            }
            for (ll a : beams[i][d]) {
                dp[a] = INF;
            }
        }

        ans += *min_element(dp.begin() + 1, dp.end() - 1);
    }

    cout << (ans >= INF ? -1 : ans) << endl;
}