C++で解くキャンディ分配問題：隣接する子供の評価値に基づく最小キャンディ数の求め方

問題概要

N人の子供が一列に並んでおり、それぞれの子供には評価値（rating）が割り当てられています。これらの子供たちにキャンディを配る際、以下の条件を満たす必要があります。

• すべての子供は最低1個のキャンディを受け取る必要があります。

• 評価値が高い子供は、隣にいる子供よりも多くのキャンディを受け取る必要があります。

このとき、配るべきキャンディの最小個数を求めます。

例えば、入力が [1, 1, 3] の場合、出力は 4 となります。このとき、子供たちはそれぞれ 1個、1個、2個 のキャンディを受け取ることになります。

解法のアプローチ

この問題は、左から右、右から左の2回の走査（2パス方式）で効率的に解くことができます。手順は以下の通りです。

1. 配列 ratings のサイズを n とし、サイズ n の配列 dp を作成して、すべての要素を 1 で初期化します（まず全員に1個ずつ配るため）。

2. 変数 ret を 0 で初期化します。

3. 左から右へ走査します（i を 1 から n - 1 まで）。

   • ratings[i] > ratings[i - 1] の場合、dp[i] := dp[i - 1] + 1 とします。

4. 右から左へ走査します（i を n - 2 から 0 まで）。

   • ratings[i] > ratings[i + 1] の場合、dp[i] := max(dp[i], dp[i + 1] + 1) とします。

5. ret := dp の全要素の合計とします。

6. ret を返します。

C++による実装例

以下の実装例を見て、理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int candy(vector<int>& ratings) {
      int n = ratings.size();
      vector <int> dp(n, 1);
      int ret = 0;
      for(int i = 1; i < n; i++){
         if(ratings[i] > ratings[i - 1]){
            dp[i] = dp[i - 1] + 1;
         }
      }
      for(int i = n - 2; i >= 0; i--){
         if(ratings[i] > ratings[i + 1]){
            dp[i] = max(dp[i], dp[i + 1] + 1);
         }
      }
      for(int i = 0; i < n; i+=1){
         ret += dp[i];
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,1,3};
   cout << (ob.candy(v));
}

入力

[1,1,3]

出力

4

計算量

このアルゴリズムの時間計算量は O(n)、空間計算量は O(n) です。配列を2回走査するだけで済むため、非常に効率的な解法となっています。