ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

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

A - Affiches

オンサイトで解けなかった問題…ザ・数学。

解法

公式解説と少し違う方法で考えたので、その解法を書きます。

大きな長方形の中にある1点  (h, w) を考えます。この点が2つの小さな長方形両方に入っている確率を考えます。

f:id:betrue12:20190225222409p:plain

小さな長方形の置き方は1枚目と2枚目では独立に、そして縦座標と横座標でも独立に考えることが出来ます。縦座標  h が長方形1つの縦座標に含まれる確率を  f(h), 横座標  w が長方形1つの横座標に含まれる確率を  g(w) とすると、点  (h, w) が2つの小さな長方形両方に含まれている確率は  f(h)^{2} g(w)^{2} になります。これを大きな長方形の領域全体で積分すると答えを求めることが出来ます。

ここで積分の式は分離することが出来て、大きな長方形の領域全体を  D とすると

 \iint_{D} f(h)^{2} g(w)^{2} dhdw = (\int_{0}^{H} f(h)^{2} dh) \times (\int_{0}^{W} g(w)^{2} dw)

と縦横それぞれの積分の掛け算で答えを求めることが出来ます。(左辺は重積分で書いていますが、あまり気にしなくてもいいです)

あとは具体的に  f(h) などの値を計算して積分をします。  f(h) がどのようなグラフになるかを調べるため、 2A H の大小関係で場合分けします。(縦座標と言いつつ横向きになっていますが気にしないでください…)

f:id:betrue12:20190225221044p:plain

f:id:betrue12:20190225221107p:plain

場合分けをしたものの、両者のグラフの形は全く同じ形をしています。両端に近づくと確率が低くなる台形状です。

実際、 a = \min(A, H-A) とおくとこれはどちらも

  •  0 \le h \le a のとき  f(h) = \frac{h}{H-A}
  •  a \le h \le H-a のとき  f(h) = \frac{a}{H-A}
  •  H-a \le h \le H のとき  f(h) = \frac{h}{H-A}

という同じ式で表すことが出来ます。それぞれの区間で2乗を積分して合計すると

 \int_{0}^{H} f(h)^{2} dh = \frac{1}{(H-A)^{2}} \times (\frac{1}{3} a^{3} + (H-2a)a^{2} + \frac{1}{3} a^{3})

という式が得られます。

 w についての積分も全く同様に計算することができるので、それぞれ計算して掛け算すると答えを求めることが出来ます。

ACコード

Submission #4354095 - 「みんなのプロコン 2019」決勝

まあ、数式をコードにしてるだけですね…。これを本番解けなかったのは悔いが残ります。