結果
問題 | No.319 happy b1rthday 2 me |
ユーザー |
|
提出日時 | 2016-03-24 19:47:27 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,560 bytes |
コンパイル時間 | 556 ms |
コンパイル使用メモリ | 53,684 KB |
最終ジャッジ日時 | 2024-11-14 19:36:01 |
合計ジャッジ時間 | 1,172 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp: In function ‘i64 f(i64)’: main.cpp:15:3: error: ‘vector’ was not declared in this scope 15 | vector<vector<vector<vector<i64>>>> dp(n+1, vector<vector<vector<i64>>>(2, vector<vector<i64>>(2, vector<i64>(n+1, 0)))); // dp[n+1][2][2][n+1] | ^~~~~~ main.cpp:3:1: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’? 2 | #include <algorithm> +++ |+#include <vector> 3 | using namespace std; main.cpp:15:34: error: expected primary-expression before ‘>>’ token 15 | vector<vector<vector<vector<i64>>>> dp(n+1, vector<vector<vector<i64>>>(2, vector<vector<i64>>(2, vector<i64>(n+1, 0)))); // dp[n+1][2][2][n+1] | ^~ main.cpp:15:36: error: expected primary-expression before ‘>>’ token 15 | vector<vector<vector<vector<i64>>>> dp(n+1, vector<vector<vector<i64>>>(2, vector<vector<i64>>(2, vector<i64>(n+1, 0)))); // dp[n+1][2][2][n+1] | ^~ main.cpp:15:71: error: expected primary-expression before ‘>>’ token 15 | vector<vector<vector<vector<i64>>>> dp(n+1, vector<vector<vector<i64>>>(2, vector<vector<i64>>(2, vector<i64>(n+1, 0)))); // dp[n+1][2][2][n+1] | ^~ main.cpp:15:73: error: expected primary-expression before ‘>’ token 15 | vector<vector<vector<vector<i64>>>> dp(n+1, vector<vector<vector<i64>>>(2, vector<vector<i64>>(2, vector<i64>(n+1, 0)))); // dp[n+1][2][2][n+1] | ^ main.cpp:15:95: error: expected primary-expression before ‘>>’ token 15 | vector<vector<vector<vector<i64>>>> dp(n+1, vector<vector<vector<i64>>>(2, vector<vector<i64>>(2, vector<i64>(n+1, 0)))); // dp[n+1][2][2][n+1] | ^~ main.cpp:15:111: error: expec
ソースコード
#include <iostream>#include <algorithm>using namespace std;using i64 = long long;template<typename T>class Range{private:struct I{T x;T operator*(){return x;}bool operator!=(I& lhs){return x<lhs.x;}void operator++(){++x;}};I i,n;public:Range(T n):i({0}),n({n}){}Range(T i,T n):i({i}),n({n}){}I& begin(){return i;}I& end(){return n;}};using range = Range<i64>;// 数字の中の '12' という文字列を数えるi64 f(i64 x) {string s = to_string(x);int n = s.size();vector<vector<vector<vector<i64>>>> dp(n+1, vector<vector<vector<i64>>>(2, vector<vector<i64>>(2, vector<i64>(n+1, 0)))); // dp[n+1][2][2][n+1]dp[0][0][0][0] = 1;for(auto&& i : range(n)) {for(auto&& j : range(2)) {for(auto&& is1 : range(2)) {for(auto&& cnt12 : range(n)) {if(!dp[i][j][is1][cnt12]) { continue; }for(auto&& d : range(j?10:s[i]-'0'+1)) {int flag = j || d < s[i] - '0',nis1 = d==1,ncnt12 = cnt12 + (is1 && d==2);dp[i+1][flag][nis1][ncnt12] += dp[i][j][is1][cnt12];}}}}}i64 res = 0;for(auto&& j : range(2)) {for(auto&& is1 : range(2)) {for(auto&& cnt12 : range(n+1)) {res += dp[n][j][is1][cnt12] * cnt12;}}}return res;}// 2で始まって2で終わる整数を数えるi64 g(i64 x) {string s = to_string(x);int n = s.size();vector<vector<vector<vector<vector<i64>>>>> dp(n+1, vector<vector<vector<vector<i64>>>>(2, vector<vector<vector<i64>>>(2, vector<vector<i64>>(2,vector<i64>(2, 0))))); // dp[n+1][2][2][2][2]dp[0][0][0][0][0] = 1;for(auto&& i : range(n)) {for(auto&& j : range(2)) {for(auto&& nuke0 : range(2)) {for(auto&& start2 : range(2)) {for(auto&& end2 : range(2)) {if(!dp[i][j][nuke0][start2][end2]) { continue; }for(auto&& d : range(j?10:s[i]-'0'+1)) {int flag = j || d < s[i] - '0',n_nuke0 = nuke0 || d > 0,nstart2 = start2 || (!nuke0 && d==2),nend2 = d == 2;dp[i+1][flag][n_nuke0][nstart2][nend2] += dp[i][j][nuke0][start2][end2];}}}}}}i64 res = 0;for(auto&& j : range(2)) {for(auto&& nuke0 : range(2)) {res += dp[n][j][nuke0][1][1];}}return res;}int main(void) {i64 a, b; scanf("%lld%lld", &a, &b);i64 x = f(b) - f(a-1),y = g(b) - g(a);i64 res = x + y;printf("%lld\n", res);return 0;}