問題概要

$1, 2, \dots, N$ を 2 個ずつ集めてできる $2N$ 個の整数から、1 個の整数を除外した。

そうした $2N - 1$ 個の整数を並べてできる数列 $A_{1}, A_{2}, \dots, A_{2N - 1}$ が与えられる。

最初に除外した整数の値を答えよ。

制約

$1 \le N \le 100$

解法

このくらいの難易度の問題から、次のようなスキルが必要になってくる。

数列 $A_{1}, A_{2}, \dots, A_{N}$ に対して、次のように定義される配列を考える。

con[v] ← 数列 $A_{1}, A_{2}, \dots, A_{N}$ の中に、整数値 $v$ が何個あるか

たとえば、 $A = \lbrack 1, 4, 2, 1, 3, 4, 3 \rbrack$ のとき、求める配列は次のようになる。

con[1] = 2
con[2] = 1
con[3] = 2
con[4] = 2

このような集計処理は、次のように実装できる。ここで、今回は数列 $A_{1}, A_{2}, \dots, A_{N}$ に含まれる値の最大値が $N$ なので、配列 con のサイズを $N+1$ としている。

vector<int> con(N + 1, 0);
for (int i = 0; i < N * 2 - 1; ++i) {
    ++con[A[i]];
}

このような配列 con を求めたあとは、con[1], con[2], ..., con[N] のうち、2 ではなく 1 であるものがあるので、それを答えればよい。

コード

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

int main() {
    int N;
    cin >> N;
    vector<int> con(N + 1, 0);
    for (int i = 0; i < N * 2 - 1; ++i) {
        int A;
        cin >> A;
        ++con[A];
    }
    int res;
    for (int i = 1; i <= N; ++i) {
        if (con[i] == 1) {
            res = i;
        }
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOI 一次予選 2023 (第 1 回) D - 二人三脚 (6Q, 難易度 2)

問題概要

制約

解法

コード