#712516 (Nim) No.1702 count good string

提出ソース

結果

問題	No.1702 count good string
ユーザー	yuly3
提出日時	2021-11-03 10:04:58
言語	Nim (2.0.2)
結果	AC
実行時間	11 ms / 2,000 ms
コード長	4,688 bytes
コンパイル時間	3,118 ms
コンパイル使用メモリ	73,952 KB
実行使用メモリ	6,820 KB
最終ジャッジ日時	2024-10-12 22:31:34
合計ジャッジ時間	4,545 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	1 ms 6,820 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	1 ms 6,820 KB
testcase_04	AC	1 ms 6,816 KB
testcase_05	AC	1 ms 6,816 KB
testcase_06	AC	1 ms 6,816 KB
testcase_07	AC	2 ms 6,816 KB
testcase_08	AC	1 ms 6,816 KB
testcase_09	AC	1 ms 6,820 KB
testcase_10	AC	1 ms 6,816 KB
testcase_11	AC	2 ms 6,816 KB
testcase_12	AC	1 ms 6,820 KB
testcase_13	AC	11 ms 6,820 KB
testcase_14	AC	11 ms 6,816 KB
testcase_15	AC	10 ms 6,816 KB
testcase_16	AC	11 ms 6,820 KB
testcase_17	AC	10 ms 6,816 KB
testcase_18	AC	11 ms 6,816 KB
testcase_19	AC	11 ms 6,816 KB
testcase_20	AC	11 ms 6,816 KB
testcase_21	AC	10 ms 6,816 KB
testcase_22	AC	10 ms 6,820 KB
testcase_23	AC	1 ms 6,816 KB
testcase_24	AC	2 ms 6,816 KB
testcase_25	AC	1 ms 6,820 KB
testcase_26	AC	1 ms 6,820 KB
testcase_27	AC	1 ms 6,816 KB
testcase_28	AC	1 ms 6,816 KB
testcase_29	AC	2 ms 6,820 KB
testcase_30	AC	1 ms 6,816 KB
testcase_31	AC	1 ms 6,820 KB
testcase_32	AC	1 ms 6,820 KB
testcase_33	AC	8 ms 6,820 KB
testcase_34	AC	8 ms 6,820 KB
testcase_35	AC	7 ms 6,820 KB
testcase_36	AC	8 ms 6,816 KB
testcase_37	AC	8 ms 6,816 KB
testcase_38	AC	8 ms 6,816 KB
testcase_39	AC	8 ms 6,820 KB
testcase_40	AC	8 ms 6,820 KB
testcase_41	AC	8 ms 6,816 KB
testcase_42	AC	8 ms 6,816 KB
testcase_43	AC	7 ms 6,816 KB
testcase_44	AC	7 ms 6,816 KB
testcase_45	AC	1 ms 6,816 KB
testcase_46	AC	1 ms 6,816 KB
testcase_47	AC	1 ms 6,816 KB
testcase_48	AC	2 ms 6,816 KB
testcase_49	AC	2 ms 6,820 KB

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

コンパイルメッセージ

/home/judge/data/code/Main.nim(5, 5) Warning: imported and not used: 'algorithm' [UnusedImport]
/home/judge/data/code/Main.nim(6, 5) Warning: imported and not used: 'bitops' [UnusedImport]
/home/judge/data/code/Main.nim(15, 5) Warning: imported and not used: 'sugar' [UnusedImport]
/home/judge/data/code/Main.nim(8, 5) Warning: imported and not used: 'heapqueue' [UnusedImport]
/home/judge/data/code/Main.nim(13, 5) Warning: imported and not used: 'strformat' [UnusedImport]

ソースコード

raw source code

