C++でAの一部の桁をBの数字に置き換えてAの値を最大化する方法

この記事では、別の数Bに含まれる数字を使って数Aの一部の桁を置き換え、Aの値を最大化する問題をC++で解く方法を解説します。ただし、Aの値を最大化できない場合は、どの桁も置き換えません。

注意： Bの各数字は一度しか使用できません。

問題の理解

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

例1

A = "1221"
B = "1211"

出力：

Aの最大値：2221

解説： この例では、Bから「2」を選び、Aの先頭の「1」と置き換えます。Aの他の桁を「2」や「1」で置き換えても値が増加しないため、これが唯一の選択肢となります。

例2

A = "1002"
B = "3200"

出力：

Aの最大値：3202

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

この問題は、貪欲法（グリーディ法）を用いて効率的に解くことができます。手順は以下の通りです。

• Aの各桁が、Bの対応する数字より小さい場合にのみ置き換えます。
• まず、文字列Bを昇順にソートします。
• Aを左端から順に走査します。
• Bは右端（最も大きい数字）から順に走査します。
• Aの現在の桁がBの現在の数字より小さい場合は置き換えを行い、Aのポインタを進め、Bのポインタを戻します。

このアプローチにより、常に利用可能な最大の数字を、最も影響力の大きい上位の桁から優先的に適用できるため、結果としてAの値が最大になります。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
// a の最大化された値を返す関数
string valueup(string str1, string str2){
    // 数字を昇順にソート
    sort(str2.begin(), str2.end());
    int len1 = str1.length();
    int len2 = str2.length();
    int j = len2 - 1;
    for (int i = 0; i < len1; i++) {
        // b のすべての数字を使い切った場合
        if (j < 0)
            break;
        if (str2[j] > str1[i]) {
            str1[i] = str2[j];
            j--; // 使用した数字は再度使えない
        }
    }
    return str1;
}
// メイン関数
int main(){
    string a = "1204";
    string b = "4521";
    cout << valueup(a, b);
    return 0;
}

実行結果

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

5424

この例では、「1204」に対して「4521」の中から大きい数字を順に適用することで、最大値「5424」が得られます。計算量はソート部分がO(|B| log |B|)、置き換え処理がO(|A|)となるため、非常に効率的な解法です。