【AtCoder】ABC 446 B - Greedy Draft

2026-03-02

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

問題概要

$N$ 人の客と $M$ 本の缶ジュースがある。

客 $i$ は長さ $L_i$ の希望リストを持っていて、希望リストの先頭から $j$ 番目は缶ジュース $X_{i,j}$ である。任意の客 $i$ に対して、客 $i$ の希望リストに載っている番号 $X_{i, 1}, \dots, X_{i, L_i}$ は相異なる。

これから客 $1, \dots, N$ が番号の小さい方から順に、以下にしたがって自分が飲む飲料を選ぶ。

その時点で誰にも選ばれていない缶ジュースの番号が自分の希望リストに存在する場合、そのうち先頭に最も近い番号の缶ジュースを選ぶ。そうでない場合は水を選ぶ。

それぞれの客がどの飲料を得るかを求めよ。

制約

$1 \leq N, M \leq 100$
$1 \leq L_i \leq M$ ( $1 \leq i \leq N$ )
入力される値はすべて整数

考察

各缶ジュースが既に選ばれたか否かを管理するフラグ配列を用意し、客 $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, M;
11.    cin >> N >> M;
12. 
13.    vector<bool> selected(N, false);
14.    rep(i, 0, N)
15.    {
16.        int L;
17.        cin >> L;
18.        vector<int> X(L);
19.        rep(j, 0, L) cin >> X[j], X[j]--;
20. 
21.        int ans = 0;
22.        rep(j, 0, L)
23.        {
24.            if (!selected[X[j]])
25.            {
26.                selected[X[j]] = true;
27.                ans = X[j] + 1;
28.                break;
29.            }
30.        }
31. 
32.        cout << ans << endl;
33.    }
34. 
35.    return 0;
36.}