ABC188F 操作の逆を考える． \(f(y) := y / 2 \ (\text{if}\ y \equiv 0 \ mod \ 2)\), \(g_{+}(y) := y + 1\), \(g_{-}(y) := y - 1\). これらの操作で \(Y\) から \(X\) を作ることを考える． 操作 \(f\) のおかげで，小さくしていくので計算量の見積りも…

ABC190E Tree におけるクエリ． まとめて処理することで回数を減らす，いつものやつ． Subtree に関する処理を，補題の様に扱えばよい． Subtree の root \(r\) を指定したとき，\(r\) の値を subtree 全体に伝搬させる． 使っている記号，マクロ等 "https:/…

ABC190E グラフの問題． ハミルトン閉路に近い． 大事な頂点が \(K \leq 17\) と少ない． 訪れた頂点を再び使う可能性はある． すべての大事な頂点を 1回以上使う． 訪れた頂点の集合と，最後に訪れた頂点を保持しながら dp. 大事な頂点間のコストは，BFS と…

ABC191E ダイクストラ． サイクルを含んでいるので注意． サイクルだけ別に管理してしまうと楽． 始点を \(s \in N\) とする良い path を考えると， [\(s \rightarrow s\) のループを使う path] または， [\(s \rightarrow i \rightarrow s\) かつ \(i \neq …

ABC192E コストが特殊な Dijikstra. 時刻を距離の代わりとして保持しておき， 時刻が \(k\) の倍数になるまで待機してから移動すればよい． 現時点の後ろの，一番近い \(k\) の倍数で移動するのが最善． 使っている記号，マクロ等 "https://ecsmtlir.hatenab…