#984102 (Crystal) No.703 ゴミ拾い Easy

提出ソース
結果

問題	No.703 ゴミ拾い Easy
コンテスト
ユーザー	tamura2004
提出日時	2024-05-30 10:55:32
言語	Crystal (1.14.0)
結果	AC
実行時間	487 ms / 1,500 ms
コード長	11,195 bytes
コンパイル時間	18,115 ms
コンパイル使用メモリ	299,908 KB
実行使用メモリ	42,112 KB
最終ジャッジ日時	2024-12-20 21:09:00
合計ジャッジ時間	25,251 ms
ジャッジサーバーID （参考情報）	judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 4
other	AC * 46
権限があれば一括ダウンロードができます
ソースコード

raw source code
# require "crystal/cht"

# require "crystal/orderedset"

# require "crystal/avl_tree"

# AVL木によるOrderedSet
class AVLTree(T)
  getter root : Node(T)?

  def initialize(@root : Node(T)? = nil)
  end

  def includes?(v : T)
    root.try &.includes?(v)
  end

  def insert(v : T)
    @root = root.try &.insert(v) || Node(T).new(v)
  end
  
  def <<(v : T)
    insert(v)
  end

  def insert_at(i : Int32, v : T)
    @root = root.try &.insert_at(i, v) || Node(T).new(v)
  end

  def []=(i : Int32, v : T)
    insert_at(i, v)
  end

  def delete(v : T)
    @root = root.try &.delete(v)
  end

  def >>(v : T)
    delete(v)
  end

  # v以下（未満）の最大値
  #
  # ```
  # tr = [1, 3, 5, 7].to_ordered_set
  # tr.lower(4)            # => 3
  # tr.lower(5)            # => 5
  # tr.lower(5, eq: false) # => 3
  # tr.lower(0)            # => nil
  # ```
  def lower(v, eq = true)
    @root.try &.lower(v, eq)
  end

  # v以下（未満）の最大のインデックス
  def lower_index(v, eq = true)
    @root.try &.lower_index(v, eq)
  end

  # v以下（未満）の要素数
  def lower_count(v, eq = true)
    @root.try(&.lower_index(v, eq)).try(&.succ) || 0
  end

  # v以上（より大きい）の最小値
  # ```
  # tr = [1, 3, 5, 7].to_ordered_set
  # tr.upper(8)            # => nil
  # tr.upper(5)            # => 7
  # tr.upper(5, eq: false) # => 5
  # ```
  def upper(v, eq = true)
    @root.try &.upper(v, eq)
  end

  def upper_index(v, eq = true)
    @root.try &.upper_index(v, eq)
  end

  # v以上（より大きい）要素数
  def upper_count(v, eq = true)
    @root.try(&.upper_index(v, eq)).try { |v| (@root.try(&.size) || 0) - v } || 0
  end

  # 区間の要素数
  def count(r : Range(Int::Primitive?, Int::Primitive?))
    lo = r.begin || min
    hi = (r.end || max)
    return 0 if lo.nil? || hi.nil?
    eq = !r.excludes_end?
    lower_count(hi, eq) - lower_count(lo, eq: false)
  end

  # 最小の値を持つノード
  def min_node
    @root.try &.min_node
  end

  # 最小の値
  def min
    @root.try &.min
  end

  # 最大の値を持つノード
  def max_node
    @root.try &.max_node
  end

  # 最大の値
  def max
    @root.try &.max
  end

  # 最大値を削除して返す
  def pop
    @root, node = root.try &.pop || {nil.as(Node(T)?), nil.as(Node(T)?)}
    node
  end

  # 小さいほうからk番目のノードの値(0-origin)
  def at(k)
    @root.try &.at(k)
  end

  def [](k)
    at(k).not_nil!
  end

  def size
    @root.try &.size || 0
  end

  def clear
    @root = nil
  end

  def inspect
    @root.inspect
  end

  def to_a
    @root.try &.to_a || [] of T
  end

  def debug
    @root.try &.debug(0)
  end

  class Node(T)
    getter val : T
    getter balance : Int32
    getter height : Int32
    getter size : Int32
    property left : Node(T)?
    property right : Node(T)?

    def initialize(@val)
      @balance = 0
      @size = 1
      @height = 1
      @left = nil
      @right = nil
    end

    def includes?(v : T)
      if v == val
        true
      elsif v < val
        left.try &.includes?(v)
      else
        right.try &.includes?(v)
      end
    end

    # 挿入
    def insert(v)
      return self if v == val
      if v < val
        @left = left.try &.insert(v) || Node(T).new(v)
      else
        @right = right.try &.insert(v) || Node(T).new(v)
      end
      update
      re_balance
    end

    # i番目に挿入
    def insert_at(i, v)
      ord = left_size
      if i <= ord
        @left = left.try &.insert_at(i, v) || Node(T).new(v)
      else
        @right = right.try &.insert_at(i - ord - 1, v) || Node(T).new(v)
      end
      update.re_balance
    end

    # 削除
    def delete(v)
      if v == val
        left.try do |l|
          @left, node = l.pop
          node.left, node.right = left, right
          node.update.re_balance
        end || right.try do |r|
          right
        end || nil
      elsif v < val
        @left = left.try &.delete(v)
        update.re_balance
      else
        @right = right.try &.delete(v)
        update.re_balance
      end
    end

    # v以下（未満）の最大値
    def lower(v, eq = true)
      if val < v || (eq && v == val)
        right.try(&.lower(v, eq)).try { |v| Math.max(v, val) } || val
      else
        left.try &.lower(v, eq)
      end
    end

    # v以下（未満）の最大のインデックス
    def lower_index(v, eq = true)
      pos = left_size
      if val < v || (eq && v == val)
        right.try(&.lower_index(v, eq)).try(&.+(pos + 1)) || pos
      else
        left.try(&.lower_index(v, eq))
      end
    end

    # v以上（超える）の最小値
    def upper(v, eq = true)
      if v < val || (eq && v == val)
        left.try(&.upper(v, eq)).try { |v| Math.min(v, val) } || val
      else
        right.try &.upper(v, eq)
      end
    end

    # v以上（超える）の最小のインデックス
    def upper_index(v, eq = true)
      pos = left_size
      if val > v || (eq && v == val)
        left.try(&.upper_index(v, eq)) || pos
      else
        right.try(&.upper_index(v, eq)).try(&.+(pos + 1))
      end
    end

    # 最大値を削除して返す
    def pop
      right.try do |r|
        @right, node = r.pop
        {update, node}
      end || {left, self}
    end

    # 最小のノード
    def min_node
      left.try &.min_node || self
    end

    # 最小の値
    def min
      min_node.try &.val
    end

    # 最大のノード
    def max_node
      right.try &.max_node || self
    end

    # 最大の値
    def max
      max_node.try &.val
    end

    # 小さいほうからk番目のノードの値(0-origin)
    def at(k)
      return at(size + k) if k < 0
      ord = left_size
      if k == ord
        val
      elsif k < ord
        left.try &.at(k)
      else
        right.try &.at(k - ord - 1)
      end
    end

    # ノードの状態を更新
    def update
      @height = Math.max(left_height, right_height) + 1
      @balance = left_height - right_height
      @size = left_size + right_size + 1
      self
    end

    # 回転によりバランスを保つ
    def re_balance
      case balance
      when 2..
        if left_balance < 0
          @left = left.try &.rotate_left.update
        end
        rotate_right.update
      when ..-2
        if right_balance > 0
          @right = right.try &.rotate_right.update
        end
        rotate_left.update
      else
        self
      end
    end

    # 左回転
    def rotate_left
      right.try do |root|
        root.tap do
          @right, root.left = root.left, self
          root.update
          update
        end
      end || self
    end

    # 右回転
    def rotate_right
      left.try do |root|
        root.tap do
          @left, root.right = root.right, self
          root.update
          update
        end
      end || self
    end

    @[AlwaysInline]
    def [](k)
      at(k).not_nil!
    end

    {% for dir in %w(left right) %}
      {% for op in %w(size height balance) %}
        @[AlwaysInline]
        private def {{dir.id}}_{{op.id}}
          {{dir.id}}.try &.{{op.id}} || 0
        end
      {% end %}
    {% end %}

    @[AlwaysInline]
    private def left_to_a
      left.try &.to_a || [] of T
    end

    @[AlwaysInline]
    private def right_to_a
      right.try &.to_a || [] of T
    end

    def inspect
      # "(#{val} #{left.inspect} #{right.inspect})".gsub(/nil/, ".")
      # "(#{left.inspect} #{val} #{right.inspect})".gsub(/nil/, ".")
      "(#{left.inspect} #{val} #{right.inspect})".gsub(/nil/, ".")
    end

    def to_a
      left_to_a + [val] + right_to_a
    end

    def debug(indent = 0)
      left.try &.debug(indent + 2)
      puts " " * indent + "#{val}[#{size},#{height},#{balance}]"
      right.try &.debug(indent + 2)
    end
  end
