C++でキャンディを均等に分配するアルゴリズムの解説

問題概要

ここに偶数の長さを持つ配列があるとします。配列内の異なる数値はそれぞれ異なる種類のキャンディを表し、各数値は対応する種類のキャンディ1個を意味します。このキャンディを兄と妹に同数ずつ分配しなければなりません。そのうえで、妹が受け取れるキャンディの種類数の最大値を求めるのがこの問題の目的です。

例として、入力が [1,1,2,3] の場合を考えてみましょう。このときの出力は 2 となります。妹にキャンディ [2,3] を、兄にキャンディ [1,1] を渡すことで、妹は2種類の異なるキャンディを受け取れる一方、兄は1種類しか持てないためです。

解決のアプローチ

この問題は「ユニークな種類の数」と「妹がもらえる個数（全体の半分）」のどちらか小さい方が答えになる、という性質を利用して解けます。手順は以下の通りです。

• 集合（set）s を定義します。
• i := 0 から開始し、i がキャンディ配列のサイズ未満である間、i を1ずつ増やしながら次の処理を繰り返します。
  • candies[i] を集合 s に挿入します。
• 最後に、s のサイズと candies のサイズ ÷ 2 のうち小さい方を返します。

集合は重複する要素を自動的に排除するため、s のサイズは「キャンディの種類数」と一致します。種類数が全体の半分以上あれば、妹はすべて異なる種類のキャンディを half 分受け取れ、種類数が半分未満であれば、持っている全種類を受け取ることができます。

実装例

以下のC++による実装を見ると、より理解が深まるでしょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int distributeCandies(vector<int>& candies){
      unordered_set<int> s;
      for (int i = 0; i < candies.size(); i++)
         s.insert(candies[i]);
      return min(s.size(), candies.size() / 2);
   }
};
main(){
   Solution ob;
   vector<int> v = {1,1,2,3};
   cout << (ob.distributeCandies(v));
}

入力

{1,1,2,3}

出力

2

計算量について

この解法では、配列の各要素を一度ずつ走査して unordered_set に挿入するため、時間計算量は O(n) です。また、格納される要素は最大でも配列の要素数以下となるため、空間計算量も O(n) となります。unordered_set を使うことで平均 O(1) での挿入が可能になり、非常に効率的な実装になっています。