怒りの場合分け。ちょっと苦手系だけど一発 AC できてよかった。

問題へのリンク

問題概要

高橋君は現在 $(X_{A}, Y_{A})$ にいて、荷物は $(X_{B}, Y_{B})$ にあり、荷物を目的地 $(X_{C}, Y_{C})$ に届けたい。

高橋君は荷物のある位置に入ることはできず、荷物と隣接した状態から荷物の方向に移動すると、荷物を押すことができる (荷物は座標 1 だけ動き、高橋君は荷物のあった位置に移動する)。

高橋君が目的を達成するための最小手数を求めよ。

制約

座標値の絶対値は $10^{17}$ 以下

考えたこと

場合分けが辛そう。最悪 WA ラッシュになったら、愚直解と比較するのをやろうと考えながら場合分けを試みた。

まずよくあるテクだが、高橋君・荷物・目的地を平行移動することで、高橋君の現在地が原点であるようにした (editorial では目的地の方を原点にしていたが一緒)。

さて、大まかな方針として

荷物の x 座標を目的地に合わせてから、y 座標の目的地を合わせる
荷物の y 座標を目的地に合わせてから、x 座標の目的地を合わせる

の 2 通りがあると考えた。それ以外の余計な営みは余計だろうと (editorial にちゃんと証明があった)。最初は、もっと都合がよく、どっちの座標軸から先に合わせても答えは一緒になるのでは......などと考えたが、入力例 1 の時点でそうではなかった。

それでも、1. を実施する関数を書いておけば、x 座標と y 座標を入れ替えてその関数を呼び出すことで 2. も調べられる。結局、1. だけを考えればよい。

x 座標を合わせる

次の 2 ステップを踏む。

高橋君が適切な位置に回り込む
押す

1 については、高橋君、荷物、目的地の x 座標の大小関係に応じて、色々状況が変わるが、次のように整理できる。「回り込むムーブ」が紛らわしい。

のとき：
- 高橋君は $(X_{B}-1, Y_{B})$ に移動する
- それに必要な手数は $|X_{B} - 1| + |Y_{B}|$ となる
- ただし、 $Y_{B} = 0$ かつ $X_{B} \lt 0$ のとは回り込むムーブが必要で、2 手余分にかかる
のとき：
- 高橋君は $(X_{B}+1, Y_{B})$ に移動する
- それに必要な手数は $|X_{B} + 1| + |Y_{B}|$ となる
- ただし、 $Y_{B} = 0$ かつ $X_{B} \gt 0$ のとは回り込むムーブが必要で、2 手余分にかかる

そしてこの操作の後、ステップ 2 の荷物を押していくのに必要な作業量は

$|X_{B} - X_{C}|$

と求められる。

y 座標を合わせる

もともと一致していればすでに目的は達成している。一致していない場合は、

高橋君が回り込む
押す

というステップを踏む。今回は、荷物と目的地の y 座標の場合分けは不要。回り込むのに 2 手、押すのに $|Y_{b} - Y_{C}|$ 手なので、必要な手数は

$|Y_{b} - Y_{c}| + 2$

となる。

計算量

以上を整理すると、次のコードのように実装できる。計算量は $O(1)$ となる

コード

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

// 先に x 座標を合わせてから、y 座標を合わせる場合の最小手数を求める
long long sub(long long xb, long long yb, long long xc, long long yc) {
    long long res = 0;
    
    // x 座標を合わせる
    if (xb < xc) {
        // (xb-1, yb) に移動する
        if (yb == 0 && xb < 0) {
            // 上下の 1 マス移動が必要
            res += abs(xb-1) + abs(yb) + 2;
        } else {
            // 不要
            res += abs(xb-1) + abs(yb);
        }
        
        // (xc, yb) に運ぶ
        res += abs(xb - xc);
    } else {
        // (xb+1, yb) に移動する
        if (yb == 0 && xb > 0) {
            // 上下の 1 マス移動が必要
            res += abs(xb+1) + abs(yb) + 2;
        } else {
            // 不要
            res += abs(xb+1) + abs(yb);
        }
        
        // (xc, yb) に運ぶ
        res += abs(xb - xc);
    }

    // y 座標を合わせる
    if (yb != yc) {
        // 位置合わせ
        res += 2;
        
        // 運ぶ
        res += abs(yb - yc);
    }
    return res;
}

int main() {
    long long xa, ya, xb, yb, xc, yc;
    cin >> xa >> ya >> xb >> yb >> xc >> yc;
    
    // スタートを 0 にする
    xb -= xa, yb -= ya, xc -= xa, yc -= ya;
    
    // x 座標から y 座標をする場合と、y 座標から x 座標をする場合を探索
    long long res = min(sub(xb, yb, xc, yc), sub(yb, xb, yc, xc));
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 323 F - Push and Carry (水色, 525 点)

問題概要

制約

考えたこと

x 座標を合わせる

y 座標を合わせる

計算量

コード