Codeforces #492 Div1 C. Leaving the Bar

そこまで確証はないけど通ってしまった。
http://codeforces.com/contest/995/problem/C

問題

N個のベクトルV[i]が与えられる。
原点に対し、各ベクトルV[i]かその逆ベクトルV[i]の相対位置に移動することを繰り返す。
ベクトル長が10^6以下のとき、最終的に原点からの距離が1.5*10^6以下になる移動例を１つ示せ。

解法

√2*10^6＜1.5*10^6なので、なんとなく(-10^6,-10^6)～(10^6,10^6)にいればよさそうだなと気が付く。
自分は以下のようにした。

• ４つの象限それぞれで、原点最寄りの座標と直前の位置を持つ。
• ベクトルV[i]が与えられる毎に、上記４つの象限の値にV[i]または-V[i]を足し、次の状態に遷移する。
  • 同じ象限に至る状態遷移が複数あるなら、原点に近いものを戻す。

int N;
ll X[101010],Y[101010];

ll SY[101010][4];
ll SX[101010][4];
int from[101010][4];
int S[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		FOR(j,4) from[i+1][j]=-1;
		SY[i+1][0]=SY[i+1][1]=1LL<<30;
		SY[i+1][2]=SY[i+1][3]=-1LL<<30;
		SX[i+1][0]=SX[i+1][3]=1LL<<30;
		SX[i+1][1]=SX[i+1][2]=-1LL<<30;
		FOR(j,8) if(from[i][j/2]>=0) {
			ll nx=SX[i][j/2]+((j%2)?X[i]:-X[i]);
			ll ny=SY[i][j/2]+((j%2)?Y[i]:-Y[i]);
			
			// 0
			if(nx>=0 && ny>=0 && nx*nx+ny*ny<=SY[i+1][0]*SY[i+1][0]+SX[i+1][0]*SX[i+1][0]) from[i+1][0]=j, SY[i+1][0]=ny, SX[i+1][0]=nx;
			if(nx<=0 && ny>=0 && nx*nx+ny*ny<=SY[i+1][1]*SY[i+1][1]+SX[i+1][1]*SX[i+1][1]) from[i+1][1]=j, SY[i+1][1]=ny, SX[i+1][1]=nx;
			if(nx<=0 && ny<=0 && nx*nx+ny*ny<=SY[i+1][2]*SY[i+1][2]+SX[i+1][2]*SX[i+1][2]) from[i+1][2]=j, SY[i+1][2]=ny, SX[i+1][2]=nx;
			if(nx>=0 && ny<=0 && nx*nx+ny*ny<=SY[i+1][3]*SY[i+1][3]+SX[i+1][3]*SX[i+1][3]) from[i+1][3]=j, SY[i+1][3]=ny, SX[i+1][3]=nx;
			
		}
	}
	
	FOR(i,4) if(from[N][i]>=0 && SY[N][i]*SY[N][i]+SX[N][i]*SX[N][i]<=1500000LL*1500000LL) {
		int cur=N;
		int pos=i;
		while(cur>0) {
			if(from[cur][pos]%2==0) S[cur-1]=1;
			else S[cur-1]=-1;
			pos=from[cur][pos]/2;
			cur--;
		}
		break;
	}
	FOR(i,N) cout<<S[i]<<" ";
	cout<<endl;
}

まとめ

うまく証明できそうだけど、厳密には試していない。