解答
#!/usr/bin/env ruby
file = $stdin
lines = file.readlines
file.close
N, D = lines[0].split.map{|x| x.to_i}
p = lines[1, N].map{|x| x.to_i}
m = lines[N + 1, D].map{|x| x.to_i}
p.sort!
def calc(th, p)
i = 0
j = p.length - 1
max_total = 0
while i < j
total = p[i] + p[j]
if total == th
return total
elsif total < th
max_total = [max_total, total].max
i += 1
elsif total > th
j -= 1
end
end
return max_total
end
results = []
for th in m
p_selected = p.select {|x| x <= th - p.first}
results += [calc(th, p_selected)]
end
puts results
コードの覚え書き
- 必ず 2 つの商品を購入してその合計金額ということだったので、商品をソートして並べて、2 つのマーカーを移動させて探索する。
- キャンペーン数でループ
- マーカーを移動させて探索
- 最高額(最右) p[j] と最低額(最左) p[i] の組み合わせで、すでにキャンペーン金額 (th) を越えているのなら、高額商品 p[j] を下げるしかない。
- キャンペーン金額内の最高額の商品 p[j] が確定したら、低額商品 p[i] の方を目一杯高額なものを選択する。
- もしかしたら高額商品を別のを選択することで、合計金額はより高いものがあるかもしれない。
- しかし、その場合は低額商品 p[j] はより高いものになる。
- なぜならば過去に p[i] + p[j] <= th が成立しているならば、単に高額側の商品を下げた p[i] + p[j - 1] は (ソートしてあるため) p[i] + p[j - 1] < p[i] + p[j] <= th が成立して最大候補ではない。
- 計算量
- キャンペーン日数 D のループ * 商品点数 N の移動量 = O(DN + 事前ソート)
解説を読んでのメモ
- 当初、入出力周りがボトルネックになっていることに気づかなかった。
- 解説の O(NlogN + DN) で紹介されているアルゴリズムの説明おかしくないか? p[i] を安い商品にして、p[k] を降順にするならば、p[k] は下端ではなく上端では。
- 結果発表で紹介されているコードは、コメントを読むと集計用のテストケース以外では正しくないことがあるらしい。ただこれはバグではなく、実は商品数が膨大なテストケースではキャンペーン設定値を決め打ちで返しているため。確率的に考えると多くのテストケースでそうなるらしい。
