GCJ 2013 R1C B.Pogo

過去問 その他

問題

(0,0)から(X,Y)まで移動する。
各ターンで、上下左右に動けるが、iターン目にはiだけ移動する。

移動方法をNSEWを並べた文字列で返す。

考え方

(0,0)から(X,Y)までtターンで移動できるかどうかを考える。
移動するための条件として、
1+2+...+t >= abs(X)+abs(Y)
でなければいけない。また、偶奇性から
(1+2+...+t)mod2 = (abs(X)+abs(Y))mod2
も成り立つ必要がある。


tの時成り立つとして、t+1の時、両辺にt+1を加えることで、成り立つことがわかるので、数学的帰納法で、任意のターンtで上記の条件が満たされていれば十分であることがわかる。


上記の条件から、tターンで、(0,0)から(X,Y)にいけるかどうかが判定できる。
まず、(0,0)から(X,Y)にたどり着くまでの最小ターンをforループ回して求める。
最小ターンturnで、(X,Y)から上下左右にturnだけ動かし、そこがturn-1で移動できる点か確認する。
もし、移動できるならば、そこに移動する。
これを繰り返し、turnで(0,0)にたどり着くルートをgreedyに求める。
(turn数以下で(0,0)にたどり着くものがありえるが、それらは解ではないので終了しない)
求めたルートを反転させれば、求めるべきルートが得られる。

反省

類題
Automn Fest 2012 E.Be Together
http://autumn_fest.contest.atcoder.jp/tasks/autumn_fest_05
http://www.slideshare.net/tomerun/together-14867665

コンテスト中に解けてた。。。