2549 Sumsets

問題概要

整数の集合Sが与えられる。
この中の相違なる4つの要素a,b,c,dについてd=a+b+cを満たすもののうち、最大のdを求めよ。

Sの要素数nは1000以下、集合の各要素の値は-536870912以上536870911以下である。

解法

a+bの組を全通りハッシュを用いてテーブルに記録する。
ハッシュはa+bを素数で余りを取ったものを用いる。

d-cを全通り、試し、a,b,c,dが相違で、等式を満たすものがあるかを調べる。
ハッシュテーブルはサイズが300万で、開番地法を使った。

ソースコード

const int MX=3000017,inf=536870912;
int n,in[1000];
pi tbl[MX];

int main(){
	while(scanf("%d",&n),n){
		rep(i,MX)tbl[i].first=tbl[i].second=inf;
		rep(i,n)scanf("%d",in+i); sort(in,in+n);
		
		rep(i,n)rep(j,i){
			int h=(in[j]+in[i])%MX; if(h<0)h+=MX;
			while(tbl[h].first!=inf&&tbl[h].second!=inf)h=(h+1)%MX;
			tbl[h].first=in[j]; tbl[h].second=in[i];
		}
		for(int i=n-1;i>0;i--)rep(j,i){
			int h=(in[i]-in[j])%MX; if(h<0)h+=MX;
			while(tbl[h].first!=inf&&tbl[h].second!=inf){
				if(in[i]-in[j]==tbl[h].first+tbl[h].second&&
					tbl[h].first!=in[i]&&tbl[h].first!=in[j]&&
					tbl[h].second!=in[i]&&tbl[h].second!=in[j]){
						printf("%d\n",in[i]); goto END;
				}
				h=(h+1)%MX;
			}
		}
		puts("no solution"); END:;
	}
	return 0;
}