みんなのプロコン 決勝 2019 A - Affiches

A - Affiches

問題概要

H×W の大きな紙 1 枚と，A×B の小さな紙 2 枚がある． 小さな紙 2 枚を大きな紙の上にはみ出さないように貼る．このとき，小さな紙同士が重なっていても構わない． 小さな紙の左上の座標が [0, H-A]×[0, W-B] 上の独立な一様分布に従うとしたとき，小さな紙同士が重なった面積の期待値を求めよ．

解法概要

小さな紙の左上の座標が [0, H-A]×[0, W-B] 上の独立な一様分布に従うとあるので，縦と横はそれぞれ独立に考えてあとから掛け合わせれば良い． したがって，(重なった部分の縦の長さの期待値) × (重なった部分の横の長さの期待値) を求めたい．

縦の長さのみについて考える． 重なった部分の縦の長さの期待値は，(考えうるすべての場合の「重なった部分の縦の長さ」の和) / (H-A)² で求められる． 小さな紙の左上の座標値は整数とは限らないため，(考えうるすべての場合の「重なった部分の縦の長さ」の和) の部分を頑張って積分で計算する． 例えば，私の場合は次のような計算した．初めから 1 枚目と 2 枚目のどちらの座標が大きい場合にも対応するのではなく，まずは 1 枚目の座標が 2 枚目の座標以下だと仮定して積分を求め，後からそれを 2 枚して (考えうるすべての場合の「重なった部分の縦の長さ」の和) を求めている．

ソースコード

いつもの C++ ではなく，なぜか Python．

def f(H, A, a):
    return (-a**3/3 + (H-2*A)*a**2-(H-A)*(H-3*A)*a) / 2

def calc(H, A):
  ret = f(H, A, H-A)
  if H-2*A > 0:
    ret -= f(H, A, H-2*A)
    ret += A**2 * (H-2*A) / 2
  return 2*ret / (H-A)**2

H,W,A,B = map(float, input().split())

ans = calc(H, A) * calc(W, B)
print(ans)

所感

積分の計算が苦手なのに慢心してミスしまくってしんどかった