end

module Indexable(T)
  def to_avl
    AVLTree(T).new.tap do |tr|
      each do |v|
        tr << v
      end
    end
  end
end

alias Orderedset = AVLTree

module Indexable(T)
  def to_ordered_set
    to_avl
  end
end

record Line, a : Int64, b : Int64 do
  include Comparable(Line)

  # 傾きの降順、y切片の昇順で比較
  #   /     \
  #  /   ->  \
  # /         \
  def <=>(other : Line) : Int32
    { -a, b } <=> { -other.a, other.b }
  end

  def cross(other : Line) : Int64
    (other.b - b) // (a - other.a)
  end

  def [](x : Int64)
    a * x + b
  end
end

# 動的 Convex Hull Trick
#  - 直線の追加: O(log N)
#  - 最小値クエリ: O(log N)
class CHT
  getter lines : Orderedset(Line)
  delegate to_a, size, to: lines

  def initialize
    @lines = Orderedset(Line).new
  end

  def add(line : Line)
    return if lines.includes?(line)

    # 傾きが同じ直線が既に存在する場合
    # y切片が小さい方を残す
    if left = lines.lower(line, eq: false)
      if line.a == left.a
        return unless line.b < left.b
        lines.delete(left)
        lines << line
      end
    else
      lines << line
    end

    # 傾きが同じ直線が既に存在する場合
    # y切片が小さい方を残す
    if right = lines.upper(line, eq: false)
      if line.a == right.a
        return unless line.b < right.b
        lines.delete(right)
        lines << line
      end
    else
      lines << line
    end

    # 両側に直線が存在する場合
    # 交点より小さい場合は追加する
    if left = lines.lower(line, eq: false)
      if right = lines.upper(line, eq: false)
        return unless left.cross(line) < line.cross(right)
        lines << line
      end
    end

    # 小さい方の直線が交点を上回る場合は削除する
    if left_right = lines.lower(line, eq: false)
      while left_left = lines.lower(left_right, eq: false)
        unless left_left.cross(left_right) < left_right.cross(line)
          lines.delete(left_right)
          left_right = left_left
        else
          break
        end
      end
    end

    # 大きい方の直線が交点を上回る場合は削除する
    if right_left = lines.upper(line, eq: false)
      while right_right = lines.upper(right_left, eq: false)
        unless line.cross(right_left) < right_left.cross(right_right)
          lines.delete(right_left)
          right_left = right_right
        else
          break
        end
      end
    end 
  end

  def <<(line : Line)
    add(line)
  end

  def min(x : Int64) : Int64
    return Int64::MAX if lines.size == 0
    return lines[0][x] if lines.size == 1
    return Math.min(lines[0][x], lines[1][x]) if lines.size == 2

    n = lines.size - 1
    i = (0...n).bsearch do |i|
      lines[i][x] < lines[i + 1][x]
    end || n
    lines[i][x]
  end
end

# dp[i] := ゴミiを拾うときの最小値(1-indexed)
# dp[i] = Min j <= i, dp[j-1] + (x[j] - a[i])^2 + y[j]^2
# dp[i] = a[i]^2 + Min j <= i, Line.new(-2x[j], dp[j-1] + x[j]^2 + y[j]^2)[a[i]]

n = gets.to_s.to_i64
a = gets.to_s.split.map(&.to_i64)
x = gets.to_s.split.map(&.to_i64)
y = gets.to_s.split.map(&.to_i64)

dp = Array.new(n+1, 0_i64)
cht = CHT.new

(0...n).each do |i|
  cht << Line.new(-2_i64 * x[i], dp[i] + x[i] ** 2 + y[i] ** 2)
  dp[i+1] = a[i] ** 2 + cht.min(a[i])
end

pp dp[-1]
yukicoder

結果

ソースコード
