毎日格上の問題を倒すやつの6日目です。

問題リンク

atcoder.jp

問題概要

$N$ 種類の品物がそれぞれ無限個あるよ。

$f(X)$ を、体積と重さが $X$ 以下になるように品物を選んだ時の価値の最大値と定義するよ。

$\lim_{ X \to \infty } \frac{f(X)}{X}$ は有限の値になるから、それを求めてね。

解法

求めたいものは、適切に品物を選んだときの $\min(\frac{価値の総和}{重さの総和},\frac{価値の総和}{体積の総和})$ となると入力例から推測できます。また、実際そうなることが示せます。

「答えは $x$ 以上か」という判定問題を解ければ、あとはにぶたんでゲームエンドです。

ここで、いわゆる平均を総和にするテクを使います。

$a=C_i-A_ix$ とするとき、 $a$ をすべての品物に対して求めたとき、この値の和が非負になるとき、またその時に限り、 $\frac{価値の総和}{重さの総和}$ が $x$ 以上になります。

$b=C_i-B_ix$ として、 $b$ もすべての品物に対して求めます。

ここで、 $a,b$ どちらも非負のものがあれば、それを選ぶだけで答えを $x$ 以上にできるので、そうでないものを考えます。

これは、 $a\lt 0,b\geq 0$ のものに対する $-\frac{b}{a}$ の最大値を $c$ 、 $a\geq 0,b\lt 0$ のものに対する $-\frac{a}{b}$ の最大値を $d$ としたとき、 $cd\geq 1$ であるかどうかを判定すればいいです。これを満たす場合、適切に個数を設定することで答えを $x$ 以上にできます。

よって、判定問題が解けたためあとはにぶたんして終わりです。¹

提出コード

N=int(input())
thing=[list(map(int,input().split())) for i in range(N)]
l=0
r=100
for i in range(100):
    mid=(l+r)/2
    lfmax=0
    rimax=0
    for a,b,c in thing:
        lf=c-a*mid
        ri=c-b*mid
        if lf>=0 and ri>=0:
            lfmax=1
            rimax=1
        if lf<0 and ri>=0:
            rimax=max(rimax,ri/(-lf))
        if lf>=0 and ri<0:
            lfmax=max(lfmax,lf/(-ri))
        if lfmax*rimax>=1:
            break
    if lfmax*rimax>=1:
        l=mid
    else:
        r=mid
print(l)

Submission #45952226 - AtCoder Beginner Contest 275

感想

ABCの橙Diff前半は簡単なものは簡単なのにARCの橙Diff前半は大抵クソむずなの…²

想定解は全然違う方法らしい。どうして…↩
なぁぜなぁぜ？というと一部の人に怒られるらしい↩

halcの競プロ精進ブログ

はるくが競プロしたことを書き留めるなにか

【今日の精進】ABC275G - Infinite Knapsack

問題リンク

問題概要

解法

提出コード

感想