ヒント 1

各桁について、総和への寄与を考えてみましょう。
たとえば、\(f(456) = 4 + 5 + 6\) です。ほかにも \(345, 152\) などで \(10\) の位が \(5\) になります。

各桁が \(1, 2, \dots, 9\) になる回数が何回であるかを高速に計算することができれば、答えを求めることができそうです。

ヒント 2

\(N=288\) の \(10\) の位で考えてみましょう。

ステップ 1

\(10\) の位が \(3\) になるのは、どのようなときでしょうか。

\(100\) の位が \(2\) 以下で、\(10\) の位が \(3\) である整数は、最大で \(239\) です。よって、このような整数はすべて \(N\) 以下になります。

\(100\) の位が \(k\) で、\(10\) の位が \(3\) である整数は \(100k + 30\) から \(100k+39\) の \(10\) 個存在します。

今回の場合、\(k=0, 1, 2\) の \(3\) 通り存在するため、これを満たす整数は \(3 \times 10 = 30\) 個存在します。 \(10\) の位が \(1\) 以上 \(7\) 以下のときも、同様の議論によって求められます。

ステップ 2

次に、\(10\) の位が \(8\) になるのは、どのようなときでしょうか。

\(100\) の位が \(1\) 以下の場合は、ステップ 1 の議論と同様に計算できます。（実際に確かめてみましょう）

しかし、\(100\) の位が \(2\) で \(10\) の位が \(8\) である整数の最大値は \(289\) で、これは \(N\) より大きい値です。 \(100\) の位が \(2\) のとき、\(10\) の位が \(8\) である \(N\) 以下の整数は、\(280\) 以上 \(288\) 以下の \(9\) 個です。

上記の考察によって、\(10\) の位が \(8\) で \(N\) 以下の整数は \(2 \times 10 + 9\) 個あることがわかりました。

ステップ 3

\(10\) の位が \(9\) になる場合を考えます。

\(100\) の位が \(2\) で \(10\) の位が \(9\) になる整数は、すべて \(N\) より大きい値です。

一方、\(100\) の位が \(0\) または \(1\) で \(10\) の位が \(9\) になる整数は、最大でも \(199\) なので、すべて \(N\) より小さい値です。

\(10\) の位が \(9\) になる \(N\) 以下の整数は \(2 \times 10\) 個あることがわかりました。

まとめ

各桁について、ステップ 1, 2, 3 で計算することで、求める値が計算できそうです。

ヒント 3

\(d_p(i)\) を \(i\) の \(10^p\) の位の数、\([a, b]\) は \(a\) 以上 \(b\) 以下の整数の集合とします。

ヒント 2 の考察を、\(10\) の位に着目して一般化します。 \(k=1, 2, \dots, 9\) について、\(x = [1, N]\) のうち、\(d_1(x)=k\)（\(x\) の \(10\) の位が \(k\)）となる回数は、以下の計算によって求められます。

• \(k < d_1(N)\) のとき：\(10 \times (N/100 + 1)\) 回（\(a/b\) は \(\frac{a}{b}\) を切り捨てた整数値）
• \(k = d_1(N)\) のとき：\(10 \times (N/100) + (N \bmod 10) + 1\) 回（\(a \bmod b\) は \(a\) を \(b\) で割ったあまり）
• \(k > d_1(N)\) のとき：\(10 \times (N/100)\) 回

具体例で見てみましょう。入出力例 2 の場合 \(10\) の位が \(k\) になる回数は以下のように計算できます。

• \(k = 1\) のとき：\(10 \times (N/100 + 1) = 10 \times (2 + 1) = 30\)
  • 実際に、\([10, 19], [110, 129], [210, 219]\) の \(30\) 回出現します。
• \(k = 2, 3, \dots, 7\) のとき：\(10 \times (N/100 + 1)\)
  • \(k = 1\) の場合と同様に、\([10k, 10k+9], [10k+100, 10k+109], [10k+200, 10k+209]\) の \(30\) 回出現します。
• \(k = 8\) のとき：\(10 \times (N/100) + (N \bmod 10) + 1 = 10 \times 2 + (8 + 1) = 29\)
  • \([80, 89], [180, 189], [280, 288]\) の \(29\) 回出現します。
• \(k = 9\) のとき：\(10 \times (N/100) = 10 \times 2 = 20\)
  • \([90, 99], [190, 199]\) の \(20\) 回出現します。

これにより、\(x = 1, 2, \dots, N\) について、\(10\) の位による \(f(x)\) の総和への寄与は、\(30 \times (1+2+\dots+7) + 29 \times 8 + 20 \times 9 = 1252\) と計算できます。

すべての位に対して同様の考察を行い、各桁による寄与を足し合わせることで、答えを求めることができます。

ヒント 4

ヒント 2 で書いた条件を、さらに一般化します。 \(k=1, 2, \dots, 9\) について、\(x = [1, N]\) のうち、\(d_p(x)=k\) となる回数は以下のように表せます。

• \(k < d_p(N)\) のとき：\(10^p \times (N/10^{p+1} + 1)\) 回
• \(k = d_p(N)\) のとき：\(10^p \times (N/10^{p+1}) + (N \bmod 10^p) + 1\) 回
• \(k > d_p(N)\) のとき：\(10^p \times (N/10^{p+1})\) 回