完全な3の倍数 [yukicoder 1185]

https://yukicoder.me/problems/no/1185

解説

https://yukicoder.me/submissions/537221

特徴的な条件として、任意の桁の組において、数の和が3の倍数である必要がある。
よって、求めたい数字は0369を使って作れる数のことになる。
…と思いきやサンプルをみると、12もOK。確かに。コーナーケースが入ってて助かった。
以下条件である。

• 2桁以上、かつ、0369を使って作れる数
• 2桁の場合は12,15のように桁和が3の倍数であるものもOK

only0369関数：2桁以上、かつ、0369を使って作れる数

これは先頭から順に数を決定していく。
桁DPで使うようなテクを用いるので、どちらかというと桁DPを学んだ方がこの辺はスムーズかも。
先頭から数を割り当てていくが、もうすでに小さい数になることが確定していれば、
それより下の項は適当に決めて問題ない。
これは4^{残りの桁数}通りあるので、これを足しこんでいく。
数を頭から全体に見ていって、全部0369なら自分の分も足しこむ。
求める数は2桁である必要があるので、0,3,6,9の4通りを引いておく。

special関数：2桁の場合は12,15のように桁和が3の倍数であるものもOK

こっちは全然組み合わせが無いので、2桁の数を全部探して条件を満たすものを答えればいい。
注意点として、only0369関数の方で数えた、どっちの桁も3の倍数のものは重複するので数えないようにする。

int N; string S;
//---------------------------------------------------------------------------------------------------
int cmb[10];
int only0369() {
    int len = S.length();

    cmb[0] = 1;
    rep(i, 1, 10) cmb[i] = cmb[i - 1] * 4;

    int ans = 0;
    bool ok = true;
    rep(i, 0, len) {
        int num = S[i] - '0';
        rep(c, 0, num) if (c % 3 == 0) ans += cmb[len - i - 1];
        if (num % 3 != 0) {
            ok = false;
            break;
        }
    }
    if (ok) ans++;
    return ans - 4;
}
//---------------------------------------------------------------------------------------------------
int special() {
    int ans = 0;

    rep(x, 10, 100) if (x <= N) {
        int tot = (x % 10) + (x / 10);
        if ((x % 10) % 3 == 0 && (x / 10) % 3 == 0) continue;
        if (x % 3 == 0 && tot % 3 == 0) ans++;
    }

    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    S = to_string(N);
    cout << only0369() + special() << endl;
}