SRM 514 250pt: MagicalGirlLevelOneDivOne

TopCoder

問題概要

n-jumpとは今いる座標から(±n, ±1), (±1, ±n)だけ移動することをいう。nとして使える値が配列として渡されるので(x,y)に到達できるか判定する問題。

考えたこと

  • 数論系の問題？GCDとかでてきそう。
  • 1が曲者過ぎる。全然分からん。
  • とりあえず3-jumpで行けるところを書いてみよう。こんなとき方眼紙ノートを使っていて良かったと感じられる。
  • 斜めにしか行けないっぽい。パリティあるからそりゃそうか。
  • どうも偶数ジャンプだと全部行けて奇数ジャンプだとパリティ一致する所は全部行けそう。サンプル全部通ったし出すか。
  • 証明してみよう。奇数のときは(2*k+1, 1)に行った後(2*(k-1)+1, 1)に移動できるから後はインダクションで遷移(1,1)が実現できることが分かる。なので到達可能な必要十分条件はパリティが一致すること。
  • 偶数のときもまったく同様に遷移(0,1)が実現できる。なので全マス到達可能。
  • チャレンジが珍しく大量に決まった。
    • 1があれば常にYes -> そんなわけねー
    • 要素が偶数でパリティも一致 -> これはサンプルに無いし誰か間違えると思ってた
    • (x + y)%2 == 1 -> 偶奇は&1で判定した方がいいよね

本番中に提出したコード

一応 %2 == 1の部分は中身が正であることを確認した上で書いた。

#include <string>
#include <vector>
#include <cstdio>
using namespace std;

struct MagicalGirlLevelOneDivOne {

	string isReachable(vector <int> jumpTypes, int x, int y) {
		bool odd = (x + y)&1;
		for(int i=0; i<(int)jumpTypes.size(); i++){
			if(jumpTypes[i]%2==0 || (odd ^ (jumpTypes[i]%2==1) ) ){
				return "YES";
			}
		}
		return "NO";
	}

};

バグを出さない工夫

いろいろ考えるとこっちの方が良かった。

	string isReachable(vector <int> jumpTypes, int x, int y) {
		if( !((x+y)&1) ){
			return "YES";
		}
		for(int i=0; i<(int)jumpTypes.size(); i++){
			if( jumpTypes[i]%2==0 ){
				return "YES";
			}
		}
		return "NO";
	}