問題タイトルのグラトニーとは貪食という意味で、七つの大罪にも含まれる。グラットンソードはみんなの憧れ。
ABC143に続き、答えを決め打って二分探索で解ける問題。復習大事。
かかる時間の最小値は消化コストを全て0にしたときの0、最大値は $\max(A) \times \max(F) \le 10^{12}$。 この間で、タイム $t$ が達成可能を判定する。1回あたり $O(N)$ で判定できれば、全体で $O(N \log(\max(A) \max(F)))$ でできる。
誰がどれを担当すればよいかというと、$A_i$ を昇順に、$F_i$ を降順にソートして、先頭から順番に組にしていけばよい。
以下、$A_1,A_2,...$ は昇順ソート済み、$F_1,F_2,...$ は降順ソート済みの順番とする。
特訓して消化コストを下げた状態を $B_1,B_2,...$ とする。
最大値を低くするのだから、小さいのと大きいのを組み合わせればいいというのはなんとなく思うので、それが正しいことを証明する。
i 1 2 3 B 3 5 8 F 10 7 2
ここで $B$昇順・$F$降順に並んだ状態から、$B_2$ と $B_3$ を入れ替えて、変化した部分のみのスコアを比較すると
ここで、$B_3F_2$ は、$B_2F_2, B_3F_3$ のいずれよりも必ず大きい（か等しい）ので、入れ替えてスコアが悪くなることはあっても、改善されることは無い。
よって、この状態が最適で、降順の $F$ に対して、$B$ は昇順で組にしてよい。
（ここから、特訓後 $B_i$ に対応するのは $A_i$ でいいのかの証明も必要だが、略）
食べ物の大きさ $F_i$ と目標タイム $t$ が決まっていたら、それを担当する人の消化コスト $B_i$ の制約は決まり、$B_i \le \frac{t}{F_i}$（切り捨て）である。
$A_i$ が $\frac{t}{F_i}$ より大きいなら、その差分だけ特訓が必要。逆に低いなら不要。
必要な特訓量を計算し、その合計が $K$ 以下なら目標タイム $t$ は達成可能と判定できる。
素のPythonで組むとちょっと時間が厳しめだが、こういう「配列の全ての数を $x$ で割る」「2つの配列の同じindexを組にして同じ演算を行っていく」処理はNumPyが使いどころ。
import numpy as np
def solve(n, k, aaa, fff):
aaa = np.sort(aaa)
fff = np.sort(fff)[::-1]
l = 0
r = 10 ** 12
while l <= r:
m = (l + r) // 2
req = np.clip(aaa - m // fff, 0, None).sum()
if req > k:
l = m + 1
else:
r = m - 1
return l
n, k = list(map(int, input().split()))
aaa = np.array(list(map(int, input().split())), dtype=np.int64)
fff = np.array(list(map(int, input().split())), dtype=np.int64)
print(solve(n, k, aaa, fff))
「この部屋から伸びる通路を消す」と決め打って、その時の期待値を求めて最小値を探す。全体で $O(M)$ となる。
通路を消すという奇妙な操作はできるものの、まずはそもそもの消さない場合の期待値の計算が出来ないことには答えが出ないので、その方法を考える。
通路の条件を見ると、$s_i \lt t_i$ より有向非巡回グラフであることがわかるので、部屋番号の若い方から順に処理していけそう。
しかし先頭から順に決めていこうとすると、いまいちうまくできない。 各部屋につき「通った通路数」と「その通路数でその部屋に到達する確率」を分けて持てば計算できなくは無いが…… 遷移の計算量が $N$ 倍になって面倒なので、他の方法を考える。
,---------------,
1 ------ 2 ------ 3 ------ 4
`---------------' |
`------------------------'
(通路,確率) (0,1) (1,1/3) (1,1/3) (1,1/3)
(2,1/6) (2,1/2)
(3,1/6)
後ろから求めるとうまくいく。「部屋 $i$ を出発して」$N$ までに通る通路数の期待値 $e_i$ を求めていく。
部屋 $i$ から $j,k,l$ に出路があったとすると、$e_j,e_k,e_l$ は既に求まっているので $\displaystyle e_i=\frac{e_j+e_k+e_l}{3} + 1$ で求められる。
,---------------,
1 ------ 2 ------ 3 ------ 4
`---------------' |
`------------------------'
ei 11/6 3/2 1 0
$e_1$ が通路を消さない場合の期待値となる。計算量は辺数に依存し、$O(M)$ となる。
部屋 $i$ から出る通路を消すと決め、消さない場合からの削減量を考える。
まず、出路が1本しか無い部屋の通路は消せないので、飛ばしてそれ以外を考える。
通路を消して期待値を下げるということは、 残り通路数期待値（$e$）の多い部屋へ繋がる通路を消し、 少ない部屋へ向かう確率を上げるということである。
なので最も効率的なのは、$i$ から出る通路の内、次の部屋の $e$ が最大の部屋への通路を消すことである。
,---------------,
1 ------ 2 ------ 3 ------ 4
`---------------' |
`------------------------'
ei 3/2 1 0
この場合、1からは2,3,4へ行けるが、2へ繋がる通路を消すのが効果的
通路を消した場合の $e_i$ に相当する期待値を $e'_i$ とし、次の部屋を $j,k,l$ とすると、以下のようになる。
$\displaystyle e'_i = \frac{e_j+e_k+e_l - \max(e_j,e_k,e_l)}{3 - 1} + 1$
これと $e_i$ との差分 $d_i = e_i - e'_i$ が、「$i$ を出発し $N$ までに通る通路数の期待値を、 通路を1つ消すことによって削減できる量」ということになる。
では、これが全体（1を出発した場合）に対してどれだけ効いてくるかというと、 1を出発して $i$ を経由する確率を $p_i$ とすると、$p_i \times d_i$ で求められる。
よって、各部屋に至る確率 $p_i$ を求める。こちらは先頭からのdpで求められる。
$p_id_i$ の最大値が、最も効果の高い通路を消した際の削減量であり、 これを通路を消さない場合の期待値 $e_1$ より引いた結果が答えとなる。
import sys
n, m = map(int, input().split())
links = [set() for _ in range(n)]
counts = [0] * n
for line in sys.stdin:
s, t = map(int, line.split())
s -= 1
t -= 1
links[s].add(t)
counts[s] += 1
# Expected number of edges passing from i to N
expected = [0.] * n
exp_get = expected.__getitem__
# i から伸びる辺を1本消すことで削減できる"iからNまでの辺数の期待値"の最大量
reducible = [0.] * n
for i in range(n - 2, -1, -1):
nxt_exp = list(map(exp_get, links[i]))
sum_exp = sum(nxt_exp)
cnt = counts[i]
expected[i] = sum_exp / cnt + 1
if cnt > 1:
reduced_exp = (sum_exp - max(nxt_exp)) / (cnt - 1) + 1
reducible[i] = expected[i] - reduced_exp
else:
reducible[i] = 0.
# Probability of visiting i when starting from 1
probability = [0.] * n
probability[0] = 1.
for i in range(n - 1):
jp = probability[i] / counts[i]
for j in links[i]:
probability[j] += jp
print(expected[0] - max(p * r for p, r in zip(probability, reducible)))