ARC12 D - Don’t worry. Be Together - math314の日記http://arc012.contest.atcoder.jp/tasks/arc012_4 二次元平面上の格子点(x,y) にいる人間が、原点(0,0)に移動したい。 この時、Tターン後に原点にいる移動方法の組み合わせを求めることが出来ればよい。 移動が可能な条件 Tターン後に原点へ移動が可能な条件は、x+y <= T かつ、x+yとTの偶奇が一致している事。 x+y <= Tは明らかとして、x+yとTの偶奇についての証明 無駄に丁寧なのでわかってる人は飛ばしてください まず1次元で考える。 Txターン後に原点へと移動したい x軸方向と逆方向の2通りの動き方があり、座標xからそれぞれ(a,b)だけ移動したとすると、移動後の座標は x+a-b となる。 ここで x+a-b = 0,a+b = Tx より a = (Tx-x)/2 , b = (Tx+x)/2 a,bが整数なので、Tx-x
