結果

問題 No.2905 Nabeatsu Integration
ユーザー 👑 amentorimaruamentorimaru
提出日時 2024-06-04 11:40:24
言語 Ruby
(3.3.0)
結果
AC  
実行時間 976 ms / 2,000 ms
コード長 654 bytes
コンパイル時間 699 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 22,144 KB
最終ジャッジ日時 2024-09-07 11:33:13
合計ジャッジ時間 43,984 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 87 ms
12,416 KB
testcase_01 AC 88 ms
12,288 KB
testcase_02 AC 86 ms
12,160 KB
testcase_03 AC 93 ms
12,544 KB
testcase_04 AC 86 ms
12,160 KB
testcase_05 AC 93 ms
12,416 KB
testcase_06 AC 91 ms
12,288 KB
testcase_07 AC 96 ms
12,416 KB
testcase_08 AC 86 ms
12,160 KB
testcase_09 AC 93 ms
12,416 KB
testcase_10 AC 94 ms
12,544 KB
testcase_11 AC 93 ms
12,288 KB
testcase_12 AC 91 ms
12,288 KB
testcase_13 AC 90 ms
12,160 KB
testcase_14 AC 91 ms
12,544 KB
testcase_15 AC 90 ms
12,416 KB
testcase_16 AC 92 ms
12,288 KB
testcase_17 AC 88 ms
12,160 KB
testcase_18 AC 88 ms
12,288 KB
testcase_19 AC 93 ms
12,416 KB
testcase_20 AC 86 ms
12,160 KB
testcase_21 AC 89 ms
12,544 KB
testcase_22 AC 89 ms
12,288 KB
testcase_23 AC 961 ms
21,888 KB
testcase_24 AC 799 ms
22,144 KB
testcase_25 AC 971 ms
22,016 KB
testcase_26 AC 802 ms
22,016 KB
testcase_27 AC 750 ms
21,888 KB
testcase_28 AC 976 ms
21,888 KB
testcase_29 AC 964 ms
22,144 KB
testcase_30 AC 794 ms
21,888 KB
testcase_31 AC 790 ms
22,016 KB
testcase_32 AC 965 ms
22,144 KB
testcase_33 AC 966 ms
22,016 KB
testcase_34 AC 775 ms
22,144 KB
testcase_35 AC 962 ms
21,888 KB
testcase_36 AC 772 ms
22,144 KB
testcase_37 AC 751 ms
22,016 KB
testcase_38 AC 960 ms
21,888 KB
testcase_39 AC 777 ms
21,888 KB
testcase_40 AC 961 ms
21,888 KB
testcase_41 AC 958 ms
22,016 KB
testcase_42 AC 765 ms
21,888 KB
testcase_43 AC 624 ms
21,888 KB
testcase_44 AC 633 ms
22,016 KB
testcase_45 AC 628 ms
21,888 KB
testcase_46 AC 627 ms
22,016 KB
testcase_47 AC 633 ms
21,888 KB
testcase_48 AC 612 ms
22,144 KB
testcase_49 AC 611 ms
22,016 KB
testcase_50 AC 622 ms
22,016 KB
testcase_51 AC 615 ms
21,888 KB
testcase_52 AC 618 ms
21,888 KB
testcase_53 AC 609 ms
21,888 KB
testcase_54 AC 615 ms
22,016 KB
testcase_55 AC 613 ms
22,144 KB
testcase_56 AC 608 ms
22,016 KB
testcase_57 AC 624 ms
22,016 KB
testcase_58 AC 689 ms
22,144 KB
testcase_59 AC 961 ms
21,888 KB
testcase_60 AC 942 ms
21,888 KB
testcase_61 AC 485 ms
20,096 KB
testcase_62 AC 612 ms
21,888 KB
testcase_63 AC 606 ms
22,016 KB
testcase_64 AC 605 ms
21,888 KB
testcase_65 AC 708 ms
22,016 KB
testcase_66 AC 647 ms
22,016 KB
testcase_67 AC 636 ms
21,888 KB
testcase_68 AC 619 ms
21,888 KB
testcase_69 AC 620 ms
21,888 KB
testcase_70 AC 961 ms
22,016 KB
testcase_71 AC 960 ms
21,888 KB
testcase_72 AC 973 ms
21,888 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

def z_algorithm(s)
  a = Array.new(s.length, 0)
  a[0] = s.length
  i = 1
  j = 0

  while i < s.length
    while i + j < s.length && s[j] == s[i + j]
      j += 1
    end
    a[i] = j
    if j == 0
      i += 1
      next
    end

    k = 1
    while i + k < s.length && k + a[k] < j
      a[i + k] = a[k]
      k += 1
    end

    i += k
    j -= k
  end

  a
end

def main
  s = gets.strip
  n = s.length
  a = z_algorithm(s)
  mod = 998244353
  ans = mod - n + 1
  add = 10
  (n - 1).downto(0) do |i|
    if a[i] + i >= n
      ans += add
      ans %= mod
    end
    add *= 10
    add %= mod
  end

  puts ans
end

main if __FILE__ == $PROGRAM_NAME
0