C++で数字列を切り分けて3の倍数の部分を最大化する方法

問題概要

この問題では、最大10⁵桁にもなる大きな整数値が与えられます。求めるのは、できるだけ多くの部分が3で割り切れるように数を切り分けたときに必要なカット（分割）回数の合計です。

具体例で問題を確認してみましょう。

• 入力：9216
• 出力：3
• 説明：数は「9｜21｜6」のように3つに分割されます。

解法のアプローチ

この問題を効率よく解くには、数の桁を左から順に走査しながら、累積の桁和を3で割った余りを記録していく方法が有効です。同じ余りが2回現れたということは、その間の部分の桁和が3の倍数になっていることを意味するため、その位置で切り分ければ3で割り切れる部分を作れます。

• 現在の桁だけでも3で割り切れる場合は、そこで区切ってカウントを1増やし、次の桁へ進みます。
• 現在の桁だけでは割り切れない場合は、隣接する桁と組み合わせて3の倍数になる区間を探します。

3の倍数の判定方法：ある数が3で割り切れるかどうかは、その数を構成する各桁の数字の合計が3で割り切れるかどうかで判断できます。この性質を利用すれば、巨大な数でも実際に割り算を行うことなく判定が可能です。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
int countMaximum3DivisibleNumbers(string number){
    int n = number.length();
    vector<int> remIndex(3, -1);
    remIndex[0] = 0;
    vector<int> counter(n + 1);
    int r = 0;
    for (int i = 1; i <= n; i++) {
        r = (r + number[i-1] - '0') % 3;
        counter[i] = counter[i-1];
        if (remIndex[r] != -1)
            counter[i] = max(counter[i], counter[remIndex[r]] + 1);
        remIndex[r] = i+1;
    }
    return counter[n];
}
int main() {
    string number = "216873491";
    cout<<"The number of 3 divisible number created by cutting "<<number<<" are : " <<countMaximum3DivisibleNumbers(number);
    return 0;
}

出力結果

The number of 3 divisible number created by cutting 216873491 are : 5

コードの解説

このアルゴリズムは、剰余の累積情報を利用した動的計画法（DP）として動作します。各変数の役割は以下の通りです。

• r：先頭から現在の桁までの桁和を3で割った余りを保持します。
• remIndex：各余り（0・1・2）が最後に現れた位置を記録します。初期状態では余り0が位置0に存在するとみなします。
• counter[i]：先頭からi桁目までで作れる「3で割り切れる部分」の最大数を表します。

走査中に同じ余りが再び現れた場合、前回その余りが出た位置との間の区間は必ず3の倍数になります。そこで counter[remIndex[r]] + 1 を候補として比較し、より大きい方を採用することで、全体の最大カット数を求められます。

計算量は数列の長さをnとするとO(n)、必要なメモリもO(n)であり、10⁵桁のような巨大な入力でも高速に処理できるのが特徴です。