【C++】カードのデッキを同じ数字のグループ(X枚ずつ)に分割できるか判定する方法

問題概要

整数が書かれたカードのデッキが与えられます。このとき、X ≥ 2 となる整数 X を選び、デッキ全体を1つ以上のグループに分割できるかどうかを判定します。分割は以下の条件を満たす必要があります。

• 各グループはちょうど X 枚のカードで構成されている
• 同じグループ内のカードには、すべて同じ整数が書かれている

例えば、入力が deck = [1,2,3,4,4,3,2,1] の場合、出力は True になります。[1,1]、[2,2]、[3,3]、[4,4] という4つのグループに分割でき、それぞれのグループが2枚の同じ数字のカードで構成されているためです。

解法のアプローチ

この問題は「最大公約数(GCD)」を使うことで効率的に解けます。まず各数字の出現回数を求め、それらすべての最大公約数が2以上であれば、条件を満たす X が存在すると判断できます。具体的な手順は以下の通りです。

• マップ mp を定義する
• deck 内のすべての要素 x に対して、mp[x] を1ずつ増加させ、出現回数をカウントする
• mp のすべてのキーと値のペア x に対して、ans = gcd(ans, x.second) を計算する
• ans > 1 であれば true を返し、そうでなければ false を返す

なぜGCDで解けるのか?

ある数字が cnt 回出現するとき、その数字だけで構成されるグループのサイズ X は、cnt の約数である必要があります。すべての数字に対して共通の X が存在するためには、X が全出現回数の公約数でなければなりません。したがって、出現回数全体の最大公約数が2以上であれば、条件を満たす X ≥ 2 が必ず存在するというわけです。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool hasGroupsSizeX(vector<int>& deck) {
        unordered_map<int, int> mp;
        int ans;
        for (auto x : deck)
            mp[x]++;
        for (auto x : mp)
            ans = __gcd(ans, x.second);
        return (ans > 1);
    }
};
main(){
    Solution ob;
    vector<int> v = {1,2,3,4,4,3,2,1};
    cout << (ob.hasGroupsSizeX(v));
}

実行結果

入力

{1,2,3,4,4,3,2,1}

出力

1

出力が 1(true)となり、このデッキが条件を満たすグループに分割可能であることが確認できました。計算量は O(N log M)(N はカードの枚数、M は最大出現回数)程度に収まるため、大規模な入力にも対応できる効率的な解法です。