AtCoder:11 ABC086C – Traveling

https://atcoder.jp/contests/abs/tasks/arc089_a
問題文は上記リンクを参照。

この問題はパスを求める問題です。
静止せずに指定されたタイミングで指定されたパスを通ることができるかどうかを考えます。

        val time = tt - t
        val dist = Math.abs(xx - x) + Math.abs(yy - y)

上記で移動時刻と移動距離を求めます。
移動時刻は前回の時刻から今回の時刻の差で、移動距離は前回の各座標位置から今回の各座標位置の絶対値を取得し加算して求めます。

静止はありませんので、時刻1に対して移動は(x+1, y), (x−1, y), (x, y+1), (x, y−1)のいずれかになります。

初期時刻0、初期座標(0, 0)
移動時刻1、移動座標(1, 0)、 移動距離1
移動時刻1、移動座標(1, 1)、 移動距離1
移動時刻1、移動座標(1, 0)、 移動距離1
移動時刻1、移動座標(0, 0)、 移動距離1

これをまとめて表現した場合
初期時刻0、初期座標(0, 0)
移動時刻1、移動座標(1, 0)、 移動距離1
移動時刻3、移動座標(0, 0)、 移動距離3
この移動経路は、
座標(1, 0)から3移動 -> (1, 1) -> (1, 0) -> (0, 0)かもしれませんし、
座標(1, 0)から3移動 -> (0, 0) -> (1, 0) -> (0, 0)かもしれませんし、
座標(1, 0)から3移動 -> (2, 0) -> (1, 0) -> (0, 0)かもしれませんが、あり得る移動です。

time < dist

つまり、移動に費やす時刻以上の距離を移動することはできません
座標(0, 0)から2移動 -> (1, 0) -> (3, 0) …移動時刻2に対し、移動距離3などはあり得ない
逆に移動距離は戻ることができるので、移動距離が移動に費やした時刻以下になることはあり得ます
座標(0, 0)から2移動 -> (1, 0) -> (0, 0) …移動時刻2に対し、移動距離0はあり得る

ただしここでその移動距離がありうる値か確認する必要があります。
移動時刻2に対し、移動距離0はあり得る
座標(0, 0)から2移動 -> (1, 0) -> (0, 0)
移動時刻2に対し、移動距離1はあり得ない
座標(0, 0)から2移動 -> (1, 0) -> (1, 0)?? …静止してはいけない
移動時刻2に対し、移動距離2はあり得る
座標(0, 0)から2移動 -> (1, 0) -> (2, 0)

これがどういう性質を持っているかよく考えてみると、
移動時刻1、移動距離1
という性質がありますので、この両者の和や差の絶対値は必ず偶数になることがわかります。
移動時刻1、移動距離1
移動時刻2、移動距離2
または
移動時刻2、移動距離0

つまりこの和や差の絶対値が奇数になるデータはあり得ないと言えます

(dist - time) % 2 != 0

distとtimeを入れ替えれば正負は変わりますが偶奇は変わりません。
また絶対値をとって計算しても同じです。

ただし差分から偶数ではないかどうかを判定するのではなく、差分から奇数かどうか判定する場合、差分が負の数になる場合がありますので絶対値の取得が必要です。

//ここでは以下は全て同じ条件を表す
(dist + time) % 2 != 0 //加算なのでdist、timeの順序は関係ない
(dist + time) % 2 == 1 //加算なのでdist、timeの順序は関係ない

(dist - time) % 2 != 0
// (dist - time) % 2 == 1 //差分から奇数かどうか判定する場合は絶対値を使う必要がある

(time - dist) % 2 != 0
// (time - dist) % 2 == 1 //差分から奇数かどうか判定する場合は絶対値を使う必要がある

Math.abs(dist - time) % 2 != 0
Math.abs(dist - time) % 2 == 1

Math.abs(time - dist ) % 2 != 0
Math.abs(time - dist) % 2 == 1

その結果、

  • time < dist …移動に費やす時刻以上の距離を移動する場合
  • (dist – time) % 2 != 0 …移動時刻と移動距離の和や差の絶対値が奇数の場合

この条件のどちらか片方にでも該当するデータの場合、そのデータはあり得ないデータだと言えます。

if (time < dist || (dist - time) % 2 != 0) {}

想像だけではなかなかイメージしずらいので実際に手元に簡単な図を書き、幾つかサンプルを作成して動きを確かめてみるとよいでしょう。

その他timeとdistは共に偶数、奇数を入れ替えながらカウントされるという特徴を利用する方法もあります。

  • timeが奇数の場合、distも奇数
  • timeが偶数の場合、distも偶数

つまり、

if((dist - time) % 2 != 0) {}

は以下のようにも条件を指定できます。

 if (time % 2 != dist% 2) {}

また繰り返し処理をfor文で繰り返していますが、単純な繰り返しなのでrepeat()を使えば見た目は整います。

for (i in 0 until N) {}
repeat(N) {}

Advertisements

Java,Kotlin,ProgrammingAtCoder,Java,Kotlin

Posted by codive