SRM514 Div1 Easy - MagicalGirlLevelOneDivOne

問題

与えられるリストに載っている任意の数字nについて「x/y方向に±n、y/x方向に±1進む」という操作を何度でもできるとき、(0,0)から(x,y)に辿り着けるか判定

解法

リストに偶数が含まれていればどのマスでも行けるから無条件にYES
奇数しかなければi+jが偶数であるようなマス(i,j)ならどこでも行けるからx+yが偶数ならYES
チェスのナイトとビショップを想像したら一瞬でわかった

↓具体的なムーブを使った証明
x方向にi、y方向にj動かす移動を{i,j}と表す

n=偶数のとき)
{1,n}と{1,-n}という2つの移動のセットをn/2回繰り返して(n,0)に行った後に{-n,1}で(0,1)に行ける
同様にして上下左右どこでも1マス進むことができるから任意のマスに行ける

n=奇数のとき)
{1,n}と{1,-n}のセットを(n+1)/2回繰り返して(n+1,0)に行った後に{-n,1}で(1,1)に行ける
同様にして斜め4方向ならどこでも1マス進める
nが奇数 ∴ ±1が偶数だからどう移動してもi+jが奇数のマス(i,j)には進めない

class MagicalGirlLevelOneDivOne {
	public:
	string isReachable(vector<int> a, int x, int y) {
		each(i,a) if (i%2==0) return "YES";
		return ((x+y)%2 ? "NO" : "YES");
	}
};