ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

AtCoder Beginner Contest 135 E - Golf

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 が言えるので成り立ちます。

以上でこの構築が可能であることが示せました。

これで構築が不可能であるケースに対してはその証明を、可能であるケース全てに対しては具体的な構築方法とステップ数  n の最適性の証明を与えることができました。あとは場合分けや座標計算を間違えずに書けば解くことができます。

ACコード

Submission #6597616 - AtCoder Beginner Contest 135