【AtCoder】ABC 462 B - Gift

2026-06-14

AtCoder/ABC/B問題 AtCoder/ABC/200点問題 AtCoder/灰Diff AtCoder/NoviSteps/5Q AtCoder/アルゴリズムの基礎/forループ AtCoder/アルゴリズムの基礎/多次元配列競技プログラミング

B - Gift

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 70 / NoviSteps: 5Q / 配点: 200 点

問題概要

$N$ 人がギフトを送り合っており、人 $i$ は人 $A_{i,1},A_{i,2},\ldots,A_{i,K_i}$ の $K_i$ 人にギフトを送った。

$i=1,2,\ldots,N$ に対し、人 $i$ にギフトを送った人を全て求めよ。

制約

$2\le N\le 100$
$1\le K_i\le N-1$
$1\le A_{i,1} < A_{i,2} < \cdots < A_{i,K_i}\le N$
$A_{i,j} \neq i$
入力される値は全て整数

考察

$B_{ij}$ を「人 $i$ が人 $j$ からギフトを受け取った」ことを表す二次元配列とすると、 $1 \leq i \leq N, \, 1 \leq j \leq K_i$ に対して, 1次元配列 $B_{A_{i,j}}$ に $i$ を追加していけばよい。

実装時はインデックスの扱いに注意すること。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.// ======================================== //
7. 
8.int main()
9.{
10.    int N;
11.    cin >> N;
12. 
13.    vector<vector<int>> ans(N);
14.    rep(i, 0, N) {
15.        int K;
16.        cin >> K;
17.        rep(j, 0, K) {
18.            int A;
19.            cin >> A;
20.            ans[A - 1].push_back(i + 1);
21.        }
22.    }
23. 
24.    rep(i, 0, N) {
25.        cout << ans[i].size();
26.        for (auto a : ans[i])
27.            cout << " " << a;
28.        cout << endl;
29.    }
30. 
31.    return 0;
32.}