ABC144 E - Gluttony - あっとのTECH LOG

問題原文

問題要旨

$N$ 人のメンバーと、 $N$ 種類の食べ物がある。 $i$ 番目のメンバーの消化コストは $A_i$ で、食べ物 $i$ の食べにくさは $F_i$ である。
一人のメンバーに対して、一つの食べ物を割り当てる。この時、そのメンバーが食べ物を完食するのには、 (そのメンバーの消化コスト) × (その食べ物の食べにくさ) 秒だけかかる。
以下の操作が $K$ 回許されている時、各メンバーに対して食べ物を適切に割り当てた時の、 (そのメンバーの消化コスト) × (その食べ物の食べにくさ) の最大値を求めよ。
操作
消化コストが１以上のあるメンバー一人の消化コストを１減らす

$1 \leq N \leq 2 × 10^{5}$
$0 \leq K \leq 10^{18}$
$1 \leq A_i, F_i \leq 10^{6}$

解法

明らかに消化コストが低いメンバー順に、食べにくさが大きい食べ物を割り当てていくのが最適。この食べ物の割り当ては固定。
以降各メンバーのコストを、上記の割り当てを行った上で、 $A_iF_i$ とする。

操作を行うべきメンバーは、 $A_iF_i$ が最大のメンバー。
優先度付きキューで管理すれば、最大のメンバーを取り出す操作は $O(logN)$ でできるが、操作回数がバカでかいのでシミュレーションはできない。

答えに単調性があることに気づく。つまりにぶたんができる。
答えを $x$ にすることができるかどうかは、各メンバーの $A_iF_i$ を $x$ 以下にするために何回修行したかによる。
あるメンバーについて、 $A_iF_i$ を $x$ 以下にするために必要なコストは、適に式変形して $\min(0, a - \frac{x}{f})$ （小数点以下切り捨て）となる。

これでにぶたんができるようになって、解ける。

実装

達成不可能が画定したらにぶたんを打ち切るのがいい。

N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
F = sorted(list(map(int, input().split())), reverse=True)


# にぶたん := N人のメンバーそれぞれが完食にかかる時間のうち最大値をxに以下にできるか？
ok, ng = 10 ** 12 + 1, -1
while ok - ng > 1:
    x = (ok + ng) // 2

    need_training = 0
    for a, f in zip(A, F):
        need_training += max(0, a - x // f)

        if need_training > K:
            ng = x
            break
    else:
        ok = x

print(ok)

感想

にぶたん典型〜〜教育的な問題だと思います。