【AtCoder】ABC 466 B - Representative Balls

2026-07-14

AtCoder/ABC/B問題 AtCoder/ABC/200点問題 AtCoder/灰Diff AtCoder/NoviSteps/6Q AtCoder/データ構造/set 競技プログラミング

B - Representative Balls

B - Representative Balls

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

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

問題概要

$N$ 個のボールがあり、 $i$ 番目のボールの色は $C_i$ 、大きさは $S_i$ である。

$k = 1, 2, \ldots, M$ について、色 $k$ のボールの大きさの最大値を出力せよ。ただし、色 $k$ のボールが存在しない場合は-1とすること。

制約

$1 \leq N, M \leq 100$
$1 \leq C_i \leq M$
$1 \leq S_i \leq 100$
入力される値はすべて整数

考察

ボールの色ごとにsetを用意して、その大きさを格納していく。

その後、各 $k$ について、対応するsetの末尾の値(最大値)を出力すればよい。

setの長さが $0$ の場合は、-1を出力するのを忘れない。

実装例

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.    vector<set<int>> colors(M);
13.    rep(i, 0, N) {
14.        int C, S;
15.        cin >> C >> S;
16.        colors[C - 1].insert(S);
17.    }
18. 
19.    rep(k, 0, M) {
20.        if (colors[k].size() == 0) {
21.            cout << -1 << endl;
22.        }
23.        else {
24.            cout << *colors[k].rbegin() << endl;
25.        }
26.    }
27. 
28.    return 0;
29.}

https://atcoder.jp/contests/abc466/submissions/77346746

実装時間: 5 分以内

コメント

setを使わなくても、色ごとにボールの大きさの最大値のみを1次元配列で管理するのでも良さそう。