【AtCoder】ABC289 F問題 解説(ゴリ押し解法)

# 今回の注意
レート黄色レベルの問題を、緑の実力の自分がごり押しで解けたのでうれしくなって書きます。
公式の解説の方が100倍くらい簡潔なため、時間のない方はそちらへどうぞ。
# 問題
長方形内の格子点に対する対象移動を繰り返して、$s$から$t$に移動できるかという問題。

https://atcoder.jp/contests/abc289/tasks/abc289_f

# 性質
問題の性質を、思考の順番に沿って考えてみましょう。$x$座標と$y$座標は完全に独立しているため、$x$座標のみにしぼって性質を考えます。
## 性質1. 偶数回移動と奇数回移動
ある点$s$から$t$への移動を考えてみることにします。まず、$s_x$から$x$座標が$p_{0x}$の点に対して対象移動させたら$t_x$にたどりつくとするとします。この時の関係式は
- $t_x$ = $2p_{0x}$ - $s_x$

で記述することができます。中学数学の範囲ですね。これを変形すると、
- $t_x$ + $s_x$= $2p_{0x}$ 

となります。注目すべき点は、$t_x$と$s_x$の和の形で、関係式が記述されるということです。
では、$p_{0x}$の点に対する対象移動に加えて、さらに$x$座標が$p_{1x}$の点に対して対象移動させてようやく$t_x$にたどりつくとすればどうなるでしょうか。過程は省略しますが、
- $t_x$ = $2p_{1x}$ - $2p_{0x}$ + $s_x$

となり、変形すると、
- $t_x$  - $s_x$= $2p_{1x}$ - $2p_{0x}$


となります。今回の場合だと、$t_x$と$s_x$の差の形で、関係式が記述されるのがわかります。

3回の対象移動、4回の対象移動を具体的に考えてみると分かるのですが、どうやら以下の性質がいえそうです。
- **奇数回移動 : $t_x$と$s_x$の和の形で、関係式が記述される**
- **偶数回移動 : $t_x$と$s_x$の差の形で、関係式が記述される**

では、奇数回移動と偶数回移動のそれぞれで、関係式を一般化することを考えてみます。具体例を考えてみればすぐに導出することができます。奇数回移動の場合は、
- $t_x$ + $s_x$= $2p_{2nx}$ - $2p_{(2n-1)x}$ + ...  + $2p_{2x}$ - $2p_{1x}$ +$2p_{0x}$ 

となり、まとめると、
```math
t_x + s_x= \sum_{i=1}^{n}2(p_{2ix}-p_{(2i-1)x})  +  2p_{0x}
```
となることが分かります。偶数回移動の場合には、
```math
t_x - s_x= \sum_{i=1}^{n}2(p_{2ix}-p_{(2i-1)x})
```
となることが分かります。

## 性質2. 始点と終点の座標の和または差は必ず偶数になる必要がある
これは、性質1の一般式を見れば一発で分かります。入力の後に
```cpp
if ((sx + tx) % 2 == 1 || ((sy + ty) % 2 == 1)) {
		cout << "No" << endl; return 0;
	}
```
を入れているのは、この性質のためです。

## 性質3. a=bのとき関係式は限定される。
$a=b$のとき、性質1の一般式のシグマの部分は、任意の$p$が$p=a(=b)$となるため$0$になります。したがって、$s_x$と$t_x$の関係式は、
- 奇数回移動 : $t_x + s_x= 2a$
- 偶数回移動 : $s_x = t_x$

の2パターンしか存在しえないことが分かります。

## 性質4. aで対象移動→bで対象移動すれば、2(b-a)移動できる
性質1の一般式のシグマ部分に注目します。シグマ部分中の1回の操作、即ち
- $2(p_{2ix}-p_{(2i-1)x})$

は、**2回の連続した対象移動がワンセットになった操作**とみることができます。1回の操作による移動量を最大にするためには、まず$a$で対象移動し、次に$b$で対象移動させます。そうすることで、$2(b-a)$移動させることができます。


# 解答の方針

この辺まで来たら回答の方針が思いつきます。
- 1. 性質2を満たさないならNo
- 2. 性質3に該当するなら特有の処理を与える。限定された関係式を満たさないならNo
- 3. 奇数回処理か偶数回処理化で場合分け
- 4. $x,y$に対し、片方偶数回、片方奇数回ならNo

