ABC297 F - Minimum Bounding Box 2 (500)
コンテスト中の考察
各長方形に$ K個含まれる確率をメモ化再帰でより小さい範囲から求めたかった
分割した際に重複して数えてしまうのを防げなかった
解説の解法
各マスが含まれることになる個数を求めて最後に全体の数で割る
この個数は全体からの選び方からその点の上、下、左、右からのみ$ K個選んだ場合を引いた数
これだと左上、右上、左下、右下からのみ$ K個選んだ場合の数が二重に引かれるのでここの分を再度足す
問題: https://atcoder.jp/contests/abc297/tasks/abc297_f
提出: https://atcoder.jp/contests/abc297/submissions/40495540
#ABC297 #500pt #F #ABC #AtCoder
#主客転倒 #期待値