隣接する異なる数字を持つ数の個数を数えよ

隣り合う10進数の各桁が等しくない範囲内の値の個数を数えます。

このチャレンジで学べること

leftからrightまで（両端を含む）の整数のうち、隣り合う桁が等しくないものの個数を数えてください。通常の10進表記（先頭にゼロは付けない）を用います。0および他の1桁の数はすべて条件を満たします。

counting_numbers(left, right) を実装してください。

left: 許可される最初の値。

right: 許可される最後の値。

条件を満たす値の個数を返してください。

0 ≤ left ≤ right ≤ 10¹⁸。範囲が非常に大きいため、すべての整数を個別に調べることはできません。

例 1

入力：
left = 10
right = 15

期待される出力：
expected = 5

入力：
long long left = 10;
long long right = 15;

期待される出力：
long long expected = 5;

入力：
long left = 10;
long right = 15;

期待される出力：
long expected = 5;

11 だけが隣接する等しい桁を持ちます。他の5つの数は条件を満たします。

例 2

入力：
left = 0
right = 9

期待される出力：
expected = 10

入力：
long long left = 0;
long long right = 9;

期待される出力：
long long expected = 10;

入力：
long left = 0;
long right = 9;

期待される出力：
long expected = 10;

10個すべての値は1桁なので、隣接する等しい桁がありません。

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

区間の両端それぞれまでの有効な数を数え、その差を取ります。

ヒント 2

有効性が隣り合う桁と、数を開始したかどうかに依存するので、Digit DP が使えます。

ヒント 3

先頭の0は、桁数の短い数を正しく数えるために特別扱いが必要です。

目安の計算量

時間 O(k * 10 * states)、追加メモリ O(k * states)

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。