JOI 一次予選 2023 (第 2 回) D - 点数 (6Q, 難易度 2)

「検索」をしながらのシミュレーション！

• 問題へのリンク

問題概要

長さ の数列 と、長さ の数列 が与えられる。

回のゲームをする。最初の得点は 0 点である。

回目のゲームでは、得点が 点増加する。ただし、増加したあとの得点が、もし数列 の中に含まれるならば、得点は 0 点になる。

制約

• 
• 
• 

考えたこと

この問題の難しいところは、更新後の得点が、数列 に含まれるかを判定するというところだと思われる。

一つの方法として、C++ であれば集合型 set 型を用いるのが楽だと思われる。set 型変数 S に、要素 x が含まれているかどうかを判定する処理は

if (S.count(x)) {

}

と書ける。これを利用して、実装しよう。

コード

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

int main() {
    int N, M;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    cin >> M;
    set<int> S;
    for (int i = 0; i < M; ++i) {
        int B;
        cin >> B;
        S.insert(B);
    }

    int res = 0;
    for (int i = 0; i < N; ++i) {
        res += A[i];
        if (S.count(res)) res = 0;
    }
    cout << res << endl;
}

考えたこと