[Atcoder備忘録記事]AtCoder Beginner Contest 344 C問題

問題

入出力例

解法

全探索で解くことが可能ですが、普通にやると実行制限時間を超過してしまうため、少し工夫が必要です。
A+B+Cの全パターンを検索するのではなくA+Bの全パターンを検索した後にそれぞれのCをたしてXに一致するかどうかを探索します。

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;

int main() {
    int N, M, L, Q;
    cin >> N;
    vector<int> A(N);
    for(int i = 0; i < N; i++) cin >> A[i];
    
    cin >> M;
    vector<int> B(M);
    for(int i = 0; i < M; i++) cin >> B[i];
    
    cin >> L;
    vector<int> C(L);
    for(int i = 0; i < L; i++) cin >> C[i];
    
    cin >> Q;
    vector<int> X(Q);
    for(int i = 0; i < Q; i++) cin >> X[i];
    
    //回答の配列。全てをNoで埋めておく。
    vector<string> result(Q, "No");

    //A+BをABsumsに格納する。unorderd_setを用いて被りをなくす。
    unordered_set<int> ABsums;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            ABsums.insert(A[i] + B[j]);
        }
    }

    //ABsumsにCをたしてXに一致するかの確認
    for(int q = 0; q < Q; q++) {
        for(int l = 0; l < L; l++) {
            if(ABsums.find(X[q] - C[l]) != ABsums.end()) {
                result[q] = "Yes";
                break; 
            }
        }
    }

    for(int i = 0; i < Q; i++) {
        cout << result[i] << endl;
    }
}