結果

問題 No.319 happy b1rthday 2 me
コンテスト
ユーザー yuppe19 😺
提出日時 2016-03-24 19:47:27
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,560 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 556 ms
コンパイル使用メモリ 53,684 KB
最終ジャッジ日時 2024-11-14 19:36:01
合計ジャッジ時間 1,172 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、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

ソースコード

diff #
raw source code 

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