AtCoder Beginner Contest 007

Submission #1770605

Source codeソースコード

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <vector>

#define stirng string
#define vvi vector<vector<int>>
#define vi vector<int>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;

const int INF = 1e9 + 7;

int main() {
  long long int p;
  string b;
  cin >> p >> b;
  p--;
  stirng a = to_string(p);
  int n, m;
  n = b.size();
  m = a.size();
  int dp[n + 1][2][2] = {0};
  int DP[m + 1][2][2] = {0};
  dp[0][0][0] = 1;
  DP[0][0][0] = 1;

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 2; j++) {
      for (int k = 0; k < 2; k++) {
        int lim = j ? 9 : b[i] - '0';
        rep(d, lim + 1) {
          if (j == 1 || d < lim) {
            if (k == 1 || d == 4 || d == 9) {
              dp[i + 1][1][1] += dp[i][j][k];
            } else {
              dp[i + 1][1][0] += dp[i][j][k];
            }
          } else {
            if (k == 1 || d == 4 || d == 9) {
              dp[i + 1][0][1] += dp[i][j][k];
            } else {
              dp[i + 1][0][0] += dp[i][j][k];
            }
          }
        }
      }
    }
  }

  for (int i = 0; i < m; i++) {
    for (int j = 0; j < 2; j++) {
      for (int k = 0; k < 2; k++) {
        int lim = j ? 9 : a[i] - '0';
        rep(d, lim + 1) {
          if (j == 1 || d < lim) {
            if (k == 1 || d == 4 || d == 9) {
              DP[i + 1][1][1] += DP[i][j][k];
            } else {
              DP[i + 1][1][0] += DP[i][j][k];
            }
          } else {
            if (k == 1 || d == 4 || d == 9) {
              DP[i + 1][0][1] += DP[i][j][k];
            } else {
              DP[i + 1][0][0] += DP[i][j][k];
            }
          }
        }
      }
    }
  }

  cout << dp[n][0][1] + dp[n][1][1] - (DP[m][0][1] + DP[m][1][1]) << endl;

  return 0;
}

Submission

Task問題 D - 禁止された数字
User nameユーザ名 kuma13
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 WA
Score得点 30
Source lengthソースコード長 1997 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Sample - subtask0_sample01.txt,subtask0_sample02.txt,subtask0_sample03.txt,subtask0_sample04.txt
Subtask1 30 / 30 subtask1_01.txt,subtask1_02.txt,subtask1_03.txt,subtask1_04.txt,subtask1_05.txt,subtask1_06.txt,subtask1_07.txt,subtask1_08.txt,subtask1_09.txt,subtask1_10.txt,subtask1_11.txt,subtask1_12.txt,subtask1_13.txt,subtask0_sample01.txt,subtask0_sample02.txt,subtask0_sample03.txt
Subtask2 0 / 70 subtask0_sample01.txt,subtask0_sample02.txt,subtask0_sample03.txt,subtask0_sample04.txt,subtask1_01.txt,subtask1_02.txt,subtask1_03.txt,subtask1_04.txt,subtask1_05.txt,subtask1_06.txt,subtask1_07.txt,subtask1_08.txt,subtask1_09.txt,subtask1_10.txt,subtask1_11.txt,subtask1_12.txt,subtask1_13.txt,subtask2_01.txt,subtask2_02.txt,subtask2_03.txt,subtask2_04.txt,subtask2_05.txt,subtask2_06.txt,subtask2_07.txt,subtask2_08.txt,subtask2_09.txt,subtask2_10.txt,subtask2_11.txt,subtask2_12.txt,subtask2_13.txt,subtask2_14.txt,subtask2_15.txt,subtask2_16.txt,subtask2_17.txt,subtask2_18.txt,subtask2_19.txt,subtask2_20.txt,subtask2_21.txt,subtask2_22.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask0_sample01.txt AC 1 ms 256 KB
subtask0_sample02.txt AC 1 ms 256 KB
subtask0_sample03.txt AC 1 ms 256 KB
subtask0_sample04.txt WA
subtask1_01.txt AC 1 ms 256 KB
subtask1_02.txt AC 1 ms 256 KB
subtask1_03.txt AC 1 ms 256 KB
subtask1_04.txt AC 1 ms 256 KB
subtask1_05.txt AC 1 ms 256 KB
subtask1_06.txt AC 1 ms 256 KB
subtask1_07.txt AC 1 ms 256 KB
subtask1_08.txt AC 1 ms 256 KB
subtask1_09.txt AC 1 ms 256 KB
subtask1_10.txt AC 1 ms 256 KB
subtask1_11.txt AC 1 ms 256 KB
subtask1_12.txt AC 1 ms 256 KB
subtask1_13.txt AC 1 ms 256 KB
subtask2_01.txt WA
subtask2_02.txt WA
subtask2_03.txt WA
subtask2_04.txt WA
subtask2_05.txt WA
subtask2_06.txt WA
subtask2_07.txt WA
subtask2_08.txt WA
subtask2_09.txt WA
subtask2_10.txt WA
subtask2_11.txt WA
subtask2_12.txt WA
subtask2_13.txt WA
subtask2_14.txt WA
subtask2_15.txt WA
subtask2_16.txt WA
subtask2_17.txt WA
subtask2_18.txt WA
subtask2_19.txt WA
subtask2_20.txt WA
subtask2_21.txt WA
subtask2_22.txt WA