ABC273E 永続データ構造．Vector \(a\) 自身でなく，\(a\) の編集履歴を保存しておき， 履歴におけるタイミングに跳ぶことで復元する．今回は tree \(T\) を永続データ構造としてもつ． 出力クエリ必要な情報は，\(a\) の末端．これは \(T\) における頂点 \(…

ABC280E 普通にDPをしても \(O(N)\) で間に合う． 今回は遷移が線形なので，行列冪乗で遷移を計算すれば \(O(log N)\)． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" template<typename T> using M = vector<vector<T>>; template<typename T> M<T> oper</t></typename></vector<t></typename>…

ABC279E \(0\)-indexed で考える． \(j \in M\) 番目を除いたものは， \([0,j) \) と \([j+1, M)\) に分解すると便利． 累積和などでも使われるが，今回も同様にできる．あみだくじの上の方は，\(0\) の場所だけで十分． 下の方は，\([0, N)\) のすべての位…

e ABC275E ちょうど \(i \in K+1\) 回で \(j \in N+1\) に居る確率を DP で求める． どの様な手順でその局面に至ったかは，今後に影響しないので， 状態をまとめることが出来てDP可能．遷移に \(O(M)\)． 使っている記号，マクロ等 "https://ecsmtlir.hatena…

ABC274_E 状態ブースターは，取る順序は無関係． よって，どれを取ったかの情報だけで済むので，\(2^{M}\)．頂点も，訪れた順序は無関係で， どれを訪れたかの情報だけで十分なので，\(2^{N}\)． 原点を含めて，\(2^{N+M+1}\) ． 遷移今の頂点と次の頂点を用…

ABC308 問題の本質から攻めるのが王道． 商品の個数は重要ではなく，大事なのはクーポン． まずはクーポンを全探索する方針で考える． つまり，クーポンを 1枚固定して考える．払う値段は， \begin{align} & \sum_{i \in N} (p_{i} - c_{i}d_{i} )\\ = & \su…

ABC308E 動く物が 3つある場合， 真ん中を全探索する のは典型．\(E\) の場所を全探索して，\(M\) と \(X\) の場所を考える． \(M,X\) それぞれの値に対して，それが何個取り方があるのかを数える． 用意したいもの：\(i \in N\) が与えられたとき， \([0,i)…

文字列 snuke の中に，同じ文字は使われていない． よって，同じマスを通る必要はない． DFS で実装可能． 一般化:もし，文字列 snuke の代わりに，同じ文字が現れる文字列 \(S\) の場合． 訪れたかどうかを，\(x \in H, y \in W, i \in Length(S)\) に対し…