ABC086C - Travelingを解きました。
皆さんこんにちは、コロナ蔓延る今日この頃どうお過ごしですか?僕はまたAtcoder Biginners ContestのC問題を解いてきました。
さて、今回の問題は一言でいうと、メンドイ。もちろんメンドクサイ系統の中ではさほどひどくはないのですが、そうはいってもやはり面倒だったんです。ただ、高校生の時に数学(IAかIIBのどっちかは忘れたけど)で場合の数の、格子点の問題や最短経路を求める問題をやった経験があって、それが得意だった方ならメンドイという感覚が薄まるかも。
こちらがURLです。
https://atcoder.jp/contests/abs/tasks/arc089_a
問題のコピペです。
シカのAtCoDeerくんは二次元平面上で旅行をしようとしています。 AtCoDeerくんの旅行プランでは、時刻 に 点 を出発し、 以上 以下の各 に対し、時刻 に 点 を訪れる予定です。
AtCoDeerくんが時刻 に 点 にいる時、 時刻 には 点 , , , のうちいずれかに存在することができます。 その場にとどまることは出来ないことに注意してください。 AtCoDeerくんの旅行プランが実行可能かどうか判定してください。
上で書いたように、慣れている人はすぐにどうやって実行可能かどうかを調べるかは簡単に求まると思います。僕の脳みそは高校数学を徐々に飛ばし始めていたので、図を描いて考えました。すると、その場にとどまることは出来ないとは、進みたい距離と動ける距離の偶奇が一致すればよいということに帰着することが分かりました!(あんなに受験のためにやったのに何で忘れるのか...)
以上の事から、やることは単純。今いる(x,y)座標の成分同士を足し合わせて(x+yを計算して)、次に行きたい場所の座標の成分同士も足し合わせて、それらの内、大きい方から小さい方を引いてでた差(差の絶対値)がtの数値以下でかつそのtの偶奇と一致してるかを調べればいいということが分かったので、このことを実装したら見事ACもらえました!
今回の問題は高校時代を思い出せてちょっと感慨深かったかも?
では、さよなら~♪