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\) となるもののうち 最大となる様にとる． これは，前処理で …

ABC192F 簡単な問題から考える． 取り方 \(s \in 2^{N}\) を固定 \(t := sum(s)\) とおく． \(s\) に対する答えは， \(x-t \equiv 0 \ mod \ |s|\) のとき \(\frac{x-t}{|s|}\) となる． それ以外のときは不可能． 取った個数 \(k \in [1,N]\) を固定 これも…

ABC306F \(\def\cnt #1{\lvert {#1} \rvert}\) 解法 \(A,B\) を集合，\(A \cap B = \emptyset\) とする． 集合 \(C\) に対して，\(x\) 以下の元全体を \(C^{\leq x}\) とおく． \begin{align} f_{A,B} &= \sum_{x \in A} \cnt{A \cup B}^{\leq x} \\ &= \sum…

ABC276F 部分問題 \(a\) を size \(N\) の vector， \(i \in N\) とする． \(a_{[0,i)}\) において， \(a_{i}\) 未満の個数と \(a_{i}\) 以上の和が分かれば十分． これらは segtree で実装可能． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.co…

ABC275F 解法 \(a_{i}\) を残すとき 0, 消すとき 1 として，01 列を考える． 1 が連続している区間の個数を最小化する問題となる． 区間を数える代わりに，[01] の並びを数えると考えるとよい． [11], [00], [10] は数えないとする． つまり，01 列において …

ABC309F 解法 平面走査． 2次元 segtree は，1次元を 2方向にとる． まず回転が 6通りあるが，これは直方体のどの面を一番下にするかが 6通りあって， それらに 1対1 対応する． つまり，回転するということは，自由に辺の長さを並び変えることに対応する． …

ABC271F 解法 半分全列挙． 最短ルートで移動したとき，右上から左下の対角線 \(l\) を一度だけ通る． \(l\) で正方形を 2分割して，それぞれで計算した結果をつなげる． 左上から \(l\) への移動方法は，雑に見積もって \(2^{n}\)通り． 点 \(\,(x,y\,)\) …

ABC270F 超頂点を用いる． \(a,b\) が空港同士とする． \(a,b\) を直接結ぶのではなく，超頂点 \(\tilde{v}\) を経由して， \(a\) - \(\tilde{v}\) - \(b\) とする． これにより， 頂点 \(a,b\) が空港であるという情報を 辺に移すことができた ので， 連結…

ABC269F 解法0 左上基準で長方形を調べる． 解法1 \(1\)-indexed で考える． 市松模様をさらに2種類に分ける． \(a,c\) の偶奇で場合分けしていくが， まずは簡単のため \(a,c\) が共に奇数の場合だけ考える． 等差数列の和の公式を使えばよい． 使っている…