Codeforces Round #707 C. Going Home (Div. 2, based on Moscow Open Olympiad in Informatics)

비둘기집의 원리(존재의 보장)가 사용된 문제입니다.

문제 요약

정수 배열 a가 있습니다. 서로 다른 인덱스 x,y,z,w에 대해서
a[x]+a[y] =a[z]+a[w]를 만족하는 x,y,z,w가 존재하는지 판별하는 것이 문제입니다.
(n<=2e5 , 1<=a[i]<=2.5e6)

어려움

시간복잡도

모든 서로 다른 합을 구해보면 n^2이 걸립니다. n이 20만이기 때문에 연산량이 너무 많아집니다. 하지만 아무리 생각해도 n^2 풀이말고는 떠오르지 않았습니다.
어떤 수 x가 주어지고 두 합이 x와 같아지는 것을 찾는 것은 투포인터 방식으로 빠르게 찾을 수 있지만 x가 특정되지도 않았기 때문에 투포인터 방법도 해결책이 아니었습니다.

해결

핵심 아이디어는 n이 어느정도 커지면 답은 항상 존재한다는 것입니다.
다음과 같이 간단히 증명 가능합니다.

a[i]가 모두 다르고, 합의 종류가 다양할수록 최악의 경우입니다.
최악의 경우를 고려해 봅니다.
a의 수가 모두 다르다 => 최대 n(n-1)/2개의 합 종류 발생 가능
a[i]의 범위 : 1<=a[i]<=2.5e6
두 합의 범위 : 2<=a[i]+a[j] <=5e6
발생할 수 있는 종류의 최대 값 : n(n-1)/2 <=5백만 => n<3300
따라서 n이 3300쯤보다 크면 항상 a[x]+a[y] == a[z]+a[w]인 (x,y),(z,w) 쌍이 존재 (합이 겹치는 것이 반드시 발생)

a[i]의 범위가 주어졌을 때 bucket을 마련해서 세아려주는 방식을 떠올렸는데, 그 방법으론 안되겠다 판단해서 a[i]의 범위는 별로 중요하지 않은 요소라 판단했습니다. a[i]의 범위가 이런식으로 사용될 줄은 생각도 못했네요.

int a[(int)2e5+10];
vector<pii> sums[(int)5e6+100];	//sums[a[i]+a[j]] = {{i,j},...}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);	
	
	// a의 수가 모두 다르면 -> 최대 n*(n-1)/2개의 합 종류 발생 가능
	// 1<=a[i]<=2.5백만
	// 2<=a[i]+a[j] <=5백만
	// 발생할 수 있는 종류의 최대 값 = n*(n-1)/2 <=5백만  => n<3300
	// 따라서 n이 3300쯤보다 크면 항상 a+b == c+d인 (a,b),(c,d) 쌍이 존재
	
	int n;
	cin>>n;
	// vector<int> a(n);
	for(int i=0;i<n;i++) cin>>a[i];

	for(int i=1;i<n;i++){
		for(int j=0;j<i;j++){
			int s=a[i]+a[j];	

			if(sums[s].size()!=0){
				for(pii idxs:sums[s]){
					if(idxs.fs==i || idxs.fs==j || idxs.sc==i || idxs.sc==j) continue;
					cout<<"YES\n";
					cout<<idxs.fs+1<<" "<<idxs.sc+1<<" "<<i+1<<" "<<j+1<<'\n';
					return 0;
				}
			}	
			sums[s].push_back({i,j});
		}
	}

	cout<<"NO\n";

	return 0;
}