Official
E - Gap Existence Editorial
by
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)\) となり、実行時間制限に間に合わせることができます。
#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\) について調べることができます。
#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:
