そこまで確証はないけど通ってしまった。
http://codeforces.com/contest/995/problem/C
問題
N個のベクトルV[i]が与えられる。
原点に対し、各ベクトルV[i]かその逆ベクトルV[i]の相対位置に移動することを繰り返す。
ベクトル長が10^6以下のとき、最終的に原点からの距離が1.5*10^6以下になる移動例を1つ示せ。
解法
√2*10^6<1.5*10^6なので、なんとなく(-10^6,-10^6)~(10^6,10^6)にいればよさそうだなと気が付く。
自分は以下のようにした。
- 4つの象限それぞれで、原点最寄りの座標と直前の位置を持つ。
- ベクトルV[i]が与えられる毎に、上記4つの象限の値に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; }
まとめ
うまく証明できそうだけど、厳密には試していない。