yukicoder No.220 - 世界のなんとか2

問題

http://yukicoder.me/problems/no/220

解法

:=(番目の桁まで見ていて, との大小関係がで, 3で割った時の余りがで, を持っているかがという状態を満たす整数の個数)とします. あとは普通の桁DPです.

ソースコード

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

const int kMAX_P = 30;

int P;
ll dp[kMAX_P][2][3][2];    // (桁, 10^Pより小さいか, mod3, 3を含んでいるか)

void Solve() {
    vector<int> number;
    for (int i = 0; i < P + 1; i++) {
        if (i == 0) number.push_back(1);
        else number.push_back(0);
    }
    dp[0][0][0][0] = 1;
    for (int i = 0; i < P + 1; i++) {
        for (int less = 0; less <= 1; less++) {
            for (int mod3 = 0; mod3 < 3; mod3++) {
                for (int has3 = 0; has3 <= 1; has3++) {
                    if (dp[i][less][mod3][has3] == 0) continue;
                    for (int d = 0; d < 10; d++) {
                        if (!less && d > number[i]) break;
                        dp[i + 1][less | (d < number[i])][(mod3 * 10 + d) % 3][has3 | (d == 3)] += dp[i][less][mod3][has3];
                    }
                }
            }
        }
    }

    ll answer = 0;
    for (int less = 0; less <= 1; less++) {
        for (int mod3 = 0; mod3 < 3; mod3++) {
            for (int has3 = 0; has3 <= 1; has3++) {
                if (mod3 != 0 && !has3) continue;
                answer += dp[P + 1][less][mod3][has3];
            }
        }
    }
    answer -= 1;    // 0 を引く
    cout << answer << endl;
}

int main() {
    cin >> P;

    Solve();

    return 0;
}

感想

先にこっちを解いていたので簡単でした.