そこそこの結果。
https://codeforces.com/contest/2279/problem/A
問題
整数列Aに対し、以下の処理を最大1回行える。
- 部分列を指定し、その中の並びを反転したうえで2倍にする
隣接要素の差の絶対値の最大値を最小化したい。その時の値を求めよ。
解法
二分探索で解く。
解をv以下にできるか判定することを考える。
Aの初期状態で、隣接要素同士がvより大きな差がある箇所を列挙する。
vより大きな差がある場合、左右のどちらかは反転により値を差し替える必要がある。
- 0か所:v以下が確定する。
- 1か所:その1か所は、反転箇所の両端候補になるので、もう1か所の端を総当たりしチェックする。
- 2か所:その2か所は、反転箇所の両端候補になるので、実際に反転させて確認する。
- 3か所:v以下にできないことが確定する。
int T,N,A[303030]; int B[303030]; int ok(int v) { vector<int> V; int i,x,y; FOR(i,N-1) if(abs(A[i+1]-A[i])>v) V.push_back(i); if(V.size()==0) return 1; if(V.size()>2) return 0; if(V.size()==2) { x=V[0]+1; y=V[1]; FOR(i,N) { B[i]=A[i]; if(i>=x&&i<=y) B[i]*=2; } reverse(B+x,B+y+1); FOR(i,N-1) if(abs(B[i+1]-B[i])>v) return 0; return 1; } x=V[0]; for(i=x+1;i<N;i++) { if(i>x+1&&abs(A[i]-A[i-1])*2>v) break; if(abs(A[x]-2*A[i])<=v&&(i==N-1||abs(2*A[x+1]-A[i+1])<=v)) return 1; } for(i=x;i>=0;i--) { if(i<x&&abs(A[i]-A[i+1])*2>v) break; if(abs(A[x+1]-2*A[i])<=v&&(i==0||abs(2*A[x]-A[i-1])<=v)) return 1; } return 0; } void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>N; int ma=0; FOR(i,N) { cin>>A[i]; } int ret=(1<<20)-1; for(i=19;i>=0;i--) if(ok(ret-(1<<i))) ret-=1<<i; cout<<ret<<endl; } }
まとめ
しょうもないミスで1WAしてしまったのもったいない。