ABC142F 解法 Sub 0: 有向グラフにおける，サイクルを求める． Sub 1: 有向グラフにおける，最短サイクルを求める． Sub 0: サイクルを検出するだけなら，DFS, BFS で可能． Sub 1: 最短のサイクルを求めたいので，BFS を行う． 計算量的には，始点 \(i \in …

ABC165F 解法 Sub: LIS(line 型) Main: LIS(Tree 型) Line 型の LIS が解けていれば，それを tree 型にするのは容易． DP 配列を DFS で使い和ます． 注意は，遷移から戻るときに DP 配列を元に戻すこと． 使っている記号，マクロ等 "https://ecsmtlir.haten…

ABC170F 解法 いくつか解法があるが， ダイクストラで解く． コストが \(\frac{1}{k}\) として， 向きを変えたときまたはゴールしたときに，小数点以下の切り上げをする． 少数だと扱いにくいので，コストを \(1\) にして，\(k\) の倍数に切り上げる． 使っ…

ABC173F 解法 \(0\)-indexed, 半開区間で考える． 森の誘導部分グラフは森になる． よって， グラフ \(G\) が森のとき， (\(G\)の connected component の個数) = \(|V(G)| - |E(G)|\) となる． 頂点集合が区間 \([l,r)\) となる \(G\) の誘導部分グラフの …

ABC184F 解法 半分全列挙． \(a\) を半分に分けて，それぞれの和を集めておき， その vector を \(v_{0}, v_{1}\) とする． \(x \in v_{0}\) を全探索して， \(y \in v_{1}\) を，\(x + y \leq t\) となるもののうち 最大となる様にとる． これは，前処理で …