回数の期待値=(k回以上の確率)の和
回数の期待値
回数の期待値=(k回以上の確率)の和
期待値
数列
二分木のような計算順序
分割統治法
FFT
分割統治FFT
高速畳み込み計算
多項式・FPS(形式的冪級数)
数学(代数)
中堅以上の典型要素を詰め合わせた教育的問題
高度典型
NoviSteps3D
AtCoder
AtCoder600点
橙色diff
ABC-G
K以上からK+1以上を引く
「回数の期待値」は、(k 回以上の確率) の総和に一致する！！ あとは有名な「 個の一次関数の積は二分木のような計算順序で の計算量で求められるという話！ 問題へのリンク 問題概要 色が であるような靴下が 枚ずつある。いずれも 2 種類以上ある。 これら…
Codeforces
数え上げ問題
期待値
期待値DP
K以上からK+1以上を引く
考察：主客転倒・寄与分解
約数系包除
最大公約数
考察：操作・条件・目的関数を言い換える
包除原理
式変形
無限級数
エラトステネスの篩
回数の期待値
高速メビウス変換
CodeforcesDIV2
CodeforcesR2300
メビウス関数
回数の期待値=(k回以上の確率)の和
これだった！！！ drken1215.hatenablog.com もちろん高速ゼータ変換はいらなくて、愚直な包除原理で間に合う。 問題概要 整数 が与えられる。空の vector があって 以上 以下の整数の中から一様ランダムに 1 つ選び、 それを vector に push する このとき …
0. プロローグ 期待値にまつわる有名事実として、以下のことが一般によく知られていて、競プロでも過去何度も出題例がある！！！ 確率 で成功する試行を成功するまで続けたとき、成功するまでの回数の期待値は である 個の品物がランダムに出力されるコンプ…
AtCoder
ABC-C
AtCoder300点
期待値
確率
回数の期待値
茶色diff
ARC-C
入力が定数個
競技数学色強め
式変形
典型要素を詰め合わせた教育的問題
テーマにストーリー性のある面白い問題
K以上からK+1以上を引く
回数の期待値=(k回以上の確率)の和
NoviSteps3Q
期待値に関するセンスがちょっと求められる問題 問題へのリンク 問題概要 高橋君はテストケースが ケースある Yes/No 判定問題に対して、ソースコードを提出したところ 問で TLE して、残りの 問は正解しました。 そこで「 問については 100ms で正解し、残…
