ARC044 C - ビーム

問題文

http://arc044.contest.atcoder.jp/tasks/arc044_c

解法

この問題のポイントは，独立した部分問題に分割してしまう，ということ．

よく考えると，縦方向の移動と横方向の移動は完全に独立して扱うことができることがわかる．
なので，問題を1次元の同一の問題を2つ解くだけに帰着させることができる．

1次元上で最小の移動回数を求めるには，DPをすればよい．
dp[i][j] := 時刻 i までみたときに位置 j にいるときの最小移動回数
とすると，W*T でだめ．
でも W や H が大きいときはレーザーはスカスカなので，dp[i + 1] はほとんど dp[i] と同じであることに注目する．
つまり，レーザーが来たところだけ更新すればOK．
レーザーが来たとき，各地点から左で一番安全なところか，右で一番安全なところに移動することになる．
これも右方向と左方向で別々に考えることができるので，レーザーが来た場所 x に対して dp[x + 1] = min(dp[x + 1], dp[x] + 1) などとしてやればよい．
各時刻の最後に dp[x] = INF として，その場所が使えないことを表現する．

ソースコード

#include <bits/stdc++.h>
using namespace std;

constexpr int INF = 1e9;

int solve(int M, map<int, vector<int>>& beam) {
    vector<int> res(M);
    for(auto& p : beam) {
        auto& b = p.second;
        sort(b.begin(), b.end());
        for(auto x : b) {
            if(x + 1 < M) {
                res[x + 1] = min(res[x + 1], res[x] + 1);
            }
        }
        for(int i = (int)b.size() - 1; i >= 0; --i) {
            if(b[i] - 1 >= 0) {
                res[b[i] - 1] = min(res[b[i] - 1], res[b[i]] + 1);
            }
        }
        for(auto x : b) {
            res[x] = INF;
        }
    }
    return *min_element(res.begin(), res.end());
}

int main() {
    int W, H, Q;
    cin >> W >> H >> Q;
    map<int, vector<int>> beam_y;
    map<int, vector<int>> beam_x;
    for(int i = 0; i < Q; ++i) {
        int t, d, x;
        cin >> t >> d >> x;
        if(d == 0) {
            beam_x[t].push_back(x - 1);
        } else {
            beam_y[t].push_back(x - 1);
        }
    }
    int yd = solve(H, beam_y);
    int xd = solve(W, beam_x);
    if(xd == INF || yd == INF) {
        cout << -1 << endl;
    } else {
        cout << yd + xd << endl;
    }
}

感想

マンハッタン距離の問題で，縦と横で独立な問題にできるっていうのはたまにあるらしい．
それ以外の問題でも有用な考え方だと思うし，使いこなせるように訓練が必要だなあ．