Codeforces Round #456 (Div. 2) D. Fishes
問題リンク
codeforces.com
問題概要
n*mのグリッドが与えられる. ここにk匹の魚を配置する(各グリッドに高々1匹). このときグリッド上で等確率でr*rの正方形を指定したとき, 魚の個数の期待値を最大化したい. この値を求める.
制約
解法
任意の魚について, 現れる回数の総和を最大化したいので, r*rのグリッドの重複が大きい順にk個取る問題と言い換えることができる.
重複数は場合分けをすることでO(1)で求められるので, 始点を(n/2, m/2)としてPriority_queueを使って大きい順に取っていけばよい.
