AtCoder
java8

atcoder ABC111 D問題

今回は600点問題ということもありめちゃめちゃ難しかった。2の累乗をアームにしていく発想ができなさすぎた
https://atcoder.jp/contests/abc112/tasks/abc112_d

方針

初めに、不可能な場合を考えると、ある点における(x,y)についてx+yの偶奇が各点について偶奇が揃っていないと不可能である。よって、偶奇がそれっているときを考える。まずアームについてであるが、明らかにアームの数とそれぞれのアームの長さを全探索するのは不可能なので、アームの数と長さを決めてしまうことを考える。アームは1,2,4,8,と2の累乗を用いて、30本使えば図のような位置は全て網羅できることがわかる。よって、各点のx+yが奇数の時、このアームを用いて表すことができる(偶数についても1ずらすだけで表せられる)。
図6.png