kmjp's blog

競技プログラミング参加記です

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

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);
}

まとめ

積分が出るのは珍しいな。