🐢
[ABC354 C] AtCoder Magics
役に立たないカードを見つける実用問題。
問題を要約する
- 他と比べて攻撃力が低いのにコストが高いカードを削除する
- 残ったカードは？
例1で問題を理解する
| カード番号 | 攻撃力 | コスト |
|---|---|---|
| 1 | 2 | 4 |
| 2 | 1 | 1 |
| 3 | 3 | 2 |
1枚目のカードは攻撃力が3枚目のカードより低いにもかかわらずコストが高いのでいらない。残った 2, 3 が答え。
コンテスト中に考えたこと
- 攻撃力とコストでソートした二つの山を用意する
- カードを一つずつ取り出し、二分探索で二つの山のどの位置にあるかを調べる
- 他のカードより攻撃力が引く、コストが高いならそのカードを削除する
としてわけがわからなくなった。
正しい考え方
| カード番号 | 攻撃力 | コスト |
|---|---|---|
| 1 | 1 | 2 |
| 2 | 2 | 1 |
| 3 | 3 | 3 |
| 4 | 4 | 5 |
| 5 | 5 | 4 |
攻撃力とコストを座標として配置すると、
となって、不思議なことに左上と右下が、
- 左上 → いらない
- 右下 → いる
の関係になっている。そこで「いる」「いらない」をはっきりさせる境界線を作る。それには、
- コストの閾値を最大にしておく
- 右からカードを順に選択する
- そのカードのコストまで閾値を下げていく
とすれば、5 → 3 → 2 番のカードを通ったときに閾値が 4 → 3 → 1 と下がっていく。それを繋いだ境界線より上のカードは「それより攻撃力が高いカードがあるのにコストが無駄に高い」という状況なのでいらない。したがって境界線以下の 5, 3, 2 が「いる」カードになる。
例3の場合
解説の模範解答 (AC)
340 ms
N = gets.to_i # => 6
AC = N.times.collect { gets.split.collect(&:to_i) } # => [[32, 101], [65, 78], [2, 29], [46, 55], [103, 130], [52, 40]]
cards = AC.collect.with_index { |e, i| [e, i.next] } # => [[[32, 101], 1], [[65, 78], 2], [[2, 29], 3], [[46, 55], 4], [[103, 130], 5], [[52, 40], 6]]
cards.sort_by! { |(atk, _), _| -atk } # => [[[103, 130], 5], [[65, 78], 2], [[52, 40], 6], [[46, 55], 4], [[32, 101], 1], [[2, 29], 3]]
keep = []
min = Float::INFINITY
cards.each do |(_, cost), i|
if min > cost
AC[i.pred] # => [103, 130], [65, 78], [52, 40], [2, 29]
i # => 5, 2, 6, 3
min = cost # => 130, 78, 40, 29
keep << i
end
end
keep.sort! # => [2, 3, 5, 6]
p keep.size # => 4
puts keep * " "
二次元のグリッドで考えたもののグリッドはでてこない。
Discussion