結果

問題 No.319 happy b1rthday 2 me
コンテスト
ユーザー yuppe19 😺
提出日時 2018-11-18 21:45:38
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,705 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,129 ms
コンパイル使用メモリ 84,008 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-24 15:09:06
合計ジャッジ時間 2,313 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
using namespace std;
using i64 = int64_t;

int cmp(int x, int y) {
  if(x <  y) { return 0; }
  if(x == y) { return 1; }
  return 2;
}

// [1, x] の範囲において、数字を繋げて書くというのを無視した上で '12' が現れる個数
i64 g1(i64 x) {
  string s = to_string(x);
  int n = static_cast<int>(s.size());
  // dp[未満/丁度/超過][ひとつ右の数字が2だったか]['12'の個数] := パターン数
  vector<vector<vector<i64>>> dp(3, vector<vector<i64>>(2, vector<i64>(n, 0)));
  dp[1][0][0] = 1;
  for(int i=n-1; i>=0; --i) {
    vector<vector<vector<i64>>> ndp(3, vector<vector<i64>>(2, vector<i64>(n, 0)));
    for(int flag=0; flag<3; ++flag) {
      for(int was2=0; was2<2; ++was2) {
        for(int cnt12=0; cnt12<n; ++cnt12) {
          if(!dp[flag][was2][cnt12]) { continue; }
          for(int d=0; d<10; ++d) {
            int nflag = cmp(d, s[i]-'0');
            if(nflag == 1) { nflag = flag; }
            int nwas2 = d==2;
            int ncnt12 = cnt12 + (was2 && d==1);
            ndp[nflag][nwas2][ncnt12] += dp[flag][was2][cnt12];
          }
        }
      }
    }
    dp = ndp;
  }
  i64 res = 0;
  for(int flag=0; flag<2; ++flag) {
    for(int was2=0; was2<2; ++was2) {
      for(int cnt12=1; cnt12<n; ++cnt12) {
        res += dp[flag][was2][cnt12] * cnt12;
      }
    }
  }
  return res;
}

// [1, x] の範囲において、2 で始まって 2 で終わる整数の個数
i64 g2(i64 x) {
  string s = to_string(x);
  int n = static_cast<int>(s.size());
  // dp[未満/丁度/超過][末尾の数字][先頭の数字] := パターン数
  vector<vector<vector<i64>>> dp(3, vector<vector<i64>>(11, vector<i64>(10, 0)));
  dp[1][10][0] = 1;
  for(int i=n-1; i>=0; --i) {
    vector<vector<vector<i64>>> ndp(3, vector<vector<i64>>(11, vector<i64>(10, 0)));
    for(int flag=0; flag<3; ++flag) {
      for(int trail=0; trail<11; ++trail) {
        for(int lead=0; lead<10; ++lead) {
          if(!dp[flag][trail][lead]) { continue; }
          for(int d=0; d<10; ++d) {
            int nflag = cmp(d, s[i]-'0');
            if(nflag == 1) { nflag = flag; }
            int ntrail = trail == 10 ? d : trail;
            int nlead  = d == 0 ? lead : d;
            ndp[nflag][ntrail][nlead] += dp[flag][trail][lead];
          }
        }
      }
    }
    dp = ndp;
  }
  i64 res = 0;
  for(int flag=0; flag<2; ++flag) {
    res += dp[flag][2][2];
  }
  return res;
}

i64 f(i64 x) {
  return g1(x) + g2(x);
}

int main(void) {
  i64 a, b; scanf("%ld%ld", &a, &b);
  i64 res = f(b) - f(a-1);
  string sa = to_string(a);
  if(sa[0] == '2' && sa.back() == '2') { --res; }
  printf("%ld\n", res);
  return 0;
}
0