AtCoder が提供しているABC（AtCoder Beginner Contest）344 のC問題をC++とPythonで解いてみました。ABC344は、2024年3月9日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 A+B+C（Difficulty : 204）
問題はリンク先をご覧ください。
先にあり得る和を記憶してから判定します。AtCoder Problems による Difficulty は 204 でした。
解答案
クエリの回数 $Q$ の制約は、$1 \leqq Q \leqq 2 \times 10^5$ です。このクエリ毎に最大 $100 \times 100 \times 100 = 10^6$ 通りの和を計算していては間に合いません。
前準備として、あり得る和を set コンテナに記憶しておきます。この場合、クエリ毎の計算量は、$O(1)$ となり間に合います。
C++ プログラム例（ABC344C）
3種類の配列を読み込み、あり得る和を set コンテナ s に格納します（27ー34行目）。クエリ毎に s に格納されているか調べます（41行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
int n;
cin >> n;
vector<ll> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int m;
cin >> m;
vector<ll> b(m);
for (int i = 0; i < m; ++i) {
cin >> b[i];
}
int L;
cin >> L;
vector<ll> c(L);
for (int i = 0; i < L; ++i) {
cin >> c[i];
}
set<ll> s;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
for (int k = 0; k < L; ++k) {
s.insert(a[i] + b[j] + c[k]);
}
}
}
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
ll x;
cin >> x;
if (s.find(x) != s.end()) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC344C）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 344 C"""
n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))
L = int(input())
c = list(map(int, input().split()))
s = set()
for i in a:
for j in b:
for k in c:
s.add(i + j + k)
q = int(input())
x = list(map(int, input().split()))
for e in x:
print("Yes" if e in s else "No")こちらも「AC」と判定されました。
最後に
C問題は、計算量を考慮する問題が増えてくる印象です。それ以外には、実装が少し重たい問題も増えてくるでしょうか。
引き続き ABC の問題を紹介していきます。
