abc137d, abc128eのネタバレを含むので、
ネタバレ無しで解きたい方は説いてから御覧ください。
問題
https://atcoder.jp/contests/abc137/tasks/abc137_d
解説
https://img.atcoder.jp/abc137/editorial.pdf
手順
[報酬がもらえるまでの日付, 報酬]を日付で昇順ソートして、 M-1日後にやって、1日後(今日からM日後)までに報酬がもらえる仕事の内最大の報酬の仕事を取る、 という形で報酬の最大化ができます。(自明) こういうデータ構造はABCのDぐらいだとちょくちょく求められるので予め作っておいた方が無難です。解答フロー
今日からM日後 までにもらえる報酬を最大化するための仕事の割り振りを、
今日から考えるのではなくM-1日後の仕事の予定から埋めていくイメージになります。
M-2日後にやって、2日後(今日からM日後)までに報酬がもらえる仕事の内最大の報酬の仕事を取る、
...
今日やってM日後までに報酬がもらえる仕事の内最大の報酬の仕事を取る。
1日後に報酬がもらえる仕事の報酬を最大Heap(親ノードの方が必ずでかい)にぶっこんで、1個pop(最大値を取り出す)、
2日後に報酬がもらえる仕事の報酬を最大Heapに全部ぶっこんで、1個pop
...
という形で時間内に答えることが出来るはずです。
https://github.com/k-karen/ruby-samples/blob/master/heap/pop_heap.rb
私の最大Heapを置いておきます、よろしければご利用ください。
高速化テク
ということで今回は[日付, 報酬]の配列を日付でsortしたいという場面が出てくると思います。
普通にやると
n, m = gets.split.map(&:to_i)
datas1 = []
n.times do
datas1 << gets.split.map(&:to_i)
end
datas1.sort_by!(&:first)
と書くと思いますが、 sort_by!(&:first)は(後述の方法より)早くないです。
今回は入力が全部正の値で、その上限が10^5程度とわかっていますので、
これを利用して以下のように書くことができます
# (10**5).bit_length #=> 17
# 17ビットずらせば、2つの値を独立に保存できる
n, m = gets.split.map(&:to_i)
datas2 = []
n.times do
tmp = gets.split.map(&:to_i)
datas2 << (tmp[0] << 17) + tmp[1]
end
datas2.sort!
これだと気持ち早くなります。
値を取り出すときは予めビットマスクを用意しておいて、それとandを取れば良いです。
mask = (1 << 17) - 1
datas.each do |day_salary|
day = day_salary >> 17
salary = day_salary & mask
end
どんぐらい早くなるか
before( max 817ms )
https://atcoder.jp/contests/abc137/submissions/6816390
after ( max 775ms )
https://atcoder.jp/contests/abc137/submissions/6840374
今回はあまり効果がありませんが、
多重キーソートも値の順番を正しく配置すればいい感じに行えます(ABC128E)
降順と昇順が入り交じる場合は、入力の上限から引いた値を入れるなどの工夫が必要になります。
俗に言うイベントソートで大活躍する手法です。
そもそもそんな小手先の高速化を行うなら、
RubyじゃなくてC++でかけという話、ごもっともなので勘弁してください。
最後に、同じような手法で出来る問題置いておきます。
https://atcoder.jp/contests/abc128/tasks/abc128_e