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: