DP高速化:累積和
DP
DP高速化
DP高速化:累積和
累積和
数え上げ問題
区間分割型シーケンシャルDP
シーケンシャルDP
体力や燃料がある一定以上必要になる設定の問題
unrated公式コン
AtCoder
AtCoder700点
数直線上のN点の問題
二分探索:lower_bound
点が移動していく問題
解空間:O(2^N)通りの選択肢
区間分割の仕方を走査する問題
DP状態:前回の最後の場所
ひたすらバグってつらかった。。。DP 高速化系。セグ木を使ってもいいが、累積和だけで解ける。 問題へのリンク 問題概要 座標 地点から座標 地点へと移動する。 移動途中に 個のガソリンスタンドがあって、それらの座標は で与えられる。 燃料 の状態でスタ…
自己ループを除く
期待値
期待値DP
DP
包除原理
bitDP
累積和
DP高速化
DP高速化:累積和
高速ゼータ変換
考察：主客転倒・寄与分解
K以上からK+1以上を引く
O(3^N)
TopCoder
SRMDIV1Medium
無限級数
回数の期待値
楽しい！！！！！！！！！すごく勉強になったん！！！！！ 大きく 2 つのやり方があって、高速ゼータ変換を用いた O(3n) から O(n2n) への高速化や、期待値に関する重要な考察をするなど色々やれるん。 問題概要 人がテストを行う。 毎秒ごとに 番目の人がテ…
