C++で解く:数字パネルを並べて作れるお小遣いの最大額を求めるプログラム

3つの整数 A、B、C が与えられます。ここで次のようなゲームを考えてみましょう。「整数パネル」が3枚あり、それぞれに1から9までの数字が1つずつ書かれています。また、「+」記号が書かれた「演算子パネル」が1枚あります。プレイヤーはこれら4枚のパネルを左から右へ並べ、X+Y の形の式を作らなければなりません。そして、その式の計算結果がもらえるお小遣いの金額になります。

この記事では、このゲームで得られるお小遣いの最大額を求める方法を解説します。

具体例

例えば、入力が A = 1、B = 5、C = 2 の場合、出力は 53 になります。これは、パネルを「52+1」という順序で並べたときにお小遣いが最大になるためです。

解き方のアプローチ

この問題は貪欲法の考え方で非常にシンプルに解くことができます。ポイントは、2桁の数値を作る際に、できるだけ大きな数字を十の位に配置した方が合計が大きくなるという点です。したがって、以下の手順で答えを求めます。

1. A、B、C を配列 V に格納する
2. 配列 V を昇順にソートする
3. ans = V[2] × 10 + V[1] + V[0] を計算する
4. ans を返す

ソート後、最も大きい数 V[2] を十の位に置いて2桁の数を作り、残りの2つの数 V[1] と V[0] を一の位側に加算します。こうすることで、常に最大の結果が得られます。要素数が3個のみのため、計算量は事実上 O(1) と非常に効率的です。

C++での実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;

int solve(int A, int B, int C){
    vector<int> V = { A, B, C };
    sort(V.begin(), V.end());
    int ans = (V[2] * 10) + V[1] + V[0];
    return ans;
}

int main(){
    int A = 1;
    int B = 5;
    int C = 2;
    cout << solve(A, B, C) << endl;
}

入力

1, 5, 2

出力

53

まとめ

この問題のように、パネルや数字の並び替えで最大値・最小値を求める問題では、「大きい数字を上位の桁に配置する」という貪欲な戦略が有効です。ソートさえ行えば答えは一行で導けるため、競技プログラミングの入門者にとっても取り組みやすい良問といえます。