7K12 blog

猫でも分かるアルゴリズム解説

ABC145 D - Knight

f:id:tkr987:20200721031201p:plain

https://atcoder.jp/contests/abc145/submissions/15338725

  • ベクトルの個数が分かれば格子状の最短経路問題と同じ

f:id:tkr987:20200721032417p:plain

(i+1, j+2)と(i+2, j+1)のベクトルs,tの個数が分かっていれば、格子状の最短経路問題と同じ。ベクトルの個数は連立方程式で求まる。連立方程式を解くと t = \frac{2X - Y}{3}が得られるが、tが整数かどうかの判定を忘れずに書いておく。