ABC135-E †Golf†を通した話
こんにちは。おぉ味噌汁。です。
2021 年 3 月 27 日、ABC-E最難関として名高い Golf を AC しました。
私のツイート↓（一部）
数日かけて数時間考察してようやく解けて、とても嬉しかったので、こうしてブログにしています。
問題概要はこんな感じです。
- 二次元格子上でゴルフをする。
- ボールは最初 $(0,0)$ にあり、一打毎に、マンハッタン距離が ぴったり $K$ の点にボールを動かせる。
- ボールを $(X,Y)$ に動かすまでにかかる打数の最小値と、それを満たす適当な 過程 を求めなさい。（不可能な場合はそれを報告しなさい。）
はい。色々とツッコミどころはありますが、（ぴったり $K$ でゴルフやっていけると思いますか？僕は思いません。）とりあえず考えていきましょう。
- $[1]$ $(0,0) → (X,Y)$ が不可能な場合
これは、まだ簡単です。
例えば、$X = 1 , Y = 2 , K = 2$ の時、不可能です。
なぜなら、動かす距離は毎回 $K$ で、 その $K$ が偶数ならば、各打毎に動かした距離の和及び $(0,0)$ からの距離は偶数にしかなりえず、$(1,2)$ という $(0,0)$ からのマンハッタン距離が奇数の点には動かすことができないからです。
まとめると、$Kが偶数 かつ (|X|+|Y|)が奇数$ の時、不可能です。実装↓（コードをそのままコピペすると改行がおかしくなるので画像です。）
実は、それ以外の時は可能です。
これ以降、一打ごとにボールの座標を $(nx,ny)$ とし、
$$ dx = abs(X-nx) , dy = abs(Y-ny) $$
$$ dist = abs(X-nx)+abs(Y-ny)$$ とします。
また、便宜上、$X ≥ 0 , Y ≥ 0$ に変換しておきます。（例えば、$X$ が負なら、$-1$ を掛けるとできます。そうしたところで、途中の座標も同様に $-1$ を掛けてしまえばよいので、そこまで問題ではないです。）
- $[2]$ $dist \% K == 0$ の場合
これもまだ簡単です。
$dist \% K == 0$ より、$dist/K$ 打でちょうどゴールできます。
実装方針には色々あると思われますが、私は $x$座標をまず揃えて、そのあと $y$座標を揃えるという方針でやりました。（これ以降の実装方針もこんな感じです。）
実装↓（冗長です、すみません…）
さて、ここからが†本番†です。
Golfくん「おっしゃ本気出すで～～～～～！！！！＾＾」
- $[3]$ $dist \% K ≠ 0$ の場合
どうしましょう。困りました。
この場合、てきとーに動いて $dist / K$ 打でゴール、というのができません。
なので、 $dist / K$ $+ a$ 打でゴールするとして、 $a$ が最小になるようにゴールしたいですね。
どうしましょう。
とりあえず、$dist \% 2 == 0$ の時を考えてみましょう。（Kの偶奇によらず、なんか良さそうじゃないですか？）
- $[3-1]$ $dist \% 2 == 0 かつ dist \% K ≠ 0 $ の場合
$dist \% K == 0$ の場合のように動いてしまうと、$ b = K- dist\%K > 0 $ だけ、オーバーしてしまいます。
ここで、$b$ の偶奇に注目してみましょう。なんと $b \% 2 == 0$ です！
つまり「いい感じに」寄り道をするとゴールできます！
ちょっと希望の光が見えてきました。
ここで注意したいのは、その寄り道を始めるタイミングです。
$dx+dy < K$ の時やればいいではないかと思ってしまいますが、$K < dist < 2*K$ の時やった方が、1打少なくなります。
そのように考えると、次の図のように動きたくなります。
$K < dx+dy < 2*K$ の状態の $(nx,ny)$ を考えます。
赤部分で止まり、次の打で $(X,Y)$ に到達しようという算段です。
$$ dx+m+n = dy-n+m = K $$ を解いて、
$$ n = \frac{dy-dx}{2} , m = K-\frac{dy+dx}{2} $$
となります。この時、$dy≥dx$ ですから、$n,m$ は共に正となり、セーフです。
同様にして、 $dy ≤ dx$ の場合についても考えると、
$$ dy+m+n = dx-n+m = K $$ を解いて、
$$ n = \frac{dx-dy}{2} , m = K-\frac{dx+dy}{2} $$
よって、$K < dist < 2*K$ の状況に $(nx,ny)$ を動かしたとき、上のように動かせば、$+2$ 打でゴールできます。
実装↓（$K < dist < 2*K$ の実装がだるいのですが、汚いので載せません。（は？））
配列OUTPUTに、出力する $(nx,ny)$ を保存しています。
ふぅ…。疲れましたが、まだこの問題は終わっていません。
最後の場合分けです。
- $[3-2]$ $dist \% 2 == 1 かつ dist \% K ≠ 0 $ の場合
どうしましょう…。困りました。Golf くんが悪魔の笑みを浮かべています。
ちなみに、この時、$dist \% 2 == 1$ より、$K \% 2 == 1$ です。（$0$ なら不可能）
いやもう無理だろこれ
さっきみたいに動かそうと思っても変数多すぎるし
はいはい Golf くんの勝ちですよ
どうせ私はまた通せないんでｓあれ？
$dist \% 2 == 1 かつ K \% 2 == 1$ ということは $2*K < dist または dist < K $ の状態から1打を「いい感じ」に動かして $K < dist < 2*K$ に残り $2$ 打の状態にすれば $dist \% 2 == 0$ で $[3-1]$ に帰着できる…？いやできるわ！勝った！
というわけで、$2*K < dist$ の状態で止めて、そこから $+3$ 打でゴールすることが可能だということが分かりました。
ちょっと待って
$ 2*K < dist $ の状態から $K < dist < 2*K$ に必ずできるの？
…………
…………………
どうしよう…………………（おい）
またもや場合分けです。
- $[3-2-1]$ $dist < K $ の場合
これは簡単です。
$x$ または $y$ の負の方向に $K$ 動かせば $ K < dist < 2*K $ となり、OKです。（$X ≥ 0 , Y ≥ 0$ としているので、オーバーしていない限りゴール必ずは正の方向にある。）
実装↓
- $[3-2-2]$ $ 2*K < dist $ の場合
これもまだ簡単です。
$x$ または $y$ の正の方向に $K$ 動かします。すると、 $K < dist < 2*K$ となり、OKです。
しかし、注意すべきなのは、正の方向に $K$ 動かす際、$X,Y$ をそれぞれオーバーしないように動く必要があります。（オーバーすると $dist$ がその分増えてしまうため）
実装↓
- $[3-2-3]$ $ K < dist < 2*K $ の場合
ちょっと困りますが、ここも場合分けです。（場合分けの数が多すぎませんか？ごめんなさい………）
- $[3-2-3-1]$ $ dist == (2*K)-1 $ の場合
右端のケースです。この場合、$dist$ が 一打後に $+1$ または $-K$ されてしまうとダメです。
何とかして回避しましょう。
説明するのが面倒になってきました。（は？）
実装↓（+1しちゃダメ というコメントは、「一打後に $dist$ が+1以上されていてはダメ」という意味です。）
こんな感じにすると良いです。
結局は、$(正の方向に進む距離) > (負の方向に進む距離)$ になっている かつ $1$ 以上は負の方向に進む ことをすればよいです。
- $[3-2-3-2]$ $ dist == K+1 $ の場合
左端のケースです。これは、$$[3-2-3-1]$$ と反対な感じでやると良いです。つまり、
$(正の方向に進む距離) < (負の方向に進む距離)$ になっている かつ $1$ 以上は正の方向に進む ことをすればよいです。
実装↓
- $[3-2-3-3]$ $ dist ≠ K+1 かつ dist ≠ (2*K)-1 $ の場合
これは $[3-2-3-1],[3-2-3-2]$ に比べれば楽です。
$dx < dy$ の時、$dy > \frac{K}{2}+1$ なので、$y$ の正の方向に $\frac{K}{2}+1$ だけ動かしてもオーバーしません。よって、$y$の正の方向に $\frac{K}{2}+1$ 、$x$ の負の方向に $\frac{K}{2}$ （$K$ は奇数なので割る2は切り捨てて考えます）動かすことで、1手動かした後でも $ K < dist < 2*K $ を保つことができます。
$dx > dy$ の時も同様にして、 $x$の正の方向に $\frac{K}{2}+1$ 、$y$ の負の方向に $\frac{K}{2}$ 動かすことで、1手動かした後でも $ K < dist < 2*K $ を保つことができます。
実装↓
これで1打調節が正常に終わりました！！！！！！！！！！
ふはは、ついにお前を倒す時が来たようだなぁ？ Golf クンよぉ！
これで $[3-1]$ に帰着できました！きちゃ！（きちゃく だけに）
あとは $[3-1]$ と同じことをやればよいです！
残りの実装↓
これで全ての場合を計算することができました！！！！
あとは $X,Y$ を負から正に直したなら出力時に $-1$ を掛けるのを忘れないようにします！
これでコードは完成しました。
渾身のコードを提出するときがやってきました。
うおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおお
「」
`＿ (三|
|ﾋ_) ／￣￣＼ LﾆO
| | ／●) (●)＼ ｜｜
|_|( (_人_) )∧亅
| ヽ＼ ￣ ＿／ ミﾉ
ヽﾉﾉ￣|ﾚ―-ｲ / ﾉ ／
＼ ヽ＼ |/ イ
／￣二二二二二二＼
`｜答｜ AC ｜｜
＼＿二二二二二二／
完
自己満足な記事でしたがここまで読んでくれた方がいれば嬉しいです。
ありがとうございました。
提出したコード(AC)
AC後に解説見ても天才すぎて意味が分からなかった話は黙っておきます
