自己ループを除く
確率や期待値を計算する DP をするときは、自己ループを除去することが多いね。 問題へのリンク 「EDPC J - ボール」などは類題と言える。先にこの問題を解いておくと、今回の問題も解きやすいかもしれない! qiita.com 問題概要 以上 以下の整数が等確率で…
AOJ
JAG
AOJ-ICPC600点
期待値
ランダムウォーク
期待値DP
DP
連立一次方程式
行列
方程式
最適化テク:解に確実に含まれる要素を列挙する
グラフ
最短路問題
Dijkstra法
前処理
自己ループを除く
AOJ-ICPC
JAG夏合宿
そのまま覚えたいシンプル設定の中堅以上の典型問題
回数の期待値
Gauss-Jordanの掃き出し法
浮動小数点型を扱う問題
ランダムウォークな問題! 実数係数の連立方程式の練習に 問題へのリンク 問題概要 頂点の重み付き無向グラフが与えられる。ただし自己ループを含み得る (多重辺はない)。二頂点 が指定されていて、 から へとランダムウォークによって辿り着きたい。 ただし…
自己ループを除く
期待値
期待値DP
DP
包除原理
bitDP
累積和
DP高速化
DP高速化:累積和
高速ゼータ変換
主客転倒
テク:K以上からK+1以上を引く
O(3^N)
TopCoder
SRMDIV1Medium
無限級数
回数の期待値
楽しい!!!!!!!!!すごく勉強になったん!!!!! 大きく 2 つのやり方があって、高速ゼータ変換を用いた O(3n) から O(n2n) への高速化や、期待値に関する重要な考察をするなど色々やれるん。 問題概要 人がテストを行う。 毎秒ごとに 番目の人がテ…