結果

問題 No.265 数学のテスト
ユーザー yuruhiyayuruhiya
提出日時 2021-07-03 16:14:38
言語 Crystal
(1.11.2)
結果
AC  
実行時間 13 ms / 2,000 ms
コード長 3,430 bytes
コンパイル時間 19,632 ms
コンパイル使用メモリ 256,376 KB
実行使用メモリ 9,508 KB
最終ジャッジ日時 2023-09-12 20:51:05
合計ジャッジ時間 21,511 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 11 ms
8,944 KB
testcase_01 AC 13 ms
9,508 KB
testcase_02 AC 10 ms
6,364 KB
testcase_03 AC 7 ms
5,152 KB
testcase_04 AC 7 ms
5,296 KB
testcase_05 AC 8 ms
5,172 KB
testcase_06 AC 7 ms
5,112 KB
testcase_07 AC 7 ms
5,192 KB
testcase_08 AC 9 ms
5,156 KB
testcase_09 AC 6 ms
5,172 KB
testcase_10 AC 7 ms
5,116 KB
testcase_11 AC 7 ms
5,160 KB
testcase_12 AC 2 ms
4,576 KB
testcase_13 AC 4 ms
5,116 KB
testcase_14 AC 4 ms
5,124 KB
testcase_15 AC 3 ms
4,412 KB
testcase_16 AC 4 ms
4,936 KB
testcase_17 AC 3 ms
4,408 KB
testcase_18 AC 2 ms
4,520 KB
testcase_19 AC 3 ms
4,376 KB
testcase_20 AC 3 ms
4,504 KB
testcase_21 AC 3 ms
4,380 KB
testcase_22 AC 4 ms
5,232 KB
testcase_23 AC 2 ms
4,376 KB
testcase_24 AC 2 ms
4,376 KB
testcase_25 AC 5 ms
5,036 KB
testcase_26 AC 2 ms
4,384 KB
testcase_27 AC 3 ms
4,384 KB
testcase_28 AC 3 ms
4,764 KB
testcase_29 AC 3 ms
4,504 KB
testcase_30 AC 3 ms
4,772 KB
testcase_31 AC 3 ms
4,408 KB
testcase_32 AC 3 ms
4,400 KB
testcase_33 AC 2 ms
4,556 KB
testcase_34 AC 2 ms
4,388 KB
testcase_35 AC 2 ms
4,508 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# require "/Scanner"
require "io/error"

class Scanner
  private def self.skip_to_not_space
    peek = STDIN.peek
    not_space = peek.index { |x| x != 32 && x != 10 } || peek.size
    STDIN.skip(not_space)
  end

  def self.s
    skip_to_not_space

    peek = STDIN.peek
    if index = peek.index { |x| x == 32 || x == 10 }
      STDIN.skip(index + 1)
      return String.new(peek[0, index])
    end

    String.build do |buffer|
      loop do
        buffer.write peek
        STDIN.skip(peek.size)
        peek = STDIN.peek
        break if peek.empty?
        if index = peek.index { |x| x == 32 || x == 10 }
          buffer.write peek[0, index]
          STDIN.skip(index)
          break
        end
      end
    end
  end
end

macro input_array(type, args)
  Array.new({{args.first}}) do
    {% if args.size == 1 %}
      input({{type.id}})
    {% else %}
      input_array({{type}}, {{args[1...args.size]}})
    {% end %}
  end
end

macro input(type)
  {% if type.is_a?(Path) %}
    {{type}}.new(Scanner.s)
  {% elsif type.is_a?(Var) || (type.is_a?(Call) && type.args.size == 0) %}
    {% if Scanner.methods.includes?(type.id) %}
      Scanner.{{type.id}}
    {% else %}
      Scanner.s.to_{{type.id}}
    {% end %}
  {% elsif type.name == "[]" %}
    input_array("{{type.receiver}}", {{type.args}})
  {% else %}
    input_array("{{type.name}}", {{type.args}})
  {% end %}
end

macro input(*types)
  {
    {% for type in types %}
      input({{type}}),
    {% end %}
  }
end

class Polynomial
  getter a : Array(Int64)

  def initialize(d : Int)
    @a = Array.new(d, 0i64)
  end

  def initialize(@a)
  end

  delegate size, to: @a
  delegate :[], to: @a
  delegate :[]=, to: @a

  def d
    Polynomial.new @a[1..].map_with_index(1) { |x, i| x * i } + [0i64]
  end

  def x
    Polynomial.new [0i64] + @a[..-2]
  end

  def +(other : self)
    Polynomial.new @a.zip(other.@a).map { |x, y| x + y }
  end

  def *(val : Int32)
    Polynomial.new @a.map { |x| x * val }
  end

  def to_s(io)
    io << @a
  end

  def inspect(io)
    io << @a
  end
end

class Solve
  getter n : Int32, d : Int32, s : Array(Char), hash : Hash(Int32, Int32)

  def initialize
    @n, @d = input(i, i)
    @d += 1
    @s = input(s).chars

    @hash = Hash(Int32, Int32).new
    stack = Deque(Int32).new
    s.each_with_index do |c, i|
      if c == '{'
        stack << i
      elsif c == '}'
        start = stack.pop
        hash[start + 1] = i - 1
      end
    end
  end

  def detect(pos : Int32)
    case s[pos]
    when 'd'
      end_pos = hash[pos + 2]
      {solve(pos + 2..end_pos).d, end_pos + 2}
    when 'x'
      res = Polynomial.new(d)
      res[1] = 1i64
      {res, pos + 1}
    when '1'..'9'
      res = Polynomial.new(d)
      res[0] = s[pos].to_i64
      {res, pos + 1}
    else
      raise "a"
    end
  end

  def solve(range : Range = 0..n - 1)
    first, pos = detect(range.begin)
    stack = Deque{first}
    while pos < range.end
      case s[pos]
      when '*'
        pos += 1
        case s[pos]
        when 'x'
          now = stack.pop
          stack.push now.x
        when '1'..'9'
          now = stack.pop
          stack.push now * s[pos].to_i
        else
          raise "b"
        end
        pos += 1
      when '+'
        now, pos = detect(pos + 1)
        stack << now
      else
        raise "c"
      end
    end
    stack.reduce { |x, y| x + y }
  end
end

puts Solve.new.solve.a.join(' ')
0