when not declared ATCODER_YULY3HEADER_HPP:
  const ATCODER_YULY3HEADER_HPP* = 1

  import
    algorithm,
    bitops,
    deques,
    heapqueue,
    math,
    macros,
    sets,
    sequtils,
    strformat,
    strutils,
    sugar,
    tables

  proc transLastStmt(n, res, bracketExpr: NimNode): (NimNode, NimNode, NimNode) =
    # Looks for the last statement of the last statement, etc...
    case n.kind
    of nnkIfExpr, nnkIfStmt, nnkTryStmt, nnkCaseStmt:
      result[0] = copyNimTree(n)
      result[1] = copyNimTree(n)
      result[2] = copyNimTree(n)
      for i in ord(n.kind == nnkCaseStmt)..<n.len:
        (result[0][i], result[1][^1], result[2][^1]) = transLastStmt(n[i], res, bracketExpr)
    of nnkStmtList, nnkStmtListExpr, nnkBlockStmt, nnkBlockExpr, nnkWhileStmt,
        nnkForStmt, nnkElifBranch, nnkElse, nnkElifExpr, nnkOfBranch, nnkExceptBranch:
      result[0] = copyNimTree(n)
      result[1] = copyNimTree(n)
      result[2] = copyNimTree(n)
      if n.len >= 1:
        (result[0][^1], result[1][^1], result[2][^1]) = transLastStmt(n[^1],
            res, bracketExpr)
    of nnkTableConstr:
      result[1] = n[0][0]
      result[2] = n[0][1]
      if bracketExpr.len == 1:
        bracketExpr.add([newCall(bindSym"typeof", newEmptyNode()), newCall(
            bindSym"typeof", newEmptyNode())])
      template adder(res, k, v) = res[k] = v
      result[0] = getAst(adder(res, n[0][0], n[0][1]))
    of nnkCurly:
      result[2] = n[0]
      if bracketExpr.len == 1:
        bracketExpr.add(newCall(bindSym"typeof", newEmptyNode()))
      template adder(res, v) = res.incl(v)
      result[0] = getAst(adder(res, n[0]))
    else:
      result[2] = n
      if bracketExpr.len == 1:
        bracketExpr.add(newCall(bindSym"typeof", newEmptyNode()))
      template adder(res, v) = res.add(v)
      result[0] = getAst(adder(res, n))

  macro collect*(init, body: untyped): untyped =
    runnableExamples:
      import sets, tables
      let data = @["bird", "word"]
      ## seq:
      let k = collect(newSeq):
        for i, d in data.pairs:
          if i mod 2 == 0: d
      assert k == @["bird"]
      ## seq with initialSize:
      let x = collect(newSeqOfCap(4)):
        for i, d in data.pairs:
          if i mod 2 == 0: d
      assert x == @["bird"]
      ## HashSet:
      let y = initHashSet.collect:
        for d in data.items: {d}
      assert y == data.toHashSet
      ## Table:
      let z = collect(initTable(2)):
        for i, d in data.pairs: {i: d}
      assert z == {0: "bird", 1: "word"}.toTable

    let res = genSym(nskVar, "collectResult")
    expectKind init, {nnkCall, nnkIdent, nnkSym}
    let bracketExpr = newTree(nnkBracketExpr,
      if init.kind == nnkCall: init[0] else: init)
    let (resBody, keyType, valueType) = transLastStmt(body, res, bracketExpr)
    if bracketExpr.len == 3:
      bracketExpr[1][1] = keyType
      bracketExpr[2][1] = valueType
    else:
      bracketExpr[1][1] = valueType
    let call = newTree(nnkCall, bracketExpr)
    if init.kind == nnkCall:
      for i in 1 ..< init.len:
        call.add init[i]
    result = newTree(nnkStmtListExpr, newVarStmt(res, call), resBody, res)

  proc input*(): string {.inline.} = stdin.readLine
  proc inputs*(): seq[string] {.inline.} = stdin.readLine.split
  proc inputInt*(): int {.inline.} = stdin.readLine.parseInt
  proc inputInts*(): seq[int] {.inline.} = stdin.readLine.split.map(parseInt)
  proc chmax*[T](n: var T, m: T) {.inline.} = n = max(n, m)
  proc chmin*[T](n: var T, m: T) {.inline.} = n = min(n, m)
  proc `%=`*[T: SomeInteger](n: var T, m: T) {.inline.} = n = floorMod(n, m)
  proc `|=`*[T: SomeInteger or bool](n: var T, m: T) {.inline.} = n = n or m
  proc `&=`*[T: SomeInteger or bool](n: var T, m: T) {.inline.} = n = n and m
  proc `^=`*[T: SomeInteger or bool](n: var T, m: T) {.inline.} = n = n xor m
  proc `<<=`*[T: SomeInteger](n: var T, m: T) {.inline.} = n = n shl m
  proc `>>=`*[T: SomeInteger](n: var T, m: T) {.inline.} = n = n shr m

when isMainModule:
  const MOD = 10^9 + 7
  var N = inputInt()
  var S = input()

  const yuki = "yukicoder"
  var dp: array[10, array[2, int]]
  dp[0][0] = 1

  for i in 0..<N:
    var ndp: array[10, array[2, int]]
    ndp[0][0] = 1

    for j in countdown(yuki.len, 0):
      ndp[j] = dp[j]
      if j == yuki.len:
        continue

      if S[i] == yuki[j]:
        ndp[j + 1][0] += dp[j][0]
        if ndp[j + 1][0] >= MOD: ndp[j + 1][0] -= MOD
        ndp[j + 1][1] += dp[j][1]
        if ndp[j + 1][1] >= MOD: ndp[j + 1][1] -= MOD

      elif S[i] == '?':
        ndp[j + 1][1] += dp[j][0]
        if ndp[j + 1][1] >= MOD: ndp[j + 1][1] -= MOD
    dp = ndp
  echo sum(dp[yuki.len]) mod MOD