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

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

期待値の線型性

Codeforces 553 DIV2 E. Number of Components (R2100)

面白かった。 「全体についての総和についての総和」を「個別の要素についての総和を各要素について総和」とするテク 区間の連結成分の個数は、各隙間に左端が入り込むかを数える という典型テクが詰まった問題。 問題へのリンク 問題概要 要素からなる数列 …

Codeforces 551 DIV2 F - Serval and Bonus Problem (R2800)

こういうのに慣れて行きたい。 問題へのリンク 問題概要 長さ の線分上に、ランダムな区間を 個とったときの、区間が 本以上重なっている部分の長さの期待値を求めよ (998244353 で割った余りの形式で)。 なお、区間のランダムな選び方とは、線分から 2 点ず…

キーエンス プログラミング コンテスト 2019 F - Paper Cutting (900 点)

このシンプル設定でこの深み...すごい!!! や は順列や組合せを表すものとする。 問題へのリンク 問題概要 長方形の紙があって、水平方向の切れ線が 箇所、垂直方向の切れ線が 箇所ある。 箇所の切れ線から 箇所選んで順に切って行く 通りの方法それぞれに…