C++プログラムで同じ色のボールを重複させずにすべて配布する方法

このチュートリアルでは、n個のボールをk人の生徒に、誰にも不満が出ない形で配布できるかどうかを判定する方法を解説します。

考え方はとてもシンプルです。異なる色のボールが合計n個あり、これらを生徒たちに配布します。ただし、どの生徒にも同じ色のボールを2個以上渡してはいけないというルールがあります。もし同じ色のボールを1人の生徒が複数個受け取る可能性があるなら、その配布は実行できません。

問題の例

具体的な例を見てみましょう。

入力

n = 10
k = 5
ballsColors = "rrrgbrbgbr"

出力

Yes

この例では、どの色のボールも生徒の数(k=5)を超えていません。そのため、どの生徒も同じ色のボールを複数個持つことなく、全員に配布できます。

解決手順

この問題は、次の手順で解くことができます。

• n(ボールの総数)、k(生徒の人数)、ボールの色の文字列を初期化します。
• 各色の出現回数を格納するためのマップ(map)を用意します。
• ボールの色を先頭から走査し、色ごとの出現回数をカウントします。
• 各色のカウントを確認します。
  • ある色のボールの数が生徒の人数kより大きい場合、配布は不可能です。
  • そうでなければ、配布可能です。
• 結果を出力します。

C++での実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
bool canDistributeBalls(string ballsColors, int n, int k) {
    map<char, int> charCount;
    for (int i = 0; i < n; i++) {
        charCount[ballsColors[i]]++;
    }
    map<char , int >::iterator itr;
    for(itr = charCount.begin(); itr != charCount.end(); itr++) {
        if (itr->second > k) {
            return false;
        }
    }
    return true;
}
int main() {
    int n = 10, k = 5;
    string ballsColors = "rrrgbrbgbr";
    if (canDistributeBalls(ballsColors, n, k)) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次のような結果が得られます。

Yes

まとめ

このように、各色のボールの個数をマップでカウントし、その最大値が生徒の人数k以下であるかを確認するだけで、配布の可否を簡単に判定できます。計算量はO(n log n)(std::map使用時)であり、非常に効率的なアプローチです。なお、計算量をさらに抑えたい場合は、unordered_mapや配列によるカウントも検討するとよいでしょう。チュートリアルの内容について質問がある場合は、コメント欄でお気軽にお知らせください。