僕はめっちゃめんどい言い換えをして、めっちゃめんどい場合分けして無理矢理通した...
問題概要
二次元平面上の点 (0,0),(1,0),(0,1) に石がひとつずつ置かれています。
3 つの石が次の条件を満たしているとき、くの字に並んでいるといいます。
- どの石も、座標が整数である点に置かれている
- どの石も、別の石と隣接している（石からの距離が 1 である場所に別の石が存在する）
- 3 つの石が一直線上に存在しない
好きな石を 1 つ選んで好きな位置に移動させる操作を好きなだけできます。ただし、各操作後の石は、くの字に並んでいなければなりません。 できるだけ少ない操作回数で、石が点 (ax, ay), (bx, by), (cx, cy) にひとつずつ置かれている状態にしたいです。必要な操作回数は何回ですか？
制約
- (テストケース数)
- 各座標値の絶対値
考えたこと
とてもコーナーケースの多そうなややこしい問題だと思った。この手の問題は、「くの字」のままで考えると難しいので、なにかわかりやすい状態に言い換えてその遷移を考えればよいと思った (ここまでは OK)。僕はそこから
- くの次を 2 × 2 の正方形が 1 マス欠けたものだと思うことにする
- その正方形の重心の座標 (初期状態では (1, 1))
- その正方形のどのマスを欠くとくの字になるか (0, 1, 2, 3 の 4 状態、下図)
という 2 つの値によって表すことにした。
このような特徴づけを用いても一応解けた。しかし想定解法にあるように
- (ax + bx + cx, ay + by + cy)
によって完全に特徴付けられるので、これを用いるのが楽だったようだ。
僕の解法
まず、4 象限への移動をすべて考えるのはイヤだったので、適宜
- x 座標について対称変換
- y 座標について対称変換
- z 座標について対称変換
を行うことで、目指すべき移動ベクトル が
としてよいものとして考えることにした。このとき、初期状態の向きが必ずしも「1」とはならないことに注意しよう。
さて、このような前処理を行っておくと、基本的には「右移動」と「上移動」のみを繰り返しながら を目指せば良いことになる。このとき、くの字の向きの変化としてありうるパターンはつぎのようになる。
- 右方向への移動：0 → 1、0 → 3、2 → 1、2 → 3
- 上方向への移動：3 → 0、3 → 1、2 → 0、2 → 1
- 任意回転：(0, 1, 2, 3) → (0, 1, 2, 3)
上述の移動をそれぞれ 1 ステップとして、移動ベクトルは (x, y) を実現し、向きの変化は初期状態 s から終端状態 g になるように、最小手数で実現する問題となる。
地獄のような場合分けをすることで、次のコードで通せた。具体的には
- 最初の移動は右方向で、最後の移動も右方向 (
が必要)
- 最初の移動は右方向で、最後の移動は上方向 (
が必要)
- 最初の移動は上方向で、最後の移動は右方向 (
- 最初の移動は上方向で、最後の移動も上方向 (
が必要)
という 4 通りのパターンをすべて試して、その最小値を求めている。最初の移動ベクトルを固定すると、最初と最後にどのような回転が必要なのかが決まるので、それを足している。なお、「回転による向き合わせ」は最初と最後に押し付けてよくて、それ以外のところでは連続移動が可能なものと考えてよいことも頑張って示したりした。
#include <bits/stdc++.h> using namespace std; template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } int changeX(int dir) { vector<int> res = {1, 0, 3, 2}; return res[dir]; } int changeY(int dir) { vector<int> res = {2, 3, 0, 1}; return res[dir]; } int changeXY(int dir) { vector<int> res = {3, 1, 2, 0}; return res[dir]; } using pll = pair<long long, long long>; long long solve() { vector<long long> vx(3), vy(3); for (int i = 0; i < 3; ++i) cin >> vx[i] >> vy[i]; long long x = min({vx[0], vx[1], vx[2]}); long long y = min({vy[0], vy[1], vy[2]}); set<pll> se; for (int i = 0; i < 3; ++i) se.insert({vx[i], vy[i]}); int s = 1, g; if (!se.count({x, y})) g = 2; else if (!se.count({x+1, y})) g = 3; else if (!se.count({x, y+1})) g = 0; else g = 1; if (x < 0) x = -x, s = changeX(s), g = changeX(g); if (y < 0) y = -y, s = changeY(s), g = changeY(g); if (x > y) swap(x, y), s = changeXY(s), g = changeXY(g); if (x == 0 && y == 0) { if (s == g) return 0; else return 1; } if (x == 0 && y == 1) { long long res = 1; if (s != 2 && s != 3) ++res; if (g != 0 && g != 1) ++res; return res; } long long res = 1LL<<60; // - - if (x >= 2) { long long add = y - x + 1; if (s != 0 && s != 2) ++add; if (g != 1 && g != 3) ++add; chmin(res, x+y+add); } // - | if (x >= 1 && y >= 1) { long long add = y - x; if (s != 0 && s != 2) ++add; if (g != 0 && g != 1) ++add; chmin(res, x+y+add); } // | - if (x >= 1 && y >= 1) { long long add = y - x; if (s != 2 && s != 3) ++add; if (g != 1 && g != 3) ++add; chmin(res, x+y+add); } // | | if (y >= 2) { long long add = abs(y - x - 1); if (s != 2 && s != 3) ++add; if (g != 0 && g != 1) ++add; chmin(res, x+y+add); } return res; } int main() { int T; cin >> T; while (T--) cout << solve() << endl; }
もうちょっとマシな解法
僕の考え方でも、もうちょっとマシになる。
- 向きを変えずに (+1, +1) という斜め移動は、2 回でできる
- 向きを変えずに (+1, 0) という斜め移動は、2 回でできる
ということを考える。座標 (x, y) が十分遠いとき、状態を (x, y, s) (s: 向き) と表したとき、
(x, y, s) への最小回数 = (x - 1, y - 1, s) への最小回数 + 2
になりそうだという直感が働く (斜め移動は 2 回でできることはもろに考察に生かしていた)。さらにこれによって y - 1 が十分小さくなったとき
(x, y, s) への最小回数 = (x, y - 1, s) への最小回数 + 2
という感じで移動させていって、最終的に BFS できる程度の領域まで持ってきて、BFS でトドメをさす。こんな感じでも AC になるっぽい！詳しくは解説放送より！
想定解法
想定解法では、状態の表現方法がそもそも違った。L 字をなす 3 マスの x 座標の総和と、y 座標の総和をペアで持つだけでよいのだ。だいぶわかりやすい！！！
たとえば x 座標の総和が 8 だとわかっていたならば、(2, ?), (3, ?), (3, ?) という形になっていることが確定する。7 だとわかっていたならば、(2, ?), (2, ?), (3, ?) となっていることが確定する。y 座標の情報とも合わせれば完全に確定する。つまり、x % 3 と y % 3 の値から、L 字の向きもわかるのだ。
この方法だと、いい感じに特徴付けられるっぽい。詳細は想定解法より！！！
