【C++】AとBが同数含まれるNより大きい最小の数を求めるアルゴリズム

問題概要

N、A、B の 3 つの値が与えられたとき、「数字 A と数字 B が同じ個数だけ含まれる、N 以上の最小の数」を求める問題です。具体例を見てみましょう。

N = 1234
A = 2
B = 3

この例では、数字 2 と 3 を組み合わせて数を作ります。ただし、それぞれの数字が数の中に現れる回数は等しくなければなりません。この条件を満たす 1234 以上の最小の数は 2233 です（2 が 2 個、3 が 2 個含まれています）。

アルゴリズム

基本的な考え方は、A と B を使って作れるすべての数を再帰的に生成し、その中から条件を満たす最小の数を見つけるというものです。

• A、B、N を初期化します。

• 再帰関数を実装します。

  • 現在の数が N 以上であり、かつ A と B の桁数が等しいかどうかを判定します。

  • 条件を満たしていれば、その数を返します。

  • 現在の数の末尾に A を追加した数で再帰呼び出しを行います。

  • 現在の数の末尾に B を追加した数で再帰呼び出しを行います。

  • 上記 2 つの結果のうち小さい方を返します。

なお、探索が無限に続かないよう、十分に大きな上限値（ここでは 10¹¹）に達した場合は打ち切るようにしています。

C++ による実装

以下は、上記のアルゴリズムを C++ で実装した例です。

#include <bits/stdc++.h>
using namespace std;
long getNextGreaterElement(long result, int A, int A_Count, int B, int B_Count, int N) {
    if (result > 1e11) {
        return 1e11;
    }
    if (A_Count == B_Count && result >= N) {
        return result;
    }
    return min(getNextGreaterElement(result * 10 + A, A, A_Count + 1, B, B_Count, N),
               getNextGreaterElement(result * 10 + B, A, A_Count, B, B_Count + 1, N));
}
int main() {
    int N = 1234;
    int A = 2;
    int B = 3;
    cout << getNextGreaterElement(0, A, 0, B, 0, N) << endl;
    return 0;
}

コードの解説

getNextGreaterElement 関数は、第 1 引数の result に現在までに作成した数を、A_Count と B_Count にそれぞれ使用済みの A・B の個数を受け取ります。result が N 以上になった時点で A と B の個数を比較し、等しければその数を候補として返します。再帰処理によって「末尾に A を足す経路」と「末尾に B を足す経路」の両方を網羅的に探索し、最終的に min で小さい方（＝条件を満たす最小の数）を選び出しています。

実行結果

上記のコードをコンパイルして実行すると、次のような結果が出力されます。

2233