C++で整数文字列に含まれる6の倍数となる部分文字列の個数を効率的に求める方法

本記事では、数字のみで構成された文字列が与えられたとき、その中に6で割り切れる部分文字列がいくつ含まれるかを求める問題を解説します。入力は数字の文字列として与えられますが、6で割り切れるかどうかの判定は、文字コード(ASCII値)ではなく、整数として扱って行う点に注意してください。

問題の例

入力:

str = "648"

出力:

3

説明:

部分文字列「6」「48」「648」が6で割り切れます。

入力:

str = "38342"

出力:

4

説明:

部分文字列「3834」「342」「834」「42」が6で割り切れます。

全探索(ブルートフォース)によるアプローチ

最もシンプルな方法は、取り得るすべての部分文字列を生成し、それぞれが6で割り切れるかどうかを順番に確認することです。割り切れる場合はカウントを1ずつ増やしていきます。この方法は実装が簡単ですが、すべての部分文字列を調べる必要があるため、時間計算量はO(n²)となり、文字列が長くなると処理に時間がかかります。

サンプルコード(C++)

#include <bits/stdc++.h>
using namespace std;
int
str_to_int (string str, int i, int j) {
   int temp = 0;
   for (; i <= j; i++) {
      temp = temp * 10 + (str[i] - '0');
   }
   return temp;
}
int main () {
   char str[] = "24661";
   int n = strlen (str);
   int count = 0;
   for (int i = 0; i < n; i++) {
      for (int j = i; j < n; j++) {
         int temp = str_to_int (str, i, j);
         if (temp % 6 == 0) count++;
      }
   }
   cout << count << endl;
   return 0;
}

出力

6

動的計画法を用いた効率的なアプローチ

ある数が6で割り切れるための条件は次の2つです。

• その数の最後の桁(下一桁)が偶数であること(2で割り切れること)
• その数の各桁の合計が3の倍数であること(3で割り切れること)

この性質を利用すると、動的計画法(DP)によって効率的に答えを求められます。

ここで、f(i, s) を「i番目のインデックスから始まる部分文字列のうち、桁の合計を3で割った余りがsとなるものの個数」と定義します。求めたい答えは、すべての開始位置iに対する Σf(i, 0) です。

文字列のi番目の桁を a とすると、f(i, s) からは「i + 1番目から始まる偶数の部分文字列」の情報が得られます。さらに、(a + s) が3で割り切れる場合、新たに1つの部分文字列が条件を満たします。したがって、次の漸化式が成り立ちます。

f(i, s) = f(i + 1, (s + a) % 3) + (a % 2 == 0 かつ (a + s) % 3 == 0)

サンプルコード(C++)

#include <bits/stdc++.h>
using namespace std;
int find(int i, int s, char str[], int dp[][3]){
   // 文字列の末尾に到達した場合
   if (i == strlen(str))
      return 0;
   // すでに計算済みの状態であれば結果を返す(メモ化)
   if (dp[i][s] != -1)
      return dp[i][s];
   int a = str[i] - '0';
   int ans = ((a+s)%3 == 0 && a%2 == 0) + find(i+1, (s+a)%3, str, dp);
   return dp[i][s] = ans;
}
int main(){
   char str[] = "24661";
   int n = strlen(str);
   // すべての状態を保存するためのDP配列
   int dp[n+1][3];
   memset(dp, -1, sizeof dp);
   int count = 0;
   for (int i = 0; i < n; i++){
      // 桁が0の場合は、それ自体が6の倍数となるためカウント
      if (str[i] == '0')
         count++;
      // 直前の合計の剰余(3で割った余り0)を再帰関数に渡す
      else
         count += find(i, 0, str, dp);
   }
   cout << "6で割り切れる部分文字列の個数: " << count << endl;
   return 0;
}

出力

6で割り切れる部分文字列の個数: 6

時間計算量: O(N)

全探索ではO(n²)かかっていた処理が、動的計画法とメモ化を組み合わせることで線形時間O(N)まで高速化できる点が、このアプローチの大きな利点です。

まとめ

本記事では、動的計画法を活用して、整数文字列に含まれる6の倍数となる部分文字列の個数を効率的に求める方法を学びました。紹介したロジックは、C言語、Java、Pythonなど他のプログラミング言語でも同様に実装できます。アルゴリズムの理解と実装力向上の参考にしていただければ幸いです。