Official

I - Teleporter Takahashi Editorial by MMNMM


まず、問題を \(1\) 次元で考えてみます:

  • はじめ、高橋くんは数直線上の座標 \(s\) の位置にいます。 「\(a\leq x\leq b\) なる \(x\) を選んで、高橋くんを \(x\) と対称な位置へ移動させる」操作を繰り返して高橋くんを \(t\) へ移動させたいです。

\(x\) を選んで操作すると点 \(p\) にいる高橋くんは \(2x-p\) へ移動します。 \(p\equiv2x-p\pmod2\) なので、\(s\not\equiv t\pmod2\) のとき、どうやっても \(s\) から \(t\) へ移動することはできません。 以下、\(s\equiv t\pmod2\) とします。

\(a=b\) のとき、\(s,2a-s\) にのみ移動できます。偶数回操作すると \(s\) に、奇数回操作すると \(2a-s\) に移動します。

\(a\neq b\) のとき、\(a,a+1\) の順に操作すると \(p\to p+2\) と移動することができます。\(a+1,a\) の順に操作すると \(p\to p-2\) と移動することができます。
\(s\equiv t\pmod2\) より、\(|s-t|\) 回の操作で \(s\) から \(t\) へ移動することができます。


\(2\) 次元の問題に戻ります。 \(s _ x\not\equiv t_x\pmod2\) もしくは \(s _ y\equiv t _ y\pmod2\) が必要です。

\(a=b\) もしくは \(c=d\) のとき、\(s,t\) の座標から操作を偶数回するか奇数回するかが決まります。

  • \(a=b\) かつ \(t _ x\notin\{s _ x,2a-s _ x\}\)
  • \(c=d\) かつ \(t _ y\notin\{s _ y,2c-s _ y\}\)
  • \(a=b\) かつ \(c=d\) かつ \(t _ x=s _ x\) かつ \(t _ y = 2c-s _ y\)
  • \(a=b\) かつ \(c=d\) かつ \(t _ x=2a-s _ x\) かつ \(t _ y = s _ y\)

のいずれかのとき、答えは No です。

操作を偶数回すると決まる場合、あるいはどちらとも決まらない場合、\(x\) 座標はすでに一致しているか \(2k\) だけ離れています。 \(x\) 座標が \(2k(\neq0)\) だけ離れている場合、\(a\lt b\) です。 このとき、\((a,c),(a+1,c)\) の順に操作すると \((p _ x,p _ y)\to(p _ x+2,p _ y)\) と移動することができます。 \((a+1,c),(a,c)\) の順に操作すると \((p _ x,p _ y)\to(p _ x-2,p _ y)\) と移動することができます。 よって、\(|s _ x-t _ x|\) 回の操作で高橋くんのいる位置の \(y\) 座標を変えないまま \(x\) 座標を \(s _ x\) と一致させることができます。

同様に、\(y\) 座標についても \((a,c),(a,c+1)\) や \((a,c+1),(a,c)\) のような操作を繰り返すことで高橋くんのいる位置の \(x\) 座標を変えないまま \(y\) 座標を \(s _ y\) と一致させることができます。

必要な操作回数は \(|s _ x-t _ x|+|s _ y+t _ y|\leq4\times10^5\lt10^6\) 回となり、十分小さいです。

操作を奇数回すると決まる場合、適当な点に対して操作をおこなっておくことで、偶数回の場合に帰着させることができます。 たとえば \((a,c)\) に対して操作を行うことにすると、全体で必要な操作回数は \(1+|(2a-s _ x)-t _ x|+|(2c-s _ y)-t _ y|\leq1+8\times10^5\lt10^6\) 回となり、解けました。

処理をまとめると次のようになります。

  • \(s _ x\) と \(t _ x\) 、\(s _ y\) と \(t _ y\) の偶奇のどちらかが一致していない場合、No
  • 次のいずれかの場合、No
    • \(a=b\) かつ \(t _ x\notin\{s _ x,2a-s _ x\}\)
    • \(c=d\) かつ \(t _ y\notin\{s _ y,2c-s _ y\}\)
    • \(a=b\) かつ \(c=d\) かつ \(t _ x=s _ x\) かつ \(t _ y = 2c-s _ y\)
    • \(a=b\) かつ \(c=d\) かつ \(t _ x=2a-s _ x\) かつ \(t _ y = s _ y\)
  • それ以外の場合、Yes
  • \(a=b\) かつ \(t _ x=2a-s _ x\) 、もしくは \(c=d\) かつ \(t _ y=2c-s _ y\) のとき、\((a,c)\) に対して操作を行う。
  • \(s _ x\neq t _ x\) なら、\((a,c),(a+1,c)\) もしくは \((a+1,c),(a,c)\) のうち適切なほうの操作を繰り返す。
  • \(s _ y\neq t _ y\) なら、\((a,c),(a,c+1)\) もしくは \((a,c+1),(a,c)\) のうち適切なほうの操作を繰り返す。

実装例は以下のようになります。 このような問題では、操作と出力をまとめて行う関数を定義しておくと、実装の見通しがよくなる場合があります。

(おまけ:最短の操作列も求めることができます。)

#include <iostream>

int main() {
    using namespace std;

    long sx, sy, tx, ty, a, b, c, d;
    cin >> sx >> sy >> tx >> ty >> a >> b >> c >> d;

    // それぞれの偶奇が一致していなければ No
    if ((sx ^ tx) % 2 != 0 || (sy ^ ty) % 2 != 0) {
        cout << "No" << endl;
        return 0;
    }

    // possible_0 : 偶数回でたどり着けるか
    // possible_1 : 奇数回でたどり着けるか
    bool possible_0{(a != b || sx == tx) && (c != d || sy == ty)};
    bool possible_1{(a != b || sx + tx == a + b) && (c != d || sy + ty == c + d)};

    // どちらでも無理なら、無理
    if (!possible_0 && !possible_1) {
        cout << "No" << endl;
        return 0;
    }

    // そうでなければ、可能
    cout << "Yes" << endl;

    // 操作を行う関数
    const auto instruction{[&sx, &sy](long x, long y){
        cout << x << " " << y << endl;
        sx = 2 * x - sx;
        sy = 2 * y - sy;
    }};

    // 偶数回では無理なら、適当に 1 回動かしておく
    if (!possible_0) instruction(a, c);

    // それぞれの座標に 2 ずつ動かして揃える
    while (sx < tx) { // x 座標を増やす
        instruction(a, c);
        instruction(a + 1, c);
    }
    while (sx > tx) { // x 座標を減らす
        instruction(a + 1, c);
        instruction(a, c);
    }
    while (sy < ty) { // y 座標を増やす
        instruction(a, c);
        instruction(a, c + 1);
    }
    while (sy > ty) { // y 座標を減らす
        instruction(a, c + 1);
        instruction(a, c);
    }

    return 0;
}

posted:
last update: