あるあるあるある。

問題概要

$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;
}