Yuulis.log

トンネルを抜けるとそこは参照エラーであった。

トップ > AtCoder > 【AtCoder】ABC 344 C - A+B+C | 茶コーダーが解くAtCoder

【AtCoder】ABC 344 C - A+B+C | 茶コーダーが解くAtCoder

AtCoder ABC 灰Diff Diff: 100~299 set プログラミング

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 204

問題概要

3個の数列 A=\{A_1, A_2, ..., A_N\}, B=\{B_1, B_2, ..., B_M\}, C=\{C_1, C_2, ..., C_L\} と、数列 X=\{X_1, X_2, ..., X_Q\} が与えられる。各 i = 1, 2, ..., Q について、数列 A, B, C からそれぞれ1個ずつ要素を選び、和を X_i にできるかどうかを判定せよ。

制約

  • 入力は全て整数
  • 1 \leq N, M, L \leq 100
  • 0 \leq A_i, B_i, C_i \leq 10^8
  • 1 \leq Q \leq 2 \times 10^5
  • 0 \leq X_i \leq 3 \times 10^8

考察

A, B, C の各数列の要素数は 100 以下なので、 A_i + B_i + C_i が取り得る値は高々 100^3 = 10^6 通りしかない。まずはこれを求めてしまおう。

とはいえ、最大で 2 \times 10^5 個の X_i に対して判定を行う必要があるので、各 X_i についていちいち 10^6 通りの探索をしていたのでは間に合わない。

そこで、 C++ では連想コンテナに対してcount関数を使うことで計算量を抑えることができる ( C++20 ではcontainsも使用可) 。詳しくは

zenn.dev

を参照。なお、私のコードではデータ構造としてsetを用いたが、より高速化を狙うならunordered_setを使うのが良いだろう。

コード

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

#define rep(i, start, end) for (ll i = (start); i < (ll)(end); i++)

// ======================================== //

int main()
{
    int N, M, L, Q;
    vector<int> A, B, C, X;
    cin >> N;
    A.resize(N);
    rep(i, 0, N) cin >> A[i];
    cin >> M;
    B.resize(M);
    rep(i, 0, M) cin >> B[i];
    cin >> L;
    C.resize(L);
    rep(i, 0, L) cin >> C[i];
    cin >> Q;
    X.resize(Q);
    rep(i, 0, Q) cin >> X[i];

    set<int> s;
    rep(i, 0, N) rep(j, 0, M) rep(k, 0, L)
    {
        s.insert(A[i] + B[j] + C[k]);
    }

    rep(i, 0, Q)
    {
        if (s.count(X[i]) == 0)
            cout << "No" << endl;
        else
            cout << "Yes" << endl;
    }
}

atcoder.jp

実装時間: 10分