コードのひな型は以下のようになります。
```java
int main() {
	if (性質2を満たさない) {
		cout << "No" << endl; return 0;
	}
	//zeroflag
	if (性質3,つまりa=b) {
		if (関係式1) {
			//処理
		}
		else if ((関係式2) {
			//処理
		}
		else {
			cout << "No" << endl; return 0;
		}
	}

	if (x,yともに偶数回操作) {
		if (a=bでない) {
			//処理
		}
		if (c=dでない) {
            //処理
		}
	}
	else if (x,yともに奇数回操作) {
		if (a=bでない) {
			//処理
		}
		if (c=dでない) {
            //処理
		}
	}
	else {//不可能操作
		cout << "No" << endl; return 0;
	}

	//出力部分

	return 0;
}
```

# 実装しながら考えたこと
## 1. 性質2,3を満たすなら、最大回数近く対象移動させればなんとかなりそう
性質2,3を満たしていて、対象移動で最も回数がかかりそうなのはどんな時かと考えると、$b$と$a$の差が最も小さく、$s_x$と$t_x$の差が最も大きいときになります。$b$と$a$の差が最も小さくなるのは差が1の時で、$s_x$と$t_x$の最も大きい差は、問題の条件によると$2×10^5$です。これを加味すると、$2×10^5$回移動させると、どれだけ$s$と$t$が離れていても移動させることができそうですね。

## 2. a→b→a→...と移動させるときの「あまり」をどうするか
$a→b$と移動させることで、常に最大の移動量$2(b-a)$を得ることができますが、この移動だけで$s$から$t$へ到達できるわけではないですね。その時の「あまり」に相当する量を
```cpp
long long mod_x = (tx - sx) % (2 * (b - a)); mod_x /= 2;
```
で定義します。正直、この``mod_x``の処理がこのゴリ押し解放の肝です。
``mod_x``が長方形内部に含まれてくれれば、話はカンタンなのです。なぜなら座標が``mod_x``の点を選択して対象移動させればそれだけで完了するからです。しかし、当然ながら``mod_x``が$a$より小さくなる可能性もあります($b$より大きくなる可能性はありません)。その時の処理を、偶数回移動のときと奇数回移動の時にわけて考えてみることにしましょう。

## 3. 偶数回移動のときの「あまり」の処理
偶数回移動の時はかなり簡単です。``mod_x``は絶対に$b-a$より小さい数なので、
- $b-mod_x$　→　$b$

とすれば、$b-mod_x$は絶対に長方形内部に含まれる点となるため、これであまり分の変化を得ることができます。

## 4. 奇数回移動のときの「あまり」の処理
「あまり」を、なんとかして絶対に長方形内部に含まれる点のみでの奇数回移動で処理させる方法を考えます。これには、対象移動における以下の2つの性質を用います。
- $p→q→q→p$と対象移動させればもとの点に戻る。
- $p-q+r$と移動させるのと、$r→q→p$と移動させるのでは、到達点は同じ

これは色々と考えるうちに発見した性質です。実際に書いて考えるとこれが正しいことが分かります。これらの性質を用いることで「``mod_x``で対象移動」という操作を、等価に置き換えることができます。
- ``mod_x``で対象移動
=$a→b→b→a→$``mod_x``で対象移動
=$a→b→$``mod_x``$-a+b$で対象移動

これを複数回考えることで、結局
- $a→b$の移動を$n$回して、``mod_x``+$n(b-a)$で対象移動

させる操作が等価になることが分かります。処理としては``mod_x``が$a$よりも大きくなるまで、$b-a$を足し続け、足した分だけあとで$a→b$の操作によって戻す、ということをすれば良いです。
これで生じる戻す操作の最大回数は${max(a)/min 2(b-a)} * 2 = 2×10^5$となるので、移動の最大回数を加味しても$10^6$回以内という制約には引っかからないことが分かります。


