問題はこちらです atcoder.jp 周期性を使った解説が多いので、ダブリングを使って解いていきます。 自力でACできなかったのでこちらの記事を参考にしました。 drken1215.hatenablog.com 遷移後の値を管理する配列と、操作後の総和を管理する配列の2つを用意…

問題はこちらです atcoder.jp この問題は典型的なbitDPで解けます。 以下の解説は都市を0-indexで扱うため、例えば都市１->都市０としています。 ここで、S := 訪れた都市の集合。2進数に変換したとき 1 の都市を訪れている と定義します。 例えば、のときは…

問題はこちらです。 atcoder.jp Pythonでセグ木を使う解法記事がないので書いておきます。 まず、セグ木でAに0~N+1がそれぞれ登場する回数を管理します。 クエリが飛んできた時には、のセグ木上の登場回数1へらし、xを1増やします。（実装ではupdateメソッド…

AHC030のベイズ推定を使う解法をPythonでやってみます。 以下の記事を参考にさせていただきました。 qiita.com M=2のときの配置推定 まずはM=2のときの配置推定（ベイズの定理）からやってみます。 ベイズの定理の細かい内容は飛ばします。（僕もお気持ち程…

問題はこちらです atcoder.jp 全列挙が間に合いそうなので、考えられる文字列を全列挙します。 全列挙にはDFSを使います（典型ですね）。 Sの並び替えはpermutationsを使い、"_"の追加をDFSでやります。 実装して以下のコードを提出してみます。 import sys,…