blue_jamのTopCoder日記

SRM514 Div1 Easy

Practice, SRM | 00:32

最近怠けすぎてたので練習．

間違ってタブ消して一から書き直し．

概要

(0,0)にいる魔法少女（仮にマリアちゃんとしよう）が，(x,y)にいる魔女を倒しに行きたい．

しかしマリアちゃんは(±1,±n)，(±n,±1）の方向にしか動けないのだ！（ちょっとすごい桂馬跳びみたいな．nは複数個与えられます)

マリアちゃんは魔女を倒しにいくことができるだろうか．

解法

• nに偶数が1個でも入るならば倒せにいける
• nに偶数が1個もないなら，x + y が偶数のときのみ倒せに行ける

これだけで判定．

nが2ならば，3回の動きを組み合わせることで，上下左右に移動することができる．よって，何回かかるかは知らないが，マリアちゃんは魔女を倒せにいける．

nが3以上ならば，(+1，+n)方向に移動する．(+n，-1)方向に移動する．このときの位置は(+n+1，+n-1)，さらに(-n，-1)方向に移動．位置は(+1，+n-2)

何ということだろう．これはn-2の時の動きと同じではないだろうか．

つまり，nが偶数ならばnが2の時と同様の動きをできるのでマリアちゃんは魔女がどの場所にいても倒しにいくことができる．

nが奇数のとき，x座標，y座標の和について考える．

初期値は0+0=0．

これに，±(n+1)，±(n-1)を加えることになる．nが奇数ならn+1，n-1はともに偶数．偶数にいくら偶数を足しても偶数なので，マリアちゃんはx+yが偶数の位置にいる魔女しか倒しに行けない．

ソース

class MagicalGirlLevelOneDivOne {
public:
    string isReachable(vector <int> jumpTypes, int x, int y) {
        string res;
		int n = jumpTypes.size();
		for(int i=0;i<n;++i){
			if(jumpTypes[i] % 2 == 0)
				return "YES";
		}
        return (x + y) % 2 == 0 ? "YES": "NO";
    }

};