Saiko~ No Contesuto #03 D. ぐるぐるツアー
問題文
解法
dp[すでに訪れた街][現在いる街][現在向いている方向]:=（最小コスト）
としてDPすればいい*1。向きxで街aにいる状態から、向きyで街bにいる状態へ遷移する最小コストを調べよう。
現在地を原点にとる。 目的地が第一象限にあり、上向きで始まり下向きで終わる場合、次のような経路が最短経路になる。
よく見ると、
（最小コスト）=（マンハッタン距離）+2
になることが分かる。
目的地が第二象限にあり、上向きで始まり下向きで終わる場合、次のような経路が最短経路になる。
よく見ると、
（最小コスト）=（マンハッタン距離）+8
になることが分かる。
このことから一般に、
（最小コスト）=（マンハッタン距離）+α
になることが予想できる。
このまま場合分けを続けてもαを求めることができるが、場合分けするとミスりそうだし、ミスった時のデバッグが辛い。
下向き(123,456)に行く場合も、下向き(1,1)に行く場合もαは同じなのだから、-5から5ぐらいまでのグリッド上で幅優先探索してαを求めるのが安全。
Saiko~ No Contesuto #03 D. ぐるぐるツアー
感想
早い段階で場合分けを諦めてプログラムまかせにしたのが良かった気がする。 distにstart directionとcurrent directionとかコメント書いておきながら、ところどころ逆になっててアレ。対称的じゃなかったら死んでた。
*1:巡回セールスマン問題
