C++で数値を合計が等しい複数のセグメントに分割できるか判定する方法

この記事では、ある数値を合計が等しい複数のセグメントに分割できるかどうかを判定するC++プログラムを紹介します。例えば、74325 という数値は (7)、(4, 3)、(2, 5) の3つの部分に分割でき、それぞれの合計はすべて 7 で等しくなります。

この問題を解決するためには、以下の手順に従います。

• 数値を文字列として受け取る
• 接頭辞和（プレフィックスサム）を格納するための配列を用意する
• 2番目の要素から最後の要素まで走査します。このとき最初のセグメントは 0 から i-1 までとなり、その合計は prefix_sum[i - 1] に格納されます
• 別の変数を使って 1 から n まで走査しながら、合計を加算し続けます
• 任意の時点で合計値が prefix_sum[i - 1] と一致すれば、そのセグメントは最初のセグメントと同じ合計を持つことになります
• セグメントの合計値を 0 に再初期化し、ポインタを進め続けます
• 途中でセグメントの合計が prefix_sum[i - 1] より大きくなった場合は、ループを抜けます
• 最後まで到達し、かつ最後のセグメントの合計が最初のセグメントの合計と一致していれば、その数値は等しい合計を持つセグメントに分割可能です

実装例

#include <iostream>
using namespace std;
bool canBeSegmented(string str) {
   int n = str.length();
   int prefix_sum[n];
   prefix_sum[0] = str[0] - '0';
   for (int i = 1; i < n; i++) {
      prefix_sum[i] = prefix_sum[i - 1] + (str[i] - '0');
   }
   for (int i = 1; i <= n - 1; i++) {
      int sum = prefix_sum[i - 1];
      int prev_sum = 0;
      int it = i;
      bool flag = false;
      while (it < n) {
         prev_sum += str[it] - '0';
         if (prev_sum == sum) {
            prev_sum = 0;
            flag = true;
         } else if (prev_sum > sum) {
            break;
         }
         it++;
      }
      if (prev_sum == 0 && it == n && flag) {
         return true;
      }
   }
   return false;
}
int main() {
   string s = "74325";
   if (canBeSegmented(s))
      cout << "Yes, This can be segmented into more than two segments";
   else
      cout << "No, This can not be segmented into more than two segments";
}

出力結果

Yes, This can be segmented into more than two segments

解説

このアルゴリズムでは、まず文字列として与えられた数値の各桁に対して接頭辞和を計算します。これにより、任意の区間の合計を効率的に参照できるようになります。

次に、最初のセグメントの終了位置を1桁目から順に試しながら、残りの桁を同じ合計値で区切れるかを検証します。途中で合計が基準値を超えた時点でその分割は不可能と判断できるため、無駄な探索を早期に打ち切ることができます。

計算量は外側のループと内側のループの組み合わせにより O(n²) となりますが、桁数がそれほど多くない数値であれば十分に高速に動作します。