C++で数字の連続区間を代替数字に置き換えて数値を最大化する方法

N桁の数値を最大化する問題を考えます。置き換えには、0から9までの各1桁の数字に対応する代替数字を10個格納した配列を使用します。

ただし、置き換えが可能なのは連続した一つの区間のみで、かつ一度だけという条件が課せられています。

入出力例

例1

入力:

N=1234, arr[]={3 ,0 ,1 ,5 ,7 ,7 ,8 ,2 ,9 ,4}

出力:

1257

説明:
3は代替数字5（arr[3]）に置き換えられます。
4は代替数字7（arr[4]）に置き換えられます。
これにより「1234」が「1257」へと最大化されます。

例2

入力:

N=5183, arr[]={3 ,0 ,1 ,5 ,7 ,7 ,8 ,2 ,9 ,4}

出力:

7183

説明:
5は代替数字7（arr[5]）に置き換えられます。1と8は代替数字が元の数字以下のため変更されず、ここで置き換え区間が確定します。

アルゴリズムのアプローチ

• 関数Max()内に、数値の桁数を格納するint型の変数Nを作成します。
• i=0からi<Nまでループし、代替数字が元の数字より大きくなる最初の桁を探します。
• 見つかった桁を代替数字に置き換えます。
• 代替数字が元の数字より小さくなる桁が現れるまで、後続の桁も順次置き換えます。これにより、損をしない最適な連続区間が自動的に選択されます。
• 置き換えによって利益が得られる桁が存在しない場合は、元の文字列をそのまま返します。

C++実装例

#include <bits/stdc++.h>
using namespace std;
string Max(string str, int arr[]){
   int N = str.size();
   // 文字列の末尾まで走査する
   for (int i = 0; i < N; i++) {
      // 代替数字の方が大きいかどうかを判定
      if (str[i] - '0' < arr[str[i] - '0']) {
         int j = i;
         // 代替数字が小さくなるまで置き換えを続ける
         while (j < N && (str[j] - '0' <= arr[str[j] - '0'])) {
            str[j] = '0' + arr[str[j] - '0'];
            j++;
         }
         return str;
      }
   }
   // 変更がない場合は元の文字列を返す
   return str;
}
// メイン関数
int main(){
   string str = "2075";
   int arr[] = {3 ,0 ,1 ,5 ,7 ,7 ,8 ,2 ,9 ,4 };
   cout <<" 区間を代替数字に置き換えて最大化した結果: " <<Max(str, arr);
   return 0;
}

出力結果

上記のコードを実行すると、以下の出力が得られます。

区間を代替数字に置き換えて最大化した結果: 2375

アルゴリズムのポイント

この貪欲法（グリーディ法）では、左端から走査し、初めて「代替数字が元の数字より大きい」位置を見つけた時点で置き換えを開始します。より上位の桁を大きくするほど数値全体が大きくなるため、この戦略が最適です。また、置き換えは「代替数字が元の数字以上である限り」継続されるため、損をする桁を含まない区間が選ばれます。計算量はO(N)と非常に効率的で、大きな桁数の数値にも高速に対応できます。