問題概要
正整数 $l, r$ が与えられる．$l$ 以上 $r$ 以下の整数であって，以下の条件を満たすものの個数を求めよ：
- $10$ 以上の整数であって，$10$ 進数表記したときに最上位の桁が他のどの桁よりも（strict に）大きい．
制約
- $10 \leq l \leq r \leq 10^{ 18 }$
解法
「$l$ 以上 $r$ 以下の整数で，ある条件を満たすものの個数を求めよ」という形式の問題はしばしば出題されます．よく使う言い換えとして，「$n$ 以下の整数であって同様の条件を満たすものの個数」を求める関数を $f( n )$ として，答えを直接求める代わりに $f( r ) - f( l - 1 )$ を計算するというものがあります．題意で言われたものを直接求めるより $f$ を設計する方が考えやすい場合がしばしばあり，今回も該当するように思えます．
では $f$ の中身について考えていきます．何かうまいことやれそうな気配はしますが，「$n$ 以下の非負整数で，ある条件を満たすものの個数を求めよ」といった問題にしばしば使える動的計画法の類型として，Digit DP と呼ばれるものがあるので，今回はこちらでやります．詳細は上記リンク先の記事をお読みいただくとして，今回の問題では以下のように状態をとります：
\begin{align*}
\mathit{ dp }[i][j][k][l] := \begin{aligned}
&\text{先頭から $i$ 桁決めて，} \\
&\text{leading zero を抜けて最初の桁の数字が $j$ であり，} \\
&\text{leading zero を除いた桁数と $2$ の内で大きくない方が $k$ で，} \\
&\text{$n$ 未満かを表す真偽値が $l$}
\end{aligned}
\end{align*}
先頭桁と他の桁との大小関係を管理するために $j$ を使います，leading zero を抜けていない場合は $j = 0$ にすることに決めておきます．また，$10$ 以上であることを $2$ 桁以上であることと言い換えて $k$ を使って管理します．
$\mathit{ dp }[i][j][k][l]$ からの遷移について考えます．$n$ の上から $i + 1$ 桁目を $d_i$ として，次の桁に入れる数字 $d$ は，
- $l = \mathrm{ True }$ なら $9$ 以下，そうでないなら $d_i$ 以下
- $j \neq 0$ なら $j$ 未満
という条件をともに満たす必要があります．そのような $d$ を遷移先としてすべて試すとすると，それぞれについて遷移先を指す添字 $i', j', k', l'$ はそれぞれ
- $i'$ は $i$ から $1$ 桁増えるので $i + 1$
- $j'$ は $j \neq 0$ なら $j$, そうでないなら $d$
- $k'$ は $\min( 2, k + ( \text{$j' \neq 0$ なら $1$, そうでないなら $0$} ) )$
- $l'$ は $l \lor ( d < d_i )$
となります．
DP を回し終わった後，
\begin{equation*}
\sum_{ j = 0 }^9 \sum_{ l = 0 }^1 \mathit{ dp }[ \text{$n$ の桁数}][j][2][l]
\end{equation*}
が答えです．
あとは，$f$ を外側から適当に呼び出して差を取れば問題に答えられます．
計算量については，$i$ の範囲が $\Theta( \log n )$ なので，$10$ 進数由来の $10$ を定数とすれば $\Theta( \log n )$ 時間・空間となります．
コード
LL solve( const LL N ) { const string S = toString( N ); const int L = SZ( S ); static LL dp[ 32 ][ 16 ][ 4 ][ 2 ]; // dp[ # of digits ][ first digits whic is not 0 ][ min 2 $ # of digits after leading zero ][ less than N? ] := # of ways fill( AALL( dp ), 0 ); dp[0][0][0][0] = 1; REP( i, L ) { const int D = S[i] - '0'; REP( j, 10 ) { REP( k, 3 ) { REP( l, 2 ) { REP( d, ( l ? 9 : D ) + 1 ) { if ( j && j <= d ) { continue; } const int nj = j ? j : d; const int nk = min( 2, k + !!nj ); const int nl = l || d < D; dp[ i + 1 ][ nj ][ nk ][ nl ] += dp[i][j][k][l]; } } } } } LL res = 0; REP( j, 10 ) { REP( l, 2 ) { res += dp[L][j][2][l]; } } return res; } int main() { IN( LL, L, R ); cout << solve( R ) - solve( L - 1 ) << endl; return 0; }
