AtCoder ABC 086 C - Traveling の解答(by Python)

前置き

今更ですが、AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ という記事に触発され、過去問10問を自分なりにコードを書いて解いてみました。
だいたいはスムーズに解けたのですが、その10問目である086Cの問題でafter_contest01.txtのテストがどうしても通らなくてハマっていたのが、原因を突き止めたので記事にします。
Pythonで記述していますが、ハマりポイントは言語とは関係ありませんので別言語で書いてハマってしまっているよという方にも参考になると思います。

問題の内容

こちらにもある通り、旅行プランが可能かどうかを判定する問題です。
1秒ごとに上下左右に移動し、なおかつその場にとどまれないという条件から、時刻tと座標合計の偶奇が一致するかというところに着目すれば大枠は解けています。もちろん、以下のような大きすぎる移動も不可であることも含めないといけません。解説に関しては問題番号で調べればたくさんでてくるのでここらで割愛します。

# 入力例2
1
2 100 100

自分が作った最初の解答

  N = int(input())
  plan = [input().split() for i in range(N)]

  def isRealizable(t, x, y):
    if x + y > t:
      return False
    elif (x + y) % 2 == t % 2:
      return True
    else:
      return False

  # t = 1 のとき
  if not isRealizable(int(plan[0][0]), int(plan[0][1]), int(plan[0][2])):
    print("No")
    exit()

  # t = 1 だけ判定済
  for i in range(1, N):
    diff_t = int(plan[i][0]) - int(plan[i - 1][0])
    diff_x = int(plan[i][1]) - int(plan[i - 1][1])
    diff_y = int(plan[i][2]) - int(plan[i - 1][2])
    if not isRealizable(diff_t, diff_x, diff_y):
      print("No")
      exit()

  print("Yes")

ほぼほぼ正解だったのですが、after_contenst01.txtのテストだけ失敗してしまい、頭を抱えて悩んであれこれ調べました。

ハマりポイント1 嘘解法

ABC086C - Traveling の嘘解法
上記のような記事も見つけたのですが、こちらは時刻tに対して原点からの移動が可能かどうかを判定しているコードが出回っているという記事でした。自分はdiff_t, diff_x~~の辺りでその部分はしっかり考慮できていたため、そういった間違いもあるのかという程度でした。旅行プランが可能かどうかなのは瞬間瞬間だけでなく一連の移動が可能かどうかを見ないといけないですね。(こちらも記事に詳細があるので解説は省きます。)

ハマりポイント2 絶対値

after_contest01.txtが通らない原因は結論から言うと、diff_xやdiff_yがマイナスになるときに答えが間違ってしまうからです。diff_x, diff_yを絶対値に修正します。

    diff_x = abs(int(plan[i][1]) - int(plan[i - 1][1]))
    diff_y = abs(int(plan[i][2]) - int(plan[i - 1][2]))

なぜこれでうまくいくのかを言うより具体的になぜ修正前のコードではダメだったのかの例を記します。

2
100 50 50
102 0 0 

100秒後に(50, 50)に到達し、その2秒後に(0, 0)に到達できるか？を考えることになります。人間の目からでは当然"No"とわかりますが、修正前のコードではこちらが"Yes"になってしまいます。
大きすぎる移動ははじかないといけないので x + y > t としていましたが、diff_x, diff_yがマイナスであると、この条件がクリアされてしまっていたということです。言い方を変えると、関数isRealizableの引数xやyは"移動量"としなければいけませんでした。

余談

初期条件をt=0, x=0, y=0としてt=1のケースをループに含めてしまうのがよかったですね。