PAST1M
考えたこと
比率を最大化する選び方を探す問題
比率の大小関係に関して何かあるかな
3/1と200/100では前者が大きいが、0/100を足すと後者の方が大きい
比率に関するDP問題
今回は値の範囲が10^5だから無理だな
公式解説
比率を直接最大化するのではなく、比率がXを超えるかの判定問題にする
これはO(NlogN)で判定できる
比率の取りうる範囲について二分探索すればよい
時間をおいて考えたこと
Nが1000なので2^Nの全探索は無理
貪欲に「大きくなるものを足していく」ではダメか？
「X1 < X1 + X2 なら X1 + X3 < X1 + X2 + X3」ならOK
pythonfrom random import randint
for i in range(1000):
a, b, c, d, e, f = [randint(1, 10) for i in range(6)]
if a / b < (a + c) / (b + d) and (a + e) / (b + f) > (a + c + e) / (b + d + f):
print(a, b, c, d, e, f)
break反例あっさり見つかった: 5 8 5 7 8 7
和の比率の最大化をベースに考える
Xを超えるかどうかの判定問題にする
B_i - X A_iの符号判定問題
Mから最大のものを1つ選ぶ
すべて負なら「選ばない」の0が最大
ソートして最も大きいものが正ならOK
3WA
pythondef solve(N, M, AS, BS, CS, DS):
left = 0.0
right = 1000000.0
while left < right - 10 ** -7:
x = (left + right) / 2
y = max(DS[i] - x * CS[i] for i in range(M))
zs = list(sorted([BS[i] - x * AS[i] for i in range(N)], reverse=True))
if y > 0:
y = y + sum(zs[:4])
else:
y = sum(zs[:5])
if y >= 0:
left = x
else:
right = x
return leftrightは10001で良いはず、多めに1000000にしたが変化なし
left < right - 10 ** -7は要求されてる10 ** -6より小さくしてある
あ、わかった
if y > 0: → if y > zs[4]: か→AC
最良のお助けが負のスコアの時「得しないから使わなくて良い」と判断したが「5匹選ばなければならない」という制約によりお助けを選ばない場合にはzs4が選ばれることになるので、こちらがもっと大きなマイナスである可能性がある
Related Pages
- →chokudai×貪欲法の証明パターン×選択肢が少ない方から貪欲×マトロイド×クラスカル法×区間スケジューリング×交換しても悪化しない×アルゴリズムとデータ構造×区間はマトロイドではない×abc076b×現在が良いほど未来も良い×poj3617×poj3069×ダイクストラ法×agc009a×arc111×abc187×arc110c×一回り小さい同じ形の問題×agc049b×abc103d×abc023d×和の比率の最大化×単位時間ジョブスケジューリング問題×乱択＋貪欲×abc171_f×離散凸性→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]