C++で数値を2つの割り切れる部分に分割する方法

この問題では、数値として解釈できる文字列が与えられます。この文字列を2つの部分に分割し、前半部分が整数Aで割り切れ、後半部分が整数Bで割り切れるようにする必要があります。以下に入力例と出力例を示します。

入力 : str = "123", a = 12, b = 3
出力 : YES
12 3
「12」はaで割り切れ、「3」はbで割り切れます。

入力 : str = "1200", a = 4, b = 3
出力 : YES
12 00

入力 : str = "125", a = 12, b = 3
出力 : NO

本記事では、事前計算(前処理)を活用してプログラムを高速化し、より大きな入力サイズでも十分な速度で動作させられるようにする方法を解説します。

解決アプローチ

このアプローチでは、文字列に対して2方向のループを実行します。1つ目は先頭から末尾へ向かうループ、2つ目は末尾から先頭へ向かうループです。各位置において、前方向のループでは「先頭からその位置までの数値」をAで割った剰余を、後ろ方向のループでは「その位置から末尾までの数値」をBで割った剰余をそれぞれ求めます。こうして得られた剰余情報をもとに、条件を満たす分割点を見つけ出すことができます。

アルゴリズムのポイント

桁数が多い数値をそのまま整数として扱うとオーバーフローする恐れがあるため、「直前の位置までの剰余 × 10 + 現在の桁の値」をその都度A(またはB)で割ることで、常に小さな値のみを扱うのがポイントです。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
void divisionOfString(string &str, int a, int b){
    int n = str.length();
    vector<int> mod_a(n+1, 0); // 接頭辞部分の剰余を格納する配列
    mod_a[0] = (str[0] - '0')%a;
    for (int i=1; i<n; i++) // 前方向ループ:Aで割った剰余を計算
        mod_a[i] = ((mod_a[i-1]*10)%a + (str[i]-'0'))%a;
    vector<int> mod_b(n+1, 0);
    mod_b[n-1] = (str[n-1] - '0')%b;
    int power10 = 10; // 最後のインデックスは代入済みなので10から開始
    for (int i= n-2; i>=0; i--){ // 後ろ方向ループ:Bで割った剰余を計算
        mod_b[i] = (mod_b[i+1] + (str[i]-'0')*power10)%b;
        power10 = (power10 * 10) % b;
    }
    for (int i=0; i<n-1; i++){ // 分割点を探す
        if (mod_a[i] != 0) // 剰余が0でない位置はすべてスキップ
            continue;
        if (mod_b[i+1] == 0){ // 次の位置の剰余も0なら、そこが分割点
            cout << "YES\n";
            /*******形成された分割を出力*******/
            for (int k=0; k<=i; k++)
                cout << str[k];
            cout << " ";
            for (int k=i+1; k < n; k++)
                cout << str[k];
            return;
        }
    }
    cout << "NO\n"; // 見つからなければNOを出力
}
// メイン関数
int main(){
    string str = "123"; // 対象の文字列
    int a = 12, b = 3;
    divisionOfString(str, a, b);
    return 0;
}

出力結果

YES
12 3

コードの解説

この実装では、考えられるすべての分割位置についての剰余を事前に計算しています。まず前方向のループで、先頭からその位置までの数値をAで割った剰余を配列mod_aに順番に格納していきます。続いて後ろ方向のループで、その位置から末尾までの数値をBで割った剰余を配列mod_bに格納します。

その後、各位置iを走査し、mod_a[i]が0(前半部分がAで割り切れる)であり、かつmod_b[i+1]も0(後半部分がBで割り切れる)となる位置が見つかれば、そこが求める分割点です。「YES」とともに実際の分割結果を出力して処理を終了し、最後まで見つからなければ「NO」を出力します。

計算量

時間計算量はO(n)、空間計算量もO(n)です(nは文字列の長さ)。単純な全探索では分割点ごとに剰余を再計算する必要がありO(n²)かかりますが、この方法なら線形時間で処理でき、非常に長い文字列にも対応できます。

まとめ

本記事では、数値を2つの割り切れる部分に分割する問題を取り上げました。C++による実装例と、剰余の事前計算によって効率化するアプローチについて学びました。同じロジックはC、Java、Pythonなどの他の言語でも同様に記述できます。本チュートリアルが皆さんの学習のお役に立てば幸いです。