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

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

Codeforces Round #584 - Dasha Code Championship 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;
}