【C++】長さNの数字列を、いずれかの1桁がK回以上出現するように変換する方法

はじめに

このチュートリアルでは、長さNの数値を変換して、いずれか1つの数字（0〜9）が少なくともK回含まれるようにするプログラムを、C++を用いて解説します。

問題の概要

長さNの数値（数字列）が与えられます。私たちのタスクは、与えられた数値のいくつかの桁を書き換えて、どれか1つの数字が少なくともK回繰り返されるようにすることです。同時に、この操作にかかるコストも計算する必要があります。ここでいうコストとは、元の数字と書き換え後の数字の差の絶対値の合計のことです。最終的に、コストが最小となる変換後の数値と、その最小コストを出力します。

アルゴリズムの考え方

この問題は、目標となる数字を0〜9のそれぞれについて試す貪欲法で解くことができます。手順は以下の通りです。

1. まず、対象の数字が元の数値に既に何個含まれているかを数えます。
2. 必要な個数Kに足りない場合は、対象の数字との差が小さい数字（差1、差2…）から順に、置き換えの候補を探します。
3. 対象より大きい数字は左端側から、対象より小さい数字は右端側から置き換えることで、変換後の数値をできるだけ小さく保ちます。
4. 各候補について得られたコストと変換後の数値を比較し、全体で最小となる組み合わせを出力します。

C++での実装例

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

// 最小コストと最終的な数値を計算する関数
int get_final(int n, int k, string a){
    int modtemp; // 変更にかかったコストの合計
    int co;      // 目標の数字への変更数
    string temp; // 変換途中の数値
    // 最小コストとそのときの数値を保持
    pair<int, string> ans = make_pair(INT_MAX, "");
    for (int i = 0; i < 10; i++) {
        temp = a;
        modtemp = 0;
        co = count(a.begin(), a.end(), i + '0'); // 既に出現している個数をカウント
        for (int j = 1; j < 10; j++) {
            if (i + j < 10) {
                // 目標より大きい数字を目標の数字へ置き換え（左端から走査）
                for (int p = 0; p < n; p++) {
                    if (co <= k)
                        break;
                    if (i + '0' == temp[p] - j) {
                        temp[p] = i + '0';
                        modtemp += j;
                        co++;
                    }
                }
            }
            if (i - j >= 0) {
                // 目標より小さい数字を目標の数字へ置き換え（右端から走査）
                for (int p = n - 1; p >= 0; p--) {
                    if (co >= k)
                        break;
                    if (i + '0' == temp[p] + j) {
                        temp[p] = i + '0';
                        modtemp += j;
                        co++;
                    }
                }
            }
        }
        // 以前の最小コストより小さければ更新
        ans = min(ans, make_pair(modtemp, temp));
    }
    cout << ans.first << endl << ans.second << endl;
}
int main(){
    int n = 5, k = 4;
    string a = "21122";
    get_final(n, k, a);
    return 0;
}

出力

1
21222

出力の解説

n = 5、k = 4、入力文字列「21122」の場合、先頭の「1」を「2」に書き換えると、数字「2」が4回出現する数値「21222」が得られます。このときのコストは |1 − 2| = 1 となり、これが最小です。したがって、プログラムは最小コスト「1」と変換後の数値「21222」を出力します。

まとめ

本記事では、長さNの数値を、いずれか1桁がK回以上出現するように変換し、その最小コストを求めるC++プログラムを紹介しました。0〜9の各数字を目標として全探索し、近い数字から順に置き換えていくのがポイントです。計算量はO(10 × 9 × N)程度に収まるため、Nがある程度大きくなっても高速に動作します。