【今日の精進】ARC114E - Paper Cutting 2

毎日格上の問題を倒すやつの8日目です。

問題リンク

atcoder.jp

問題概要

2つの点が描かれた紙があるよ。

マスの境界にある線をランダムに選んで切ることを2つの点が分かれるまで行うとき、回数の期待値を答えてね。

解法

「操作が終わるまでにこの線を切る確率」をすべての線に関して足せば期待値になります。¹

切ったら死ぬ線は、それぞれ確率が になります。

それ以外の線は、それぞれ確率は になります。

これらをすべての線に対して計算して足し合わせれば終わりです。

提出コード

MOD=998244353
H,W=map(int,input().split())
h1,w1,h2,w2=map(int,input().split())
if h1>h2:
    h1,h2=h2,h1
if w1>w2:
    w1,w2=w2,w1
frac=[None]
for i in range(1,H+W):
    frac.append(pow(i,-1,MOD))
ans=0
for i in range(1,H):
    if h1<=i<h2:
        ans+=frac[(h2-h1)+(w2-w1)]
    elif i<h1:
        ans+=frac[(h1-i)+(h2-h1)+(w2-w1)]
    else:
        ans+=frac[(i-h2+1)+(h2-h1)+(w2-w1)]
    ans%=MOD
for i in range(1,W):
    if w1<=i<w2:
        ans+=frac[(h2-h1)+(w2-w1)]
    elif i<w1:
        ans+=frac[(w1-i)+(h2-h1)+(w2-w1)]
    else:
        ans+=frac[(i-w2+1)+(h2-h1)+(w2-w1)]
    ans%=MOD
print(ans)

Submission #46001402 - AtCoder Regular Contest 114

感想

ARC-Eにしては簡単な期待値の遊びでした。

---

1. 期待値の線形性とやら↩