結果

問題 No.220 世界のなんとか2
コンテスト
ユーザー ふーらくたる
提出日時 2016-07-03 15:21:08
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 1,370 bytes
コンパイル時間 637 ms
コンパイル使用メモリ 60,992 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-12 19:44:48
合計ジャッジ時間 1,481 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0