ABC135 E Golfのパターパート
・偶奇によってどうしようもないことがある。
・必要な手数は基本はceil(距離/K)で、偶奇によって+1が必要なことがある。
・残り2手までは適当に近づく。
あたりは一旦いいとして
・今いる地点と目標地点の距離が2K以下
・かつ偶数
のところから最後2手でどうやってカップインするかという話。
考察1
上の2条件が満たされているとき必ず2手でいける。
証明: そうじゃないと困る。
考察2
(X, Y) = (x+y, x-y) として座標変換(いわゆる45度回転)すると、(x,y) からマンハッタン距離がちょうどKであるような点の集合は変換後の座標では (X±K,Y±K ) の4点を頂点とする正方形になる。
証明: 略
以下では今いる地点を(x1, y1), ゴールを(x2, y2) とし、
2点の座標変換後の座標を(X1, Y1), (X2, Y2) とします。
また最初の2条件は満たされているものとします。
考察3
(X1, Y1), (X2, Y2) を中心とする2つの正方形が共有点をもつとき、
(Xi ± K, Yj ± K) と表すことのできる共有点が存在する。
証明: 共有点をもつ正方形の図をいくつか書くとわかる。
考察4
(Xi ± K, Yj ± K) と書ける点は逆変換でxy平面に戻しても格子点(xy座標がともに整数)である。
証明: 読者への演習問題とする。
つまり
①45度回転
②(Xi ± K, Yj ± K) と書ける頂点を全探索
③どれかが共有点になってる
④③を45度逆回転で戻した点はちゃんと元の座標でも格子点になってる。
⑤そこが最後から2手目で行くべき点である。
めでたしめでたし
まとめ
完全な解にはいたれなくても全探索等が現実的な時間に収まりそうなところまで持っていけたらあとはパソコンにやらせちゃうのはかなり有効(他の問題の例: AGC041-C, エクサウィザーズ2019-F)
