C++で数値にk個の区切り点を設定した後の最大セグメント値を求める方法

この問題では、大きな数値を表す文字列と、区切り点（ブレークポイント）の数を表す整数kが与えられます。私たちのタスクは、数値にk個の区切り点を設定した後に得られる最大のセグメント値を見つけるプログラムを作成することです。

つまり、文字列として与えられた数値の中にk個の区切り点を挿入することで生成できる、最大の数値を求める必要があります。

問題の理解

具体例を使って問題を確認しましょう。

入力： 文字列 = "45972"、k = 3

出力： 97

説明：

考えられるすべての分割パターンは以下の通りです。
45    9    7    2
4    59    7    2
4    5    97    2
4    5    9    72

この中で最大の数値は97です。

解決アプローチ：スライディングウィンドウ法

この問題を解くには、スライディングウィンドウ（sliding window）という手法が有効です。ここでのポイントは以下の通りです。

• ウィンドウサイズは「文字列の長さ − k」となります。これは、k個の区切り点を挿入したときに生成される最大セグメントの桁数に相当します。
• 指定されたサイズを持つすべての候補数値に対して、スライディングウィンドウ技法を用いて最大値を効率的に探索します。
• 各ステップで先頭の桁を削除し、末尾に新しい桁を追加するだけで値を更新できるため、毎回数値を最初から計算するよりも高速に処理できます。

C++による実装例

以下は、数値にk個の区切り点を設定した後の最大セグメント値を求めるC++プログラムです。

#include <bits/stdc++.h>
using namespace std;
int findMaxSegmentWithKbreaks(string &s, int k) {
   int window = s.length() - k;
   int MaxNumber = 0;
   for (int i=0; i<window; i++)
   MaxNumber = MaxNumber * 10 + (s[i] - '0');
   int slWindow = pow(10, window-1);
   int value = MaxNumber;
   for (int i = 1; i <= (s.length() - window); i++) {
      value = value - (s[i-1]- '0')*slWindow;
      value = value*10 + (s[i+window-1]- '0');
      MaxNumber = max(MaxNumber, value);
   }
   return MaxNumber;
}
int main() {
   string s = "45972";
   int k = 3;
   cout<<"Maximum segment value after putting "<<k<<" break points in a number = "<<findMaxSegmentWithKbreaks(s, k);
   return 0;
}

実行結果

Maximum segment value after putting 3 breakpoints in a number = 97

コードの解説

このプログラムの動作を順番に見ていきましょう。

1. まず、ウィンドウサイズを「文字列の長さ − 区切り点の数」で計算します。例では 5 − 3 = 2 桁となります。
2. 最初のウィンドウ（先頭からwindow桁分）の数値を構築し、初期の最大値として保存します。
3. その後、ウィンドウを1桁ずつ右にスライドさせます。具体的には、左端の桁の値を減算し、残りの値を10倍してから新しい右端の桁を加算します。
4. 各ステップで現在の値と最大値を比較し、より大きい方を最大値として更新します。

この手法により、時間計算量はO(n)となり、すべての分割パターンを総当たりで確認する方法と比べて大幅に効率的です。大きな数値を扱う場合でも、文字列ベースで処理するためオーバーフローの心配もありません。