AtCoder Beginner Contest 135 E - Golf

解法

コの字の作り方を考えてみる

まずは考えやすい＆実装しやすいように座標変換をします。 $X, Y$ に負の値がある場合、符号反転させて両方とも非負としておきます。

始点 $(0, 0)$ から終点 $(X, Y)$ までボールが移動する軌道は、長さの総和が $K$ の倍数になっている必要があります。 $X+Y$ が $K$ で割り切れる場合は素直に最短距離を進めばよいです。そうでない場合はどこかで無駄な移動を挟まないといけません。ここで無駄に進んだぶんだけ必ず戻らなければいけないので、無駄な移動距離は必ず偶数である必要があります。

無駄な移動の取り方はどのようなものが良いでしょうか？色々なものが考えられますが、例えば以下のような軌道はほとんどの場合アウトです。

f:id:betrue12:20190728194707p:plain

1ステップでの移動が折り返すところをまたいでしまうと、そのステップの始点と終点のマンハッタン距離が $K$ になりません。こうならないようなもの、イメージとしては「ヘアピンカーブが急でないもの」を考えたいです。

以下はどうでしょうか。コの字を作ります。

f:id:betrue12:20190728195610p:plain

さっきより良さそうです。しかしこちらの場合も、1ステップの移動がコの字の3辺にまたがってしまうとアウトです。3辺にまたがりにくくするためには、2本目に通る横向きの辺は長いほうが嬉しそうです。

そこでまた座標変換をします。もし $X \lt Y$ であれば入れ替えて、常に $X \ge Y$ ということにします。そして図の向きにコの字を作ると、2本目に通る辺を長い方にできます。

より具体的にステップ数や長さを決めていき、これで大丈夫なのか計算していきます。

コの字：具体的に計算

まずはステップ数を決めましょう。ステップ数を $n$ とします。また $D = X+Y$ と置きます。こうすると無駄な移動距離は $nK - D$ と表せます。

もし単純な切り上げ、つまり $n = \lceil\frac{D}{K}\rceil$ ステップで移動することができれば理想です。ただし $n$ が以下の2つに当てはまる場合には実現できないので、その場合は $n$ を増やします。

まずは $\lceil\frac{D}{K}\rceil = 1$ になるとき、1ステップでの移動は $D = K$ である場合を除いて実現不可能です。この場合は $n$ をひとまず2に増やします。

次に、無駄な移動距離は偶数である必要があります。もし $nK - D$ が奇数になっている場合、もし $K$ が奇数であればステップ数を1増やすことで偶奇が変わります。もし $K$ が偶数であれば偶奇を変えることはできないので、 $n$ がいくつであっても実現不可能です。

これらの条件に従って $n$ を修正します。その結果、 $\lceil\frac{D}{K}\rceil = 1$ である場合は $n=2, 3$ のどちらかになり、そうでない場合は $n = \lceil\frac{D}{K}\rceil, \lceil\frac{D}{K}\rceil + 1$ のどちらかになります。

こうして決めた $n$ に対して、先ほどのコの字が構築できないか考えましょう。

f:id:betrue12:20190728202016p:plain

図中の長さ $a$ は無駄な移動距離の半分なので $a = \frac{nK - D}{2}$ です。このとき、3辺にまたがるようなステップがないか確かめましょう。結論から書くと、これは $\lceil\frac{D}{K}\rceil = 1$ かつ $n = 3$ の時を除いて大丈夫です。それを証明します。

$\lceil\frac{D}{K}\rceil = 1$ かつ $n = 3$ の時以外は $n \le \lceil\frac{D}{K}\rceil + 1 \lt \frac{D}{K} + 2$ なので、 $a \lt K$ が成り立ちます。そのため終点側から辿ると、必ず1ステップで右の辺は通り越して上の辺に掛かります。

ここで右の辺と上の辺の長さ合計が $K$ 以上であれば、左の辺に掛からないので大丈夫だと示せます。実際に計算すると $a + X = \frac{nK + (X-Y)}{2}$ となり、座標変換で $X \ge Y$ を保証したことと $n \ge 2$ であることから $a+X \ge K$ が示されます。

これで $\lceil\frac{D}{K}\rceil = 1$ かつ $n = 3$ の時を除いて構築可能であることが示されました。あとはこれを何とかします。

最後の詰め

$\lceil\frac{D}{K}\rceil = 1$ ということは $D \lt K$ なので、終点までの距離よりも1ステップの移動距離が大きいということです。このような時に合計3ステップで移動しようとすると、確かに以下のような動きになってヘアピンカーブをまたぐ可能性があります。

f:id:betrue12:20190728204914p:plain

これを何とかします。直感的には縦方向に伸びすぎているので、横方向にも回り道をしてみます。

f:id:betrue12:20190728205415p:plain

縦横それぞれに無駄な動きの長さがあるので、 $a + b = \frac{3K - D}{2}$ となります。これを、3辺をまたぐステップがないように $a, b$ に割り振ります。

先ほどと同じく、辺の長さに関する不等式を示していきましょう。始点終点それぞれから見て、図のように1ステップ目が2本目の辺の途中（両端含む）で終わることを確かめます。すなわち始点側について $b \le K \le b+Y+a$ 、終点側について $a \le K \le a+X+b$ が成り立っていればよいです。

$b \le K$ かつ $a \le K$ については、 $\frac{3K - D}{2}$ をほぼ等分に $a, b$ に分けることによって成り立ちます。そして $K \le b+Y+a$ かつ $K \le a+X+b$ については、 $D \lt K$ であることから $a + b = \frac{3K - D}{2} \gt K$ が言えるので成り立ちます。