#749240 (D) No.741 AscNumber(Easy)

提出ソース

結果

問題	No.741 AscNumber(Easy)
ユーザー	nobuta05
提出日時	2022-03-27 15:19:08
言語	D (dmd 2.106.1)
結果	AC
実行時間	945 ms / 2,000 ms
コード長	1,707 bytes
コンパイル時間	682 ms
コンパイル使用メモリ	101,840 KB
実行使用メモリ	264,460 KB
最終ジャッジ日時	2024-06-22 14:43:12
合計ジャッジ時間	14,332 ms
ジャッジサーバーID （参考情報）	judge4 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,820 KB
testcase_01	AC	1 ms 6,940 KB
testcase_02	AC	1 ms 6,940 KB
testcase_03	AC	1 ms 6,940 KB
testcase_04	AC	1 ms 6,944 KB
testcase_05	AC	1 ms 6,940 KB
testcase_06	AC	1 ms 6,940 KB
testcase_07	AC	1 ms 6,940 KB
testcase_08	AC	1 ms 6,940 KB
testcase_09	AC	1 ms 6,940 KB
testcase_10	AC	1 ms 6,944 KB
testcase_11	AC	1 ms 6,944 KB
testcase_12	AC	1 ms 6,940 KB
testcase_13	AC	1 ms 6,944 KB
testcase_14	AC	1 ms 6,944 KB
testcase_15	AC	1 ms 6,944 KB
testcase_16	AC	1 ms 6,944 KB
testcase_17	AC	1 ms 6,940 KB
testcase_18	AC	1 ms 6,940 KB
testcase_19	AC	1 ms 6,940 KB
testcase_20	AC	1 ms 6,940 KB
testcase_21	AC	1 ms 6,940 KB
testcase_22	AC	2 ms 6,944 KB
testcase_23	AC	1 ms 6,940 KB
testcase_24	AC	1 ms 6,940 KB
testcase_25	AC	1 ms 6,948 KB
testcase_26	AC	1 ms 6,948 KB
testcase_27	AC	1 ms 6,944 KB
testcase_28	AC	1 ms 6,940 KB
testcase_29	AC	1 ms 6,944 KB
testcase_30	AC	1 ms 6,944 KB
testcase_31	AC	1 ms 6,940 KB
testcase_32	AC	1 ms 6,940 KB
testcase_33	AC	1 ms 6,944 KB
testcase_34	AC	2 ms 6,944 KB
testcase_35	AC	945 ms 251,344 KB
testcase_36	AC	389 ms 114,192 KB
testcase_37	AC	488 ms 130,648 KB
testcase_38	AC	452 ms 128,424 KB
testcase_39	AC	382 ms 109,852 KB
testcase_40	AC	544 ms 148,004 KB
testcase_41	AC	826 ms 229,764 KB
testcase_42	AC	429 ms 124,424 KB
testcase_43	AC	316 ms 92,432 KB
testcase_44	AC	661 ms 182,064 KB
testcase_45	AC	694 ms 195,612 KB
testcase_46	AC	856 ms 239,988 KB
testcase_47	AC	140 ms 42,728 KB
testcase_48	AC	859 ms 241,056 KB
testcase_49	AC	723 ms 201,204 KB
testcase_50	AC	99 ms 31,068 KB
testcase_51	AC	334 ms 93,968 KB
testcase_52	AC	943 ms 264,460 KB
testcase_53	AC	944 ms 263,584 KB
testcase_54	AC	939 ms 261,380 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import std.stdio, std.string, std.conv;
import std.algorithm, std.math;
import std.range;
import std.container.rbtree, std.container.dlist;
import std.container.binaryheap, std.container.array;
import std.typecons;

alias mstring = char[];
const long INF = 1L << 60L;
const long mod = 1_000_000_000 + 7;

void chmin(T)(ref T x, T y) {
  x = min(x, y);
}

void chmax(T)(ref T x, T y) {
  x = max(x, y);
}

// 単一の数値を取得
// readln.chomp.to!int;
//  or
// int a;
// readf("%s\n", a);

// 複数の数値を取得(可変数個の場合推奨)
// readln.chomp.split.map!(to!long).array

// 複数の数値を取得(固定数個の場合、推奨)
// int a, b;
// readf("%s %s\n", &a, &b);

// インデントを一個ずらして複数の数値を取得(累積和とかで1-indexedの方が良い時がある)
// long[] vs = readln.chomp.split.map!(to!long).array;
// vs = [0L] ~ vs;

// 小数点は以下で指定
// double ret = 10.0;
// writefln("%.12f", ret);

// 配列の最後の要素は arr[$-1] でアクセスできる

void main() {

  int N = readln.chomp.to!int;
  const int maxK = N + 1;

  auto dp = new long[][][](maxK + 1, 2, 10);
  dp[maxK][0][0] = 1L;

  for (int i = maxK; i > 0; i--) {
    long ni = (i == maxK) ? 1L : 0L;
    for (int k = 0; k < 2; k++)
      for (int j = 0; j < 10; j++)
        for (int d = 0; d < 10; d++) {
          if (k == 0 && d > ni)
            continue;
          if (d < j)
            continue;

          dp[i - 1][k == 1 || d < ni][d] += dp[i][k][j];
          dp[i - 1][k == 1 || d < ni][d] %= mod;
        }
  }

  long ret = 0L;
  for (int j = 0; j < 10; j++) {
    ret += dp[0][0][j] + dp[0][1][j];
    ret %= mod;
  }

  writeln(ret);
}

yukicoder

結果

テストケース

ソースコード