Submission #22286878

---

Source Code Expand

# frozen_string_literal: true

module Category
  # メンバー個人の能力用メソッド
  # ５つの能力がそれぞれボーダーをクリアしているかどうかで32通りに分ける。
  # 一つもクリアできていない人が二進法で00000、パワーだけクリアしている人が二進法で00001、全てクリアしている人が二進法で11111
  def categorize_thirty_two(border)
    buffer_answer = 0
    # 以下はself.each_with_index {|status, index| buffer_answer += 2**index if status >= border }と一緒
    # 何度も回すメソッドなのでブロック使うとTLEしそう。whileで高速化
    self_length = self.length
    index_i = 0
    while index_i <= self_length - 1
      buffer_answer += 2**index_i if self[index_i] >= border
      index_i += 1
    end
    buffer_answer
  end

  # 能力カテゴリ配列用のメソッド
  # [false,true,true...]から3人まで選んで、5能力ともクリアできるチームを作れるか
  def can_make_team
    # クリア出来た候補者が0人なら考えるまでもなくクリア不可
    return false if self.none?
    # 一人で全能力クリアできる人がいるならクリアできるに決まっている
    return true if self[-1]

    # カテゴリ1の人と3の人がいる場合[nil,true,nil,true.....]の形なので[1,3.....]に書き直す
    expanded_members = []
    self.each_with_index {|member_exist, category| expanded_members << category if member_exist }
    # メンバーが二人または3人の時は全員チーム選出。四人以上なら3人選抜。一人でクリアする場合は最初に早期リターンしている
    # 二人または３人の組み合わせでビット演算で論理和して5桁とも塗りつぶせたらOK。
    if expanded_members.size >= 3
      expanded_members.combination(3).each {|category_of_members| return true if category_of_members.inject(:|) == 31 }
    else
      expanded_members.combination(2).each {|category_of_members| return true if category_of_members.inject(:|) == 31 }
    end
    # 組み合わせがなかったらNG
    false
  end
end

class Array
  include Category
end

# 入力受付
MEMBERS_COUNT = gets.to_i
MEMBERS = Array.new(MEMBERS_COUNT) { gets.split.map(&:to_i) }
# 高すぎて絶対にクリアできないスコア
over_ng_limit = 1_000_000_001
# 低すぎて絶対にクリアできるスコア
under_ok_limit = 1
# 答えはこの中にあるので二部探索
until over_ng_limit - under_ok_limit == 1
  mid = (over_ng_limit + under_ok_limit) / 2
  categorized_members_count = Array.new(32)
  # 能力32分類でそれぞれ人がいるか、いないか
  MEMBERS.each do |member|
    # 0から31まで分類
    category = member.categorize_thirty_two(mid)
    # 分類できたらカテゴリの人数を0人から一人にする。二人以上いても意味ないので二人以上にはしない
    categorized_members_count[category] = true
    # 一人で全能力クリアできてる人がいるなら中断。それ以上考えるまでもなくクリアできる。これはTLEしないならやらなくてもいい
    break if categorized_members_count[-1]
  end
  # 全能力ボーダー未達の人が何人いても意味ないので無視。これはTLEしないならやらなくてもいい
  categorized_members_count[0] = false
  # クリアできるかどうか判定
  if categorized_members_count.can_make_team
    under_ok_limit = mid
  else
    over_ng_limit = mid
  end
end
puts under_ok_limit

Submission Info

Judge Result