PAST1M
https://gyazo.com/6e7b0970c5ef90359fec6baba959c845
考えたこと
比率を最大化する選び方を探す問題
比率の大小関係に関して何かあるかな
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
code:python
from random import randint
for i in range(1000):
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
code:python
def solve(N, M, AS, BS, CS, DS):
left = 0.0
right = 1000000.0
while left < right - 10 ** -7:
x = (left + right) / 2
y = max(DSi - x * CSi for i in range(M)) zs = list(sorted([BSi - x * ASi for i in range(N)], reverse=True)) if y > 0:
else:
if y >= 0:
left = x
else:
right = x
return left
rightは10001で良いはず、多めに1000000にしたが変化なし
left < right - 10 ** -7は要求されてる10 ** -6より小さくしてある
あ、わかった if y > 0:→ if y > zs[4]:か
→AC
最良のお助けが負のスコアの時「得しないから使わなくて良い」と判断したが「5匹選ばなければならない」という制約によりお助けを選ばない場合にはzs4が選ばれることになるので、こちらがもっと大きなマイナスである可能性がある