公式解説の読解に5000兆年かかったので、記号や論理の展開の仕方を全て俺好みに書き換えたものを記す。 オリジナル：Editorial - Monoxer Programming Contest 2022（AtCoder Beginner Contest 249） 数列 に対して、終了条件を満たすまでの操作回数の期待値…

これの続き sugarknri.hatenablog.com201 DP202 前座パートは中受典型 No.306 さいたま2008 - yukicoder 本編前半は3種類の直線をZ[ω]座標系で書いて考える 本編後半は素因数分解してDPなり包除原理なり203 やるだけ クンマーの定理を思い出してもいい204 O(…

これの続き sugarknri.hatenablog.com「DPの状態数が少ないので行列累乗や高速きたまさ法で計算量落ちまーす」の類は実りがないので以降言及しません。151 DP152 1/kpを使ったら、pがどこかで約分される必要があります バックトラックDFSで全探索 指数でも分…

これの続き sugarknri.hatenablog.com101 ラグランジュ補間 普通にやるとO(N^3) 補間に使う点が等差数列なのでO(N^2)にできる ラグランジュ補間したときの係数をぐっと睨むと求めるものをexplicitにも書ける102 多角形の内外判定 普通は半直線と線分の交差判…