けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

みんなのプロコン 2019 決勝 A - Affiches (500 点)

AtCoder AtCoder500点 unrated公式コン 積分 式変形 期待値 Greedy:各要素について独立に考えてよい 競技数学色強め 連続量問題 総和を求める 図形的量の期待値 x軸とy軸について独立に考えてよい 浮動小数点型を扱う問題

積分した

問題へのリンク

問題概要

サイズ H, W の長方形の紙と、それよりサイズの小さいサイズ A, B の長方形の紙が 2 枚あります。

2 枚の小さいサイズの紙を、それぞれ、大きいサイズの紙の中に包含される範囲内でランダムに配置します (その位置は連続量)。

このとき、2 枚の小さい長方形の重なりの面積の期待値を求めよ。

制約

  • 1 \le A < H \le 100
  • 1 \le B < W \le 100

解法 1: 積分

最初、連続量だと思わなくてアレ！？となってた。

さて、今回は長方形の重なった部分の縦方向の長さを表す確率変数を X、横方向の長さを表す確率変数を Y として E[XY] を求める問題になる。 X と Y とが独立なので実は

E [ XY ] = E [ X ] E [ Y ]

が成立する。 E [ X + Y ] = E [ X ] + E [ Y ]は X, Y が独立でなくても成立するが、 E [ XY ] = E [ X ] E [ Y ] は独立の場合に成立する。

よって E [ X ] が計算できればよくて、これを期待値の定義に従って計算することにする。これは

長さ H の区間に、長さ A の区間を 2 本ランダムに配置したときの、重なりの長さの期待値

を求める問題である。重なりの長さが x になる場合の確率密度関数を f(x) としてこれを求める。

重なった区間をまとめて 1 つの長さ 2A - x の区間とみなすことができて (ただしどちらの区間が左にあるかの違いがあるので 2 倍する)、この区間の動ける範囲の長さは

H - (2A - x)

になる。これに対して元々の区間が動ける範囲はそれぞれ H - A なので

f(x) = \frac{2(H - 2A + x)}{(H - A)^{2}}

となる。 x のとりうる範囲は

\max(0, 2A - H) 〜 A

となる。ここで K = \max(0, 2A - H) とおいておく。こうして求める期待値は

E [ X ] = \int_{K}^{A} x\frac{2(H - 2A + x)}{(H - A)^{2}} dx
= \frac{2}{(H-A)^{2}} (\frac{A^{3}-K^{3}}{3} + \frac{(H-2A)(A^{2}-K^{2})}{2})

となる。

#include <iostream>
#include <iomanip>
using namespace std;

double L[2], S[2];

int main() {
    cin >> L[0] >> L[1] >> S[0] >> S[1];
    double res = 1;
    for (int iter = 0; iter < 2; ++iter) {
        double H = L[iter], A = S[iter], K = max(0.0, A*2-H);
        double tmp = ( (A*A*A - K*K*K)/3 + (H-A*2)*(A*A - K*K)/2 ) * 2 / (H-A) / (H-A);
        res *= tmp;
    }
    cout << fixed << setprecision(10) << res << endl;
}

解法 2: 三角錐と三角柱

こんな感じで積分計算を頑張ったけど、積分しなくても図形的に導出できる。

2 本の長さ A の区間の開始位置を x 軸と y 軸にとり、重なりの大きさを z 軸にとってグラフを描くと、

  • 大きい三角錐から小さい三角錐を切り取ったもの
  • 大きい三角柱から小さい三角柱を切り取ったもの

を合わせたものになる。この体積を求めて高さを平均したものが答えである (底面積で割ればよい)。