AtCoder Regular Contest 044 - C ビーム

少しだけヒントを見てしまったが，面白かったので解説を書く．

arc044.contest.atcoder.jp

概要

レーザを避けるために必要な最小移動距離を求めよ．

考察

前提

『縦方向のレーザを左右に避ける』と『横方向のレーザを上下に避ける』は独立に考えることができる．

よって，『縦方向のレーザを左右に避ける』方法だけを考えればよい．

この辺りの説明は，解説スライドが簡潔で分かりやすい． https://www.slideshare.net/chokudai/arc044

dp

レーザ(time,pos)集合をあらかじめ昇順ソートしておく．

次のようなdp配列を定義する．

dp[x] = 座標xで生き残るために必要な移動回数

レーザが来た時にレーザを避けるようなイメージでdp配列を更新したい．

レーザは昇順にソートされているので，右(座標が増加する)方向に避けるdpの更新は，次のように書ける．シンプル．

dp[x + 1] = min(dp[x+1], dp[x] + 1)

左方向に避けるケースが厄介で，極太レーザをイメージすると分かりやすい．

left = # xより左のセルで，同時刻にレーザが来なかったセル #
dp[left] = min(dp[left], dp[x] + x-left)

leftを求めるには，レーザの左隣を調べて，そこにレーザが無ければleft = x-1と更新するようにするとうまくいく．

提出コード

Submission #1605326 - AtCoder Regular Contest 044 | AtCoder

例外処理が嫌いなので，セルを左右に2つ拡張している．

かなりすっきりしたと思うんだけれども，どうだろう・・・

ll width, height, n_q;

vector<pair<int, int>> q_rows;
vector<pair<int, int>> q_cols;

int main() {

    scanner >> width >> height >> n_q;

    q_rows.reserve(n_q + 5);
    q_cols.reserve(n_q + 5);

    repeat(i, n_q) {
        int t, d, x;
        scanner >> t >> d >> x;
        if (d == 0) {
            q_cols.emplace_back(t, x);
        }
        else {
            q_rows.emplace_back(t, x);
        }
    }

    sort(ALL(q_cols));
    sort(ALL(q_rows));

    ll answer = 0;
    {
        vector<ll> dp(width + 2, 0);
        vector<int> tm(width + 2, 0);
        int left = 0;
        for (auto q : q_cols) {
            int t = q.first;
            int x = q.second;
            
            if (tm[x-1] < t) {
                left = x-1;
            }
            {
                minset(dp[left], dp[x] + x-left); // 左に避ける
                minset(dp[x + 1], dp[x] + 1); // 右に避ける
            }
            dp[x] = 5e15;
            tm[x] = t;
            //debugv(dp);
        }
        dp.front() = dp.back() = 5e15;
        answer += *min_element(ALL(dp));
    }

    {
        vector<ll> dp(height + 2, 0);
        vector<int> tm(height + 2, 0);
        int left = 0;
        for (auto q : q_rows) {
            int t = q.first;
            int x = q.second;
            
            if (tm[x-1] < t) {
                left = x-1;
            }
            {
                minset(dp[left], dp[x] + x-left); // 上に避ける
                minset(dp[x + 1], dp[x] + 1); // 下に避ける
            }
            dp[x] = 5e15;
            tm[x] = t;
            //debugv(dp);
        }
        dp.front() = dp.back() = 5e15;
        answer += *min_element(ALL(dp));
    }

    if (answer > 1e15) {
        cout << -1 << endl;
    }
    else {
        cout << answer << endl;
    }


    return 0;
}