C++で要素を有効に塗り分けるための最小色数を求めるコード解説

n 個の要素を持つ配列 A があるとします。この配列の要素を、次の条件を満たすように色で塗り分けることを考えます。

• どの色を選んでも、その色で塗られたすべての要素は、同じ色グループ内の最小値で割り切れること。
• 使用する色の数はできるだけ少なくすること。

与えられたすべての数を有効な方法で塗り分けるために必要な、最小の色の数を求めるのがこの問題です。

例えば、入力が A = [10, 2, 3, 5, 4, 2] の場合、出力は 3 になります。1 番目の色で A[0] と A[3] を塗り、2 番目の色で A[2] を塗り、残りの 3 つの要素を 3 番目の色で塗ればよいからです。

解法のアプローチ

この問題を解くには、以下の手順に従います。

1. まず配列 A を昇順にソートします。
2. 各要素について、それより前にある（小さい）要素で割り切れるかどうかを確認します。
3. どの先行要素でも割り切れない場合、その要素は新しい色グループの最小値になる必要があるため、色を 1 つ増やします。

このアルゴリズムが正しく動作する理由は、ソート後の配列において、ある要素がそれより小さいいずれかの要素で割り切れるなら、その要素の色グループに追加できるためです。逆に、どの先行要素でも割り切れない要素は、必ず自身が属するグループの最小値にならざるを得ません。計算量は二重ループにより O(n²) となります。

アルゴリズムの擬似コード

n := A のサイズ
ans := 0
配列 A をソートする
i := 0 から i < n まで、i を 1 ずつ増やしながら繰り返す:
    ok := 1
    j := 0 から j < i まで、j を 1 ずつ増やしながら繰り返す:
        ok := ok AND (A[i] mod A[j] が 0 でなければ 1、そうでなければ 0)
    ans := ans + ok
ans を返す

C++ 実装例

理解を深めるために、実際の C++ コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A)
{
    int n = A.size();
    int ans = 0;
    sort(A.begin(), A.end());
    for (int i = 0; i < n; i++)
    {
        int ok = 1;
        for (int j = 0; j < i; j++)
        ok &= (A[i] % A[j] != 0);
        ans += ok;
    }
    return ans;
}
int main()
{
    vector<int> A = { 10, 2, 3, 5, 4, 2 };
    cout << solve(A) << endl;
}

入力

{ 10, 2, 3, 5, 4, 2 }

出力

3