ABC145 D - Knight (400)
最初の考察
DFSして原点を目指せば良いのでは
$ O(N^2)
でTLE
ちゃんとした考察
座標を変換すれば良さそう
$ 2x + y = A, x + 2y = B
とかと置くと、X,YがA,Bに変換される
A+B回の内、A回縦に、B回横に動くパターンを求めるということになる
これは格子状でよく見る問題で
$ \rm _{A+B}\rm C_A
を求めれば良い
これは
$ O(N)
でできる
問題:
https://atcoder.jp/contests/abc145/tasks/abc145_d
提出:
https://atcoder.jp/contests/abc145/submissions/8474399
#ABC145
#400pt
#D
#ABC
#AtCoder