# 解答コード
最大回数近くまでは対象移動させるという方針をとりました。早期に$t$に到達してしまった場合、あまりの回数は同じ点で対象移動させてればいいですね。
``zeroflag``で、$a=b$となったときの処理を管理します。$t_x = s_x$の時はずっと同じ点で偶数回移動すればいいし、$t_x + s_x = 2p$の時は同じ点で奇数回移動すればいいです。
計算量としては、結局出力部分が最大になって$O(10^6)$です。メモリ制限は$1024$MBもあるので特に心配いりません。
```cpp
const ll maxi = 990000;
vector<ll> vec_x, vec_y;

int main() {
	ll sx, sy, tx, ty; cin >> sx >> sy >> tx >> ty;
	ll a, b, c, d; cin >> a >> b >> c >> d;

	//偶数回移動
	int zeroflag_x = 0, zeroflag_y = 0;
	if ((sx + tx) % 2 == 1 || ((sy + ty) % 2 == 1)) {
		cout << "No" << endl; return 0;
	}
	//zeroflag
	if (b == a) {
		if (tx == sx) {
			zeroflag_x = 1;
			repl(i, maxi) vec_x.push_back(a);
		}
		else if ((tx + sx) == 2 * a) {
			zeroflag_x = 2;
			repl(i, maxi - 1) vec_x.push_back(a);
		}
		else {
			cout << "No" << endl; return 0;
		}
	}
	if (d == c) {
		if (ty == sy) {
			zeroflag_y = 1;
			repl(i, maxi) vec_y.push_back(d);
		}
		else if ((ty + sy) == 2 * d) {
			zeroflag_y = 2;
			repl(i, maxi - 1) vec_y.push_back(d);
		}
		else {
			cout << "No" << endl; return 0;
		}
	}

	if ((zeroflag_x == 0 || zeroflag_x == 1) && (zeroflag_y == 0 || zeroflag_y == 1)) {//偶数回操作
		if (zeroflag_x == 0) {
			if (tx >= sx) {
				ll move_x = (tx - sx) / (2 * (b - a));
				ll mod_x = (tx - sx) % (2 * (b - a)); mod_x /= 2;
				ll remain_x = maxi - 2 - 2 * move_x;
				repl(i, move_x) {
					vec_x.push_back(a); vec_x.push_back(b);
				}
				vec_x.push_back(b - mod_x);
				vec_x.push_back(b);
				repl(i, remain_x) {
					vec_x.push_back(b);
				}
			}
			else {
				ll move_x = (sx - tx) / (2 * (b - a));
				ll mod_x = (sx - tx) % (2 * (b - a)); mod_x /= 2;
				ll remain_x = maxi - 2 - 2 * move_x;
				repl(i, move_x) {
					vec_x.push_back(b); vec_x.push_back(a);
				}
				vec_x.push_back(b);
				vec_x.push_back(b - mod_x);
				repl(i, remain_x) {
					vec_x.push_back(b);
				}
			}
		}
		if (zeroflag_y == 0) {
			if (ty >= sy) {
				ll btoa_y = (ty - sy) / (2 * (d - c));
				ll mod_y = (ty - sy) % (2 * (d - c)); mod_y /= 2;
				ll remain = maxi - 2 - 2 * btoa_y;
				repl(i, btoa_y) {
					vec_y.push_back(c); vec_y.push_back(d);
				}
				vec_y.push_back(d - mod_y);
				vec_y.push_back(d);
				repl(i, remain) {
					vec_y.push_back(d);
				}
			}
			else {
				ll move_y = (sy - ty) / (2 * (d - c));
				ll mod_y = (sy - ty) % (2 * (d - c)); mod_y /= 2;
				ll remain = maxi - 2 - 2 * move_y;
				repl(i, move_y) {
					vec_y.push_back(d); vec_y.push_back(c);
				}
				vec_y.push_back(d);
				vec_y.push_back(d - mod_y);
				repl(i, remain) {
					vec_y.push_back(d);
				}
			}
		}
	}
	else if ((zeroflag_x == 0 || zeroflag_x == 2) && (zeroflag_y == 0 || zeroflag_y == 2)) {//奇数回操作
		if (zeroflag_x == 0) {
			ll move_x = (tx + sx) / (2 * (b - a));
			ll mod_x = (tx + sx) % (2 * (b - a)); mod_x /= 2;
			ll count_x = 0;
			while (mod_x < a) {
				mod_x += b - a; count_x += (ll)1;
			}
			ll remain = maxi - 1 - 1 - 2 * move_x - 2 * count_x;
			vec_x.push_back(mod_x);
			repl(i, move_x) {
				vec_x.push_back(a); vec_x.push_back(b);
			}
			repl(i, count_x) {
				vec_x.push_back(b); vec_x.push_back(a);
			}
			repl(i, remain) {
				vec_x.push_back(b);
			}
		}
		if (zeroflag_y == 0) {
			ll move_y = (ty + sy) / (2 * (d - c));
			ll mod_y = (ty + sy) % (2 * (d - c)); mod_y /= 2;
			ll count_y = 0;
			while (mod_y < c) {
				mod_y += d - c; count_y += (ll)1;
			}
			ll remain = maxi - 1 - 1 - 2 * move_y - 2 * count_y;
			vec_y.push_back(mod_y);
			repl(i, move_y) {
				vec_y.push_back(c); vec_y.push_back(d);
			}
			repl(i, count_y) {
				vec_y.push_back(d); vec_y.push_back(c);
			}
			repl(i, remain) {
				vec_y.push_back(d);
			}
		}
	}
	else {//不可能操作
		cout << "No" << endl; return 0;
	}

	cout << "Yes" << endl;
	rep(i, vec_x.size()) {
		cout << vec_x[i] << " " << vec_y[i] << endl;
	}

	return 0;
}
```