結果
問題 | 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; }