A - Dreamoon and Ranking Collection (Codeforces Round #631 Div. 2)

問題文を理解するのが一番の難関かも。

問題

https://codeforces.com/contest/1330/problem/A

問題概要

各項が1以上100以下の整数で構成された長さnの数列がある。この数列にx個の整数を新たに加えたとき、最大で1からいくつまで整数を連続して並べることが可能か答えよ。

考察

問題分に忠実に、1から順に埋まっていないところをx個だけ埋めて、いくつまで埋まったかを見ればよいです。

実装上の注意として、配列やループの上限を中途半端に取るとWAやRE（範囲外アクセス）が出やすいので、充分に大きい値で取っておくのがこの問題の場合特に有効です。

Codeforces Round #631 Editorial - Codeforcesでも、「O(n)でも解けるけどバグりやすいよ！」って書いてありますね。

なお私も実戦では1RE出しました。ぐぬぬ。

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, x;
        cin >> n >> x;
        // n + x は超えないので、200取っておく（0-indexedなので201）
        vector<bool> v(201, false);

        // まず入力値で埋める
        int a;
        for (int i = 0; i < n; i++) {
            cin >> a;
            v[a] = true;
        }

        // 1から順に埋まっていないところをx個だけ埋める
        int remain = x;
        for (int i = 1; i <= 200; i++) {
            if (!v[i]) {
                v[i] = true;
                remain--;
                if (remain <= 0) {
                    break;
                }
            }
        }

        // 1から順に埋まっているかどうかをチェック
        for (int i = 1; i <= 201; i++) {
            if (!v[i]) {
                // 埋まっていない場合、その一つ前が答え
                cout << i - 1 << endl;
                break;
            }
        }
    }
}