baitop https://blog.hatena.ne.jp/baitop/ バイトの競プロメモ https://baitop.hatenadiary.jp/ http://codeforces.com/contest/1153/problem/F 問題 区間[0,L]で、N個のランダムな区間が作られる。 K個以上の区間で覆われる区間の長さの期待値を求めろ。 解法 区間のうち、左端の点をl,右端の点をrと呼ぶ ここでl,rをN個ずつ決めた時、どのl,rを結んでも、領域の重なり方は同じになる。 よって、具体的な区間は考えず、LRとして使う頂点だけ考えればいい。 また、N個ずつLとRを置いた時、全体は2*N+1個に分割されますが、期待値の計算であるためそれらは等分されてると考えて良いです。 よって全てのL,Rの取り方について、2 * N+1個の区間のうち… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbaitop.hatenadiary.jp%2Fentry%2F2019%2F10%2F21%2F135249" title="Codeforces 551 Div2 F. Serval and Bonus Problem - バイトの競プロメモ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/b/baitop/20191021/20191021131918.png Hatena Blog https://hatena.blog 2019-10-21 13:52:49 rich https://baitop.hatenadiary.jp/entry/2019/10/21/135249 1.0 100%