2021-06-01から1ヶ月間の記事一覧
rerooting DP、rerooting をする DP、DP with rerooting とかなら別によさそう。 全方位木 DP 自体を指して「rerooting」と言われると気になります。 rerooting は木の根を変える操作(全方位木の中で考えられる)を指していて、全方位木 DP 自体のことを指…
インタラクティブ問題は手元でのデバッグが面倒がちなので、いやだと思っている人が多そうです。 coproc というシェルの機能を使えばそこそこ簡単にできないかな?と思ったので、書いてみます。 まえおき 簡単とは言っても、以下のものは自分で書く or 生成…
part 1 以降があるかはわかりません。 導入? 競プロで、「絶対誤差または相対誤差が \(10^{-6}\) 以下ならば正解と判定される」といった文言はちょくちょく見かけます。 思い出すシリーズ \(2e-3\) atcoder.jp 思ひでポロポロ pic.twitter.com/64N0Qk3SbX— …
「bitset で 64 倍高速化できます」「64 は定数なのでオーダーは変わりません」のような説明は、競プロ界隈でたびたび見かけます。 59 日目の解説です。std::bitset などを使った高速化テクニックは過去に AGC にも出題されたことがある重要事項ですので、理…
\(n\) 以下の素数の個数を求める関数 \(\pi(n)\) を持っていたとします。 このとき、\(n\) の素数判定は \(\pi(n)-\pi(n-1) = 1\) かどうかでできます。 fn is_prime(n: usize) -> bool { n > 0 && prime_pi(n) - prime_pi(n - 1) == 1 } たとえば \(O(n^{3/…