結果

問題 No.319 happy b1rthday 2 me
コンテスト
ユーザー yuppe19 😺
提出日時 2015-12-12 14:13:00
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,521 bytes
コンパイル時間 652 ms
コンパイル使用メモリ 52,368 KB
最終ジャッジ日時 2024-11-14 19:30:39
合計ジャッジ時間 1,305 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function ‘i64 g(i64)’:
main.cpp:19:16: error: ‘pow’ was not declared in this scope
   19 |     res += i64(pow(10LL, i));
      |                ^~~
main.cpp: In function ‘i64 f(i64)’:
main.cpp:58:3: error: ‘vector’ was not declared in this scope
   58 |   vector<vector<vector<vector<i64>>>> dp(n+1, vector<vector<vector<i64>>>(2, vector<vector<i64>>(2, vector<i64>(11))));
      |   ^~~~~~
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:58:34: error: expected primary-expression before ‘>>’ token
   58 |   vector<vector<vector<vector<i64>>>> dp(n+1, vector<vector<vector<i64>>>(2, vector<vector<i64>>(2, vector<i64>(11))));
      |                                  ^~
main.cpp:58:36: error: expected primary-expression before ‘>>’ token
   58 |   vector<vector<vector<vector<i64>>>> dp(n+1, vector<vector<vector<i64>>>(2, vector<vector<i64>>(2, vector<i64>(11))));
      |                                    ^~
main.cpp:58:71: error: expected primary-expression before ‘>>’ token
   58 |   vector<vector<vector<vector<i64>>>> dp(n+1, vector<vector<vector<i64>>>(2, vector<vector<i64>>(2, vector<i64>(11))));
      |                                                                       ^~
main.cpp:58:73: error: expected primary-expression before ‘>’ token
   58 |   vector<vector<vector<vector<i64>>>> dp(n+1, vector<vector<vector<i64>>>(2, vector<vector<i64>>(2, vector<i64>(11))));
      |                                                                         ^
main.cpp:58:95: error: expected primary-expression before ‘>>’ token
   58 |   vector<vector<vector<vector<i64>>>> dp(n+1, vector<vector<vector<i64>>>(2, vector<vector<i64>>(2, vector<i64>(11))));
      |                                                                                               ^~
main.cpp:58:111:

ソースコード

diff # 

#include <iostream>
#include <algorithm>
using namespace std;
using i64 = long long;

class range {private: struct I{int x;int operator*(){return x;}bool operator!=(I& lhs){return x<lhs.x;}void operator++(){++x;}};I i,n;
public:range(int n):i({0}),n({n}){}range(int i,int n):i({i}),n({n}){}I& begin(){return i;}I& end(){return n;}};

// (ΦωΦ)＜
// 前の数字が1で終わってて、今が2で始まってる数字のときも
// 並べて書くと "...1", "2..." になり、'12'が現れる。
i64 g(i64 x) {
  if(x <= 1) { return 0; }
  if(x < 10) { return 1; }
  string s = to_string(x);
  int n = s.size();
  i64 res = 1;
  for(int i : range(n-1-(s[0]<='2'))) {
    res += i64(pow(10LL, i));
  }
  if(s[0] == '2') {
    res += (stoll(s.substr(1)) + 10) / 10;
    if(s[n-1] - '0' < 2) {
      res--;
    }
  }
  return res;
//  string s = to_string(x);
//  int n = s.size();
//  // dp[i桁見てる][未満フラグ][先頭が2?][最後が2じゃない?]
//  vector<vector<vector<vector<i64>>>> dp(n+1, vector<vector<vector<i64>>>(2, vector<vector<i64>>(2, vector<i64>(2))));
//  dp[0][0][0][0] = 1;
//  for(int i : range(n)) {
//    for(int j : range(2)) {
//      for(int k1 : range(2)) {
//        for(int k2 : range(2)) {
//          for(int d : range(j?10:s[i]-'0'+1)) {
//            int flag = j || d < s[i] - '0';
//            dp[i+1][flag][k1||(i==0&&d==2)][k2||(i==n-1&&d==2)] += dp[i][j][k1][k2];
//          }
//        }
//      }
//    }
//  }
//  debug(dp[n][0]);
//  debug(dp[n][1]);
//  i64 res = 0;
//  for(int j : range(2)) {
//    res += dp[n][j][1][1];
//  }
//  return res;
}

i64 f(i64 x) {
  string s = to_string(x);
  int n = s.size();
  // dp[i桁見てる][未満フラグ][前の桁が1だった?]['12'の個数]
  vector<vector<vector<vector<i64>>>> dp(n+1, vector<vector<vector<i64>>>(2, vector<vector<i64>>(2, vector<i64>(11))));
  dp[0][0][0][0] = 1;
  for(int i : range(n)) {
    for(int j : range(2)) {
      for(int k : range(2)) {
        for(int x : range(10)) {
          for(int d : range(j?10:s[i]-'0'+1)) {
            int flag = j || d < s[i] - '0';
            dp[i+1][flag][d==1][x+(k&&d==2)] += dp[i][j][k][x];
          }
        }
      }
    }
  }
  i64 res = 0;
  for(int j : range(2)) {
    for(int k : range(2)) {
      for(int x : range(11)) {
        res += dp[n][j][k][x] * x;
      }
    }
  }
  return res;
}

int main(void) {
  i64 a, b; scanf("%lld%lld", &a, &b);
  i64 res = f(b) - f(a-1);
  res += g(b) - g(a);
  printf("%lld\n", res);
  return 0;
}
0