C++で特殊数の合計桁数を効率的に求める方法

問題概要

整数 k が与えられます。すべての桁が同じ数字で構成されている数を「特殊数(スペシャルナンバー)」と呼びます。例えば、1、11、111、1111 などが特殊数に該当します。

特殊数は 1, 11, 111, 1111, 2, 22, 222, 2222, 3, 33, 333, 3333, … という順序で数え上げます。このとき、k までに現れるすべての特殊数に含まれる桁数の合計を求めるのが課題です。なお、k の値は 10000 以下であるものとします。

例えば、入力が k = 9999 の場合、出力は 90 になります。

解き方のアプローチ

この問題を解くためには、次の手順に従います。

• k を文字列に変換します。
• サイズ5の配列 v を {0, 1, 3, 6, 10} として定義します。これは、桁数ごとの累積和(1桁なら 1、2桁なら 1+2=3、3桁なら 1+2+3=6、4桁なら 1+2+3+4=10)を表しています。
• 「(先頭の数字 − 1) × 10 + v[文字列の長さ]」を計算して出力します。

ロジックの解説

各数字 d(1〜9)について、d, dd, ddd, dddd という4つの特殊数が存在し、その桁数の合計は 1+2+3+4 = 10 桁になります。したがって、k の先頭の数字より小さい数字については、それぞれ 10 桁ずつ加算されます。さらに、k の先頭の数字と同じ数字については、k の桁数に対応する累積和 v[桁数] を加算します。

例えば k = 9999 の場合を考えてみましょう。1〜8 の各数字はそれぞれ 10 桁ずつで計 80 桁、数字 9 については 1+2+3+4 = 10 桁となるため、合計は 80 + 10 = 90 桁となります。この計算は O(1) で完了するため、非常に効率的です。

C++実装例

以下の実装例を見ると、理解がより深まるでしょう。

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

void solve(int k) {
    string s = to_string(k);
    int v[] = {0, 1, 3, 6, 10};
    cout << ((s[0] - '0') - 1) * 10 + v[s.length()] << endl;
}

int main() {
    int k = 9999;
    solve(k);
    return 0;
}

入力

9999

出力

90

まとめ

この問題は、特殊数の規則性(各数字につき4種類、合計10桁)に着目することで、ループ処理を使わずに定数時間で解くことができます。累積和の配列を活用したシンプルな公式がポイントです。