PAST007L 参考にした実装 https://blog.hamayanhamayan.com/entry/2021/07/24/203450 全ての \(j\) を求めるとあるが，まずは \(1\) 個求める． 特に，最小の \(j_{0}\) を求められれば， \(j_{0}+1\) 以降の中から 最小の \(j_{1}\) を求めることができる．…

PAST007J 有向グラフのサイクル検出トポロジカルソートと同じ．DFS,BFSでも可能．DFSによる実装頂点 \(i\) に対して， \(val_{i}\) を 0 : 訪れてない 1 : 訪れたが計算途中 2 : 訪れて計算が終わった として保持する． \(val_{i} = 1\) の状態で再び訪れた…

PAST007G 3冪の和で表すので，3進数の形から考える． 今回は，同じ3冪は使えないので， $$2 * 3^{i} = 3^{i+1} - 3^{i}$$ と書き直せばよい． 繰り上がりの様な計算が起きるので，下の桁から計算を確定させていく．メモこの問題は， 平衡3進法という問題らし…

PAST007I 複素数回転と平行移動のみなので，複素数による実装が簡単．実装右目と左目を区別することに注意． よって，平行移動と回転は一意に定まる．操作後の点たちを，平行移動 -> 回転 の順で求める． 平行移動を忘れずに． 使っている記号，マクロ等 "ht…

PAST007K まず min cost, 次に max scenery. また，コストは全て正． 答えは，min cost となるパス \(1 \rightarrow N\) 全体から max scenery をとる．これは Dijikstra を (cost, -scenery ) で昇順ソートの priority_queue で行えば良い． 使っている記号…

PAST008H LCAの前計算で高速化可能だが， 頂点毎にDFSをやりなおしても \( O(N^2) \) で間に合う．Tree においては，根からDFSしたときの距離が，根からの最短距離になる． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131…

PAST008J 反転するペアは独立しているのがポイント． \(mod 2\) で区間和を求めればよい． これは segtree で実装できる． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" ll op(ll a, ll b){ return a+b; } ll e() {…