落ち着いて整理して考えよう。

問題概要

$N$ 人がいてそれぞれの AtCoder レーティングが与えれている。1 以上 4800 以下で、400 ごとに色が変わるという設定。

今、レーティング 3200 以上の人は自由に色を変えることができる。このとき、 $N$ 人の中に存在する色の種類数の最大値と最小値を求めよ。

制約

$1 \le N \le 100$

考えたこと

少し数学的思考が絡む問題だけど、落ち着いて丁寧に考えれば解ける。

最大値について

最大値の方は簡単だ。3200 以上の人を全員別々の色 (しかも 3200 未満の人たちの色とも別の色) にすればよい。

よって、求める最大値は次のようになる。

(0〜3200 の範囲で登場している色の個数) + (3200 以上の人数)

最小値について

今度は 3200 以上の人がなるべく一致するようにさせたい。ここで罠があって、全員が 3200 以上だったら、求める最小値は「1 通り」（全員を同じ色にする）である。このケースを見落としがちな気がする。

3200 未満の人が一人でもいたら、3200 以上の人は全員その人に色を合わせればよい。この場合は、求める最小値は

(0〜3200 の範囲で登場している色の個数)

コード

#include <iostream>
#include <set>
using namespace std;

int main() {
    int N; cin >> N;

    set<int> se; // 3200 以下で登場する色の種類数
    int over_num = 0; // 3200 以上の人数
    for (int i = 0; i < N; ++i) {
        int a; cin >> a;
        if (a >= 3200) ++over_num;
        else se.insert(a/400);
    }
        
    int Max = (int)se.size() + over_num;
    int Min = 0;
    if (se.size() == 0) Min = 1;
    else Min = (int)se.size();
        
    cout << Min << " " << Max << endl;
}