A~Dまでは自力で解けた。
https://atcoder.jp/contests/yahoo-procon2019-final-open/tasks/yahoo_procon2019_final_a
問題
H*Wの長方形の敷地の上に、A*Bの紙を2枚辺を敷地に平行にする形で配置する。
その際、回転は行えない。また、あり得る位置にはそれぞれ等確率で配置される。
両者の共通部分の面積の期待値を求めよ。
解法
高さ方向と幅方向それぞれで共通部分の長さの期待値を求め、その積を取ればよい。
よって以下前者のみ、すなわち[0,H]の1次元の区間に長さAの領域を2つ配置するときの共通部分の長さを求めよう。
f(x) := 位置xを両領域が覆う確率
とすると、f(x)を[0,H]の区間で積分すればよい。
f(x)は[0,H]の間で対称な値を取ることを考慮するとわかりやすくなる。
- 2*A≧Hの場合
- x≦H/2のケースを考えると、両領域の左端がx以下ならよいのでf(x) = (x/(H-A))^2となる。
- 2*A<Hの場合
- x≦Aのケースは、上記と同様にf(x) = (x/(H-A))^2となる。
- A<x<H-Aの場合、f(x)=(A/(H-A))^2となる。
上記式は簡単な多項式なので、積分も解析的に求められる。
int H,W,A,B; double hoge(int X,int Y) { double D=X-Y; if(Y*2>=X) { return (X-2*D)+2*D/3.0; } else { return (X-2*Y+2*Y/3.0)*Y*Y/D/D; } } void solve() { int i,j,k,l,r,x,y; string s; cin>>H>>W>>A>>B; double ret=hoge(H,A)*hoge(W,B); _P("%.12lf\n",ret); }
まとめ
積分が出るのは珍しいな。