Ruby で解く AtCoder ABC 227 D

はじめに

AtCoder Problems の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。

今回のお題

AtCoder Beginner Contest D - Project Planning
Difficulty: 1643

今回のテーマ、二分探索　＋　鳩ノ巣原理

青レートは難しいですが、解いてみました。

Ruby

n, k = gets.split.map(&:to_i)
a = gets.split.map(&:to_i).sort
b =[0]
n.times do |i|
  b[i + 1] = b[i] + a[i]
end
ans = (0..).bsearch do |x|
  c = a.bsearch_index{ _1 >= x } || n
  b[c] + x * (n - c) < k * x
end
puts ans - 1

まず、1 つのプロジェクトは K 個の相異なる部署から 1 人ずつ選出となっていますので、鳩ノ巣原理より、各部署より選出できる人数は、作成するプロジェクト数が上限となります。

# あらかじめ累積和を作成
b =[0]
n.times do |i|
  b[i + 1] = b[i] + a[i]
end

# プロジェクトに選出できる人数を計算
  c = a.bsearch_index{ _1 >= x } || n
  b[c] + x * (n - c)

次に、プロジェクト数の最大を求めますが、各部署の社員が最大10の12乗人所属していますので、先頭から順番に探索してはTLEになってしまいます。
そこで、二分探索の登場となります。

ans = (0..).bsearch do |x|

ここで、上限をうまく設定しないとWAになったなりますのが、Rubyではハッピーな書き方があり、二分探索の威力もあって気楽にコーディングできます。

	Ruby
コード長 (Byte)	233
実行時間 (ms)	146
メモリ (KB)	33588

まとめ

• ABC 227 D を解いた