Codeforces #245 Div1 D. Tricky Function

これも適当解法で通ってしまったが、想定解も合わせて練習。
http://codeforces.com/contest/429/problem/D

問題

N要素の数列A[i]がある。
ここでf(i,j)=(i-j)^2 + (A[i+1]+A[i+2]+...+A[j])^2とする。
i < jとなる(i,j)の対において、f(i,j)の最小値を求めよ。

解法

適当解法

本番の適当解法。
f(i,j)は最初に(i-j)^2の項を含むため、iとjは近い方が良い。
iとjが遠い方がいいのは、jを遠ざけると(A[i+1]+A[i+2]+...+A[j])^2の項が小さくなる場合である。
例えば、[100,100,100,100,-100,-100,-100]といった部分列を選択すれば、(A[i+1]+A[i+2]+...+A[j])^2==0となる。
ではこのケースは最大でどの位長くなるか。
例えば[1,1,1,1,1,1.....,1,-1,-1,-1,....-1]といった数列を作ると確かに全体で(A[i+1]+A[i+2]+...+A[j])^2の項は短くなるが、この場合最初からより小さい[1,1,-1]を選択した方が(i-j)^2の項が小さくなる。
A[i]の絶対値の最大値をPとすると、恐らく√P程度であろう。

よって、iをN通り総当たりし、それぞれjをiからの距離が√P程度になるまで総当たりすればよい。
N<=10^5、P<=10^4であることからこれで通ってしまう。

恐らくこれは想定外の回答だと思う。このためこの問題の解答者が大幅に増えてしまった。
これを防ぐには、P<=10^8程度にしておくべきだった。

int N;
ll A[100001];
ll S[100001];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		S[i]=((i>0)?S[i-1]:0)+A[i];
	}
	ll ma=1LL<<50;
	FOR(x,100000) for(j=1;j<=1001 && x+j<N;j++) {
		if(j*(ll)j>=ma) break;
		ma=min(ma,j*(ll)j+(S[x+j]-S[x])*(S[x+j]-S[x]));
	}
	cout << ma << endl;
}

想定解

各A[i]に対し、(i,)という２次元座標上の点を考える。
すると、この問題はこれらの点集合における最近点対を求める問題となる。

今回、以下のサイトを参考にライブラリを作って解いてみた。
Divide and Conquer | Set 2 (Closest Pair of Points) | GeeksforGeeks

bool sortx(complex<double> l,complex<double> r) { return l.real()<r.real();}
bool sorty(complex<double> l,complex<double> r) { return l.imag()<r.imag();}

double cp_sub2(complex<double>* p,int sz,double d) {
	int x,y;
	sort(p,p+sz,sorty);
	FOR(x,sz) for(y=x+1;y<sz && p[y].imag()-p[x].imag()<d;y++) d=min(d,abs(p[x]-p[y]));
	return d;
}
double cp_sub(complex<double>* p,int sz) {
	
	int x,y,piv;
	if(sz<=5) { // brute force
		double cp=1e100;
		FOR(x,sz) for(y=x+1;y<sz;y++) cp=min(cp,norm(p[x]-p[y]));
		return sqrt(cp);
	}
	piv=sz/2;
	double d=min(cp_sub(p,piv),cp_sub(p+piv,sz-piv));
	vector<complex<double> > V;
	FOR(x,sz) if(fabs(p[x].real()-p[piv].real())<d) V.push_back(p[x]);
	
	return min(d,cp_sub2(&*V.begin(),V.size(),d));
}

double ClosePoint(vector<complex<double> > V) {
	complex<double>* be=&*V.begin();
	sort(be,be+V.size(),sortx);
	return cp_sub(be,V.size());
}

void solve() {
	int f,i,j,k,l,x,y;
	int N;
	vector<complex<double> > C;
	
	cin>>N;
	
	x=0;
	FOR(i,N) {
		cin>>y;
		x+=y;
		C.push_back(complex<double>(i,x));
	}
	double d=ClosePoint(C);
	_P("%lld\n",(ll)(d*d+0.01));
}

まとめ

Pが大きかったら、最近点対を求める問題と気づかずこんなに正答者でなかったろうな。