結果

問題 No.9 モンスターのレベル上げ
コンテスト
ユーザー らっしー(raccy)
提出日時 2015-01-26 22:30:38
言語 Ruby
(3.4.1)
結果
TLE  
実行時間 -
コード長 2,216 bytes
コンパイル時間 45 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 17,792 KB
最終ジャッジ日時 2024-06-23 03:18:24
合計ジャッジ時間 6,917 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 WA * 2 TLE * 2 -- * 10
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff #
raw source code 

class Moster
  attr_reader :level, :count, :point
  attr_accessor :left, :right, :parent

  def initialize(level, count_over)
    @level = level
    @count_over = count_over
    @count = 0
    update_point
    @left = nil
    @right = nil
    @parent = nil
  end

  def get_exp(exp)
    @level += exp
    @count += 1
    update_point
  end

  def update_point
    @point = @level * @count_over - @count
  end

  def add_tree(other)
    if @point > other.point
      if @left
        @left.add_tree(other)
      else
        @left = other
        other.parent = self
      end
    else
      if @right
        @right.add_tree(other)
      else
        @right = other
        other.parent = self
      end
    end
  end

  def min_point
    if @left
      return @left.min_point
    else
      return self
    end
  end
end

class EnemyParty
  def initialize(level_list)
    @exp_list = level_list.map{|i|i / 2}
    @size = level_list.size
  end

  def exp_each_with_start_pos(start_pos)
    @size.times do |i|
      yield @exp_list[(start_pos + i) % @size]
    end
  end
end

class OwnParty
  def initialize(level_list)
    @moster_list = []
    @size = level_list.size
    @count_over = @size + 1
    @tree_root = nil
    level_list.each do |level|
      moster = Moster.new(level, @count_over)
      @moster_list << moster
      if @tree_root
        @tree_root.add_tree(moster)
      else
        @tree_root = moster
      end
    end
  end

  def max_count
    return @moster_list.max_by{|moster|moster.count}.count
  end

  def get_exp(exp)
    moster = @tree_root.min_point

    moster.get_exp(exp)

    if moster.right
      if moster.parent
        moster.parent.left = moster.right
        moster.right.parent = moster.parent
      else
        @tree_root = moster.right
        moster.right.parent = nil
      end
      moster.right = nil
    else
      moster.parent.left = nil
    end
    moster.parent = nil

    @tree_root.add_tree(moster)
  end
end

n = gets.to_i
own_list = gets.split.map(&:to_i)
ene = EnemyParty.new(gets.split.map(&:to_i))
list = (0..n).map do |i|
  own = OwnParty.new(own_list)
  ene.exp_each_with_start_pos(i) do |exp|
    own.get_exp(exp)
  end
  own.max_count
end
puts list.min
0