Classy Numbers [Educational Codeforces Round 50 (Rated for Div. 2) C]

http://codeforces.com/contest/1036/problem/C

L≦x≦Rのなかでclassyな数の個数を答えよ。
※ classy：10進数表記した時に0でない数が3個以下である数

前提知識

• 桁DP

解法

http://codeforces.com/contest/1036/submission/42623549

[L,R]が扱いづらいので、[0,R] - [0,L-1]を答えとするいつものテクを使おう。
今後は「f(x) := [0,x]でclassyな数」を構築していく。
　
桁DPを使おう。
dp[dgt][nz][isless] := dgt桁目まで確定していて、0でない桁がnz個あって、xとの今の所の大小関係がislessの組み合わせ数
※ isless=0:今の所同じ、isless=1:既に下回っている
一般的な桁DP。遷移も一般的。
nzは[0,3]を見るようにする。4も遷移してしまうので、場所だけは取っておこう。
あと、クエリ形式なので、初期化も忘れずに。

ll L, R;
//---------------------------------------------------------------------------------------------------
string S;
int N;
ll dp[20][6][2];
ll f(ll x) {
    S = to_string(x);
    N = S.length();

    rep(dgt, 0, N + 1) rep(nz, 0, 5) rep(isless, 0, 2) dp[dgt][nz][isless] = 0;
    dp[0][0][0] = 1;
    rep(dgt, 0, N) rep(nz, 0, 4) rep(isless, 0, 2) {
        int c = S[dgt] - '0';

        rep(x, 0, 10) {
            int dgt2 = dgt + 1;
            int nz2 = nz;
            if (x != 0) nz2++;
            
            if (isless == 1) {
                dp[dgt2][nz2][isless] += dp[dgt][nz][isless];
            } else {
                if (x < c) dp[dgt2][nz2][1] += dp[dgt][nz][isless];
                else if (x == c) dp[dgt2][nz2][0] += dp[dgt][nz][isless];
            }
        }
    }

    ll res = 0;
    rep(nz, 0, 4) rep(isless, 0, 2) res += dp[N][nz][isless];
    return res;
}
//---------------------------------------------------------------------------------------------------
void solve() {
    cin >> L >> R;

    ll ans = f(R);
    ans -= f(L - 1);

    printf("%lld\n", ans);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) solve();
}