Official

E - Gap Existence Editorial by kyopro_friends


\(j\) を固定したとき、\(A_i-A_j=X\) となるための \(A_i\) の値は一意に定まります。このため、\(A\) の中にそのような値が存在するかどうかを判定できればよいです。
愚直に配列を走査すると最悪の場合 \(1\) 回あたり \(\Omega(N)\) 時間かかり、全体で \(\Omega (N^2)\) 時間となるため実行時間制限に間に合いません。C++ の vector に対する find、Python の list に対する in、Java の list に対する contains などを用いた場合も同様です。標準ライブラリの計算量にも注意しましょう。
\(A\) を set で保持するなどすれば \(1\) 回あたり \(O(\log N)\)、全体で \(O(N\log N)\) となり、実行時間制限に間に合わせることができます。

実装例(C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
	int n,x;
	cin >> n >> x;

	set<int>s;
	for(int i=0;i<n;i++){
		int t;
		cin >> t;
		s.insert(t);
	}
	
	for(auto a:s){
		if(s.find(a+x)!=s.end()){
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
}

この問題は尺取法によりソート+線形時間で解くこともできます。
\(A\) を並び替えても答えは変わらないので、\(A\) を昇順にソートします。 \(j\) を固定して \(i\) を探す際、\(j\) が小さい順に調べると、対応する \(i\) も単調増加となることから、線形時間ですべての \(j\) について調べることができます。

実装例(C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
	int n,x;
	cin >> n >> x;
	vector<int>a(n);
	for(int i=0;i<n;i++)cin >> a[i];
	sort(a.begin(),a.end());

	int i=0;
	for(int j=0;j<n;j++){
		while(i<n&&a[i]-a[j]<x)i++;
		if(i<n&&a[i]-a[j]==x){
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
}

posted:
last update: