ABC057D D Maximum Average Sets
D Maximum Average Sets
Submission #2516578 - AtCoder Beginner Contest 057
所見
解説はなんだか頭よさそうなことをしているけれども、nCrをメモ化すれば愚直にやっても通る。doubleの精度が足りなくて死ぬやつを初めてやった。n時間やって1WAが消えず絶望してテストケース見たら誤差だった時の脱力感。
問題概要
N個の品物が与えられる。その中からA個以上B個以下の品物を選ぶとき、平均の最大値を求めよ。また、平均が最大となるような品物の選び方が何通りあるかを求めよ。
取った方針
(最大の平均値)品物の価値、最大化という文字列を見てナップザックを連想するが、品物の個数が与えられるので貪欲をすればよい。少し考えると平均値が最大となるのはA個のときであるが、N<=50なので別に全探索してもよい。
(品物の選び方)取る品物Aについて、入力の中にAがn個あり、その中からr個使う場合nCr通りの選び方が存在する。今回はn,rが50個以下なので、DPとかメモ化とかすれば(過去の周辺調査が役立った例)十分高速(DPならO(nr)なのでまあO(N2)くらい)に求められる。
これを用いて、最大の平均を持つ品物の個数について品物の選び方の総和を計算すればよい。先にO(N2)で表を作っておけば組み合わせの個数はO(1)で求められるので、雑な見積もりだが、A以上B以下のすべての個数について平均値を計算しても最悪O(N2)で計算ができる(全探索にN、組み合わせの積の計算に最悪N)。
しかし、v_i<=1015というのが曲者で、普通にdoubleを使うと誤差で死んでしまう。(1ケースだけ通らない)long doubleを使えば通る。
g++とかだと64 -> 80bitになって,long longの範囲を全部誤差なく扱えるようになる(はず)だよ
— 睡眠 (@yosupot) 2018年5月15日
正しい方針
ほぼ同上だが、直接平均値の計算をしていない点が異なる。
得られた知見
・組み合わせはn,rが十分小さければ時間計算量も空間計算量もO(nr)で前計算ができ、O(1)で値を取り出せる。
・doubleの有効桁数は15桁程度なので、1015みたいな制約にdoubleを使うと誤差死する。
・そういう場合はlong double(80bit、MSVCでは64bit)を使うと通ったり通らなかったりする。
・コンテスト終了後のAtCoderはテストケースが与えられている。
テストケースはここで公開されている。
解くのに必要な要素
・組み合わせの漸化式によるDP
・貪欲法
・doubleの精度は10進15桁程度
周辺調査によって得られた知見
特になし