A - Function Height

入力が大きい整数のときはdoubleの精度が足りなくなるので、整数のまま処理をしましょうという問題

B - Diagonal Walking v.2

まずゴールまで最短で行ってから、(1,1), (-1,-1)のムーブを繰り返すという戦略が最適なのであとはやるだけ

C - Classy Numbers

0からnまでのclassy numbersの数をcnt(n)とおくとcnt(R) - cnt(L - 1)で求まる。桁dpを書くだけなんですが、本番中にすごく手間取ってしまった。

ポイントは、非ゼロの桁の数は0,1,2,3の4通りだということ。自分は1,2,3の3通りだと考えたせいで初期化が複雑になりすぎて撃沈しました。

i64 cnt(i64 n) {
    string b = to_string(n);
    vvvi dp(b.size() + 1, vvi(2, vi(4)));
    // dp[i][j][k]: 上からi桁見たときに、n未満確定で、0でない桁の数がk個のような数の個数
    dp[0][0][0] = 1;
    for (int i = 0; i < b.size(); i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 4; k++) {
                if (k < 3) {
                    for (int d = 1; d < (j ? 10 : b[i] - '0' + 1); d++) {
                        dp[i + 1][j || d < b[i] - '0'][k + 1] += dp[i][j][k];
                    }
                }
                dp[i + 1][j || 0 < b[i] - '0'][k] += dp[i][j][k];
            }
        }
    }
    i64 ret = 0;
    for (int i = 0; i < 4; i++) {
        ret += dp[b.size()][0][i] + dp[b.size()][1][i];
    }
    return ret;
}