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が奇数 ∴ ±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"); } };