Autumn Fest 2012 : E Be Together

続いて５問目。
本番は部分点は取れたけど、完全解には至らず。
http://autumn_fest.contest.atcoder.jp/tasks/autumn_fest_05

部分点の範囲では、10ターン内の移動範囲を列挙すればよい。
本番では完全解について、「１回原点につけばあとは４回ごとに原点につけるから、最初に原点につくターン+4×iターンを考えればいいかな？」と思いつつ、初回原点につくまでの回数がわからなかった。

では完全解について。前提として↓がある。(x,yは正とする)

• (x,y)から(0,0)にたどり着く最短ターンMは、総移動量(1+2+...+M)がx+y以上で、かつ総移動量とx+yがともに奇数かともに偶数。

(x+yが総移動量を超えると必ず原点にたどり着く解があるのは、直感的にはわかるけど証明はできず…)

よって、各開始点のx+yの偶奇が不一致な場合は、同時に原点にたどりつくことがない。

各開始点のx+yの偶奇がいっしょの場合、x+yが最も大きな点を考えればよい。
よって、総移動量がx+y以上でかつ総移動量とx+yの偶奇が一致するMを求めればよい。

int N;
int X[10],Y[10];

void solve() {
	int x,y,i,j,p,rr,TM,TTC,mask;
	int d,s;
	
	N=GETi();
	d = 0;
	FOR(i,N) {
		X[i]=abs(GETi()); Y[i]=abs(GETi());
		if((X[i]+Y[i])%2!=(X[0]+Y[0])%2) {
			_P("-1\n");
			return;
		}
		d = max(d, X[i]+Y[i]);
	}
	
	s=0;
	while(d>0 || (d&1)) { s++; d-=s;}
	_P("%d\n",s);
	
	return;
}

まとめ

総移動量の偶奇は奇奇偶偶で４ターンで１順するので、４で割った余りに着目したのじたいは悪くなかったな。
総移動量がx+yを超えたら必ず原点にたどり着けるというのが証明ができず躊躇してしまったが、迷わず行くべきだった…。