AtCoder が提供しているABC（AtCoder Beginner Contest）296 のC問題をC++とPythonで解いてみました。ABC296は、2023年4月1日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Gap Existence（Difficulty : 162）
問題はリンク先をご覧ください。
検索する計算量を工夫して下げる必要がある問題です。AtCoder Problems による Difficulty は 162 でした。
解答案
見た目より難しい問題です。以下の単純な全検索では、$O(N^2)$ となり。$N = 2 \times 10^5$ では計算量的に間に合いません。
bool result = false;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (a[i] - a[j] == x) {
result = true;
}
}
}計算量を下げる工夫を2点紹介します。
C++ プログラム例（ABC296C）
C++ では、set コンテナを使うプログラムを紹介します。set は、二分探索木で実装されているため、特定の値を $O(\log N)$ で検索することができます。$N$ 全体に対して、値を探すため、合わせて計算量は $O(N \log N)$ となり間に合います。
set コンテナの実装は、12、16、17行目をご覧ください。以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, x;
cin >> n >> x;
set<int> a;
for (int i = 0; i < n; ++i) {
int t;
cin >> t;
a.insert(t);
}
bool result = false;
for (auto e : a) {
if (a.find(e + x) != a.end()) {
result = true;
}
}
if (result) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}次にしゃくとり法という方法を紹介します。
配列 A の値をソートして、X の値を正の値とします。これは X が負の場合に存在すれば、i と j を入れ替えればよいためです。
二つの添え字 left と right を使って、差分を調べていきます。まず left を固定して、A[right] – A[left] が X を超える直前まで調べます。A は大きさ順にソートしているため、left をインクリメントした場合に、right は、その値から調べればよくなります。right の動きが止まったり、動いたりする様子を「しゃくとり」と表現しているようです。
しゃくとり法の操作には、$O(N)$ かかります。ソートに $O(N \log N)$ かかるため、合わせて、計算量は、$O(N \log N)$ となります。
例外処理として、x が 0 の場合は、”Yes” を出力して、プログラムを終了します（13-16行）。以下が、しゃくとり法を使ったプログラムとなります。
#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];
}
x = abs(x);
if (x == 0) {
cout << "Yes" << endl;
return 0;
}
sort(a.begin(), a.end());
bool result = false;
int right = 0;
for (int left = 0; left < n - 1; ++left) {
while ((right < n - 1)&&(a[right + 1] - a[left] <= x)) {
++right;
if (a[right] - a[left] == x) {
result = true;
}
}
}
if (result) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}どちらも AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC296C）
Python について、C++ ほどコンテナの計算量が把握できていません。このため、しゃくとり法を採用しました。
"""AtCoder Beginner Contest 296 C"""
import sys
n, x = map(int, input().split())
a = list(map(int, input().split()))
x = abs(x)
if x == 0:
print("Yes")
sys.exit()
a.sort()
result = False
right = 0
for left in range(n - 1):
while right < n - 1 and a[right + 1] - a[left] <= x:
right += 1
if a[right] - a[left] == x:
result = True
print("Yes" if result else "No")こちらも「AC」と判定されました。
最後に
この問題は、アルゴリズムの知識がそれほど多くないプログラマにとって難しいと思います。一方、コンテストでは提出者の98.8%の方がAC判定となっています。AtCoder 参加者のレベルが高いと考えられます。
引き続き ABC の問題を紹介していきます。
