C++で指定範囲内の数値のうち数字dがちょうどK回出現する個数を求める方法

整数の範囲(開始値 start から終了値 end まで)と、変数 k および d が与えられます。この課題では、指定された範囲内の数値のうち、数字 d がちょうど k 回出現するものの個数を求めます。

具体例

入力: start = 10, end = 100, d = 4, K = 2

出力: 数字dがちょうどK回出現する範囲内の数値の個数: 1

説明: 範囲は10から100までです。この範囲で数字4がちょうど2回出現する数値は「44」のみであるため、個数は1となります。

入力: start = 10, end = 100, d = 6, K = 1

出力: 数字dがちょうどK回出現する範囲内の数値の個数: 8

説明: 範囲は10から100までです。数字6がちょうど1回出現する数値は、16、26、36、46、56、76、86、96の8個です。66は6が2回出現し、K回より多いため対象から除外されます。

プログラムで使用するアプローチ

• 変数startからendまでの整数範囲を作成し、変数dとkを宣言して値を設定します。その後、処理用の関数にデータを渡します。
• vector型の変数(ここではvec)を作成します。
• valが0になるまでwhileループを回し、ループ内ではval % 10の値をvecにpush_backし、valをval / 10で更新します。これにより数値を1桁ずつ分解して格納します。
• STLのreverse関数をvec.begin()とvec.end()を引数に呼び出し、桁の並びを反転させます。
• memsetを使用して、メモ化用配列arrの全要素を-1で初期化します。
• set_total(0, 0, 0, 0, vec)を返します。この関数が、条件を満たす数値の個数を再帰的に計算します。
• set_total関数の内部処理は以下のとおりです。
  • placeがvecのサイズと等しい場合、tempがKと等しければ1を、そうでなければ0を返します。
  • arr[place][temp][val][rem]が-1でない場合(すでに計算済みの場合)、その値をそのまま返します。
  • 結果を格納する変数countを宣言します。
  • 変数temp_2を宣言し、valが1の場合は9、それ以外の場合はvec[place]を設定します。
  • iを0からtemp_2までループし、iがdと等しい場合、かつ(dが0でない、またはdが0かつremが1)の場合にtotalを1増やします。
  • 変数total_2を宣言し、valの値を設定します。
  • iがvec[place]より小さい場合、total_2を1に設定します。これは、以降の桁を自由に選べることを意味します。
  • set_totalの再帰呼び出し結果をcountに加算します。
  • arr[place][temp][val][rem] = countを返します。

サンプルコード

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

const int MAX = 20;
int arr[MAX][MAX][2][2];
int d, K;

int set_total(int place, int temp, int val, int rem, vector<int> vec) {
    if (place == vec.size()) {
        if (temp == K) {
            return 1;
        }
        return 0;
    }
    if (arr[place][temp][val][rem] != -1) {
        return arr[place][temp][val][rem];
    }
    int count = 0;
    int temp_2 = (val ? 9 : vec[place]);

    for (int i = 0; i <= temp_2; i++) {
        int total = temp;
        if (i == d) {
            if (d != 0 || (!d && rem)) {
                total++;
            }
        }
        int total_2 = val;
        if (i < vec[place]) {
            total_2 = 1;
        }
        count += set_total(place + 1, total, total_2, rem || (i != 0), vec);
    }
    return arr[place][temp][val][rem] = count;
}

int occurrence_d(int val) {
    vector<int> vec;
    while (val) {
        vec.push_back(val % 10);
        val = val / 10;
    }
    reverse(vec.begin(), vec.end());
    memset(arr, -1, sizeof(arr));
    return set_total(0, 0, 0, 0, vec);
}

int main() {
    int start = 10;
    int end = 100;
    d = 4, K = 2;
    int count = occurrence_d(end) - occurrence_d(start - 1);
    cout << "数字dがちょうどK回出現する範囲内の数値の個数: " << count;
    return 0;
}

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

出力

数字dがちょうどK回出現する範囲内の数値の個数: 1