けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

2019-09-15

Codeforces Round #584 (Div. 1 + Div. 2) A. Paint the Numbers (R900)

誤読して大きく出遅れた...

問題へのリンク

問題概要

$N$ 個の整数 $a_1, a_2, \dots, a_N$ があたえられる。これを何個かのグループに分けて、各グループについて「グループ内のすべての整数がグループ内の最小値で割り切れる」という条件を満たすようにしたい。

これを実現するためのグループ数の最小値を求めよ。

制約

$1 \le N \le 100$
$1 \le a_i \le 100$

考えたこと

まず $a_i$ のうちの最小値 $mi$ に着目すると、 $mi$ はいずれかのグループにおいて最小となる。そのグループについて考えてみよう。

そうすると $mi$ で割り切れるやつは全部一つのグループにしてしまってよいことがわかる (理由: $mi$ で割り切れるやつを残しておくメリットはないため)。

$mi$ で割り切れるやつをグループとしてまとめてしまうと、 $mi$ で割り切れないやつが残る。残ったやつで同様の操作を繰り返せば OK。

とても模範的な Greedy 問題だと思う。

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

int main() {
    int N; cin >> N;
    set<long long> s;
    for (int i = 0; i < N; ++i) {
        long long a; cin >> a;
        s.insert(a);
    }

    int res = 0;
    while (!s.empty()) {
        long long v = *s.begin();
        for (auto it = s.begin(); it != s.end();) {
            if ((*it) % v == 0) {
                it = s.erase(it);
            }
            else ++it;
        }
        ++res;
    }
    cout << res << endl;
}