F ABC391F 解法 priority queue を用いて解く． 実際に候補を列挙していけばよい． 重複した \(\ (i,j,k)\ \) の組を調べないために，used 変数を用意しても良いが，別の解決策がある． Path が一意に定まれば良いので， \(j\) の遷移は \(i = 0\) のときの…

ABC357E 問題概要 Functional graph において，サイクル部分と tree 部分を求める． 解法 Cycle 部分と tree 部分を分けて処理する方がミスが少ない． Tree 部分は，元のグラフの反転を考えれば dp 出来る． Cycle 部分は，cycle の長さを求める．これは DFS…

ABC369E 解法 簡単のため，\(K\) が 1のときを考える． 辺 \(e = (a,b)\) を経由して \(s\) から \(t\) に行く場合， \(s \rightarrow a \xrightarrow{e} b \rightarrow t\) というルートを通れば良い．つまり，cost[s][a], cost[b][t] が分かれば十分で，こ…

問題概要 ABC401E 解法 最初に判定問題を考える． \(1, \cdots , k\) 以外の頂点を全て消したとき，接続されていることが必要十分． これは， \(k\) について昇順に頂点を追加していき，小さい番号に向かう辺だけ追加すれば， 頂点 \(1, \cdots, k\) からな…

問題概要 slide-min. 解法 deque の中は，次を満たす． assending order で index がはいっている． a_{deque} も assending order. 右端を全探索する．\(a\) は綺麗な形とは限らないので全探索する． front の pop を行わなければ，先頭からの min と一致．…

問題概要 Largest Rectangle in a Histgram 解法 stack の中には，descending order で入っている． \(h_{stack}\) も descending order． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll n; cin >> …

解法 \(\sum_{b \in n} \lfloor n/b \rfloor\) を計算できれば十分． \(b \geq \sqrt{N}\) のとき \(\lfloor n/b \rfloor \leq \sqrt{n}\) より高々 \(\sqrt{n}\) 通り， \(b \leq \sqrt{N}\) のとき \(\lfloor n/b\) は高々 \(\sqrt{n}\) 通りであるから， …

ABC418E 解法 四角形と，対辺の組を対応させる． 台形の選び方から平行四辺形の選び方を引けばよい． 一つの平行四辺形に対して，対辺の選び方が2通りあることに注意． 対辺が平行かどうかは，傾きで判断する．ただし，傾きが無限大のときも認める． 傾きは…

ABC416E 解法 全点間最短路問題なので，Floyd-Warshall を用いる． クエリを分解すると， 辺 \(e: a \rightarrow b\) の値を更新したときの cost を更新出来れば十分． 頂点\ (s\) から \(t\) への path であって \(e\) を使うものに対する距離を更新すれば…

ABC419E 解法 Index を mod \(l\) で類別する．同じ類は同じ値になる必要がある． よって，先頭の \(l\) 個だけ決めれば残りの値は全て一意に決まる． 先頭\(l\) 個の値の割り振りだけ全探索して dp. 使っている記号，マクロ等 "https://ecsmtlir.hatenablog…

ABC420E 解法 まず色が無い版で考える． これは union-find で解ける． 次に色が有る版で考える． 一度黒にした後に白に戻る場合がある事に注意して， connected component に含まれる黒の個数を保持すればよい． これは，connected component の代表元につ…

ABC422E 解法 乱択アルゴリズム．過半数の点が乗っている直線 \(l\) が存在すると仮定する． 異なる点 \(A,B \in N\) をランダムに取る． このとき，\(A, B\) が \(l\) 上にある確率 \(p\) は， $$p \geq \frac{\frac{N+1}{2}}{N} \cdot \frac{\frac{N+1}{2}…

ABC350F 解法 大小の flip と，区間の reverse は操作が可換なので，分離して独立に考えることができる． 大小の flip は，() の深さの偶奇で決まる． 区間の reverse は，() が出る度に reverse して表示する DFS を実行する． ここで， '(' の位置から ')'…

ABC236E 解法 平均値，中央値共に binary search で求まる． 値 \(x\) を固定した場合，平均が \(x\) 以上になる事は \[\sum_{i \in I} a_{i} / \sum_{i \in I} 1 \geq x\] と表せる．すなわち， \[\sum_{i \in I} (a_{i} - x) \geq 0\] と同値．これは先頭…

ABC161E 解法 まずは簡単のため，\(K\) 日働けるかという判定問題のアルゴリズムを考える． 入力の条件から \(K\) 日働けるのは保証されているが， このようなアルゴリズムをベースに解法を考えると解きやすい． これは，働ける日が来たら即座に働くという貪…

ABC137E 解法 Bellman-Ford でサイクル検出と最短経路(最長経路)を求めることができる． Bellman-Ford では，\(|V|\) 回 update して，それでも更新が終わらなければサイクルがあることになる． つまり，\(|V|+1\) 回更新処理をしてみれば分かる． 今回はゴ…

ABC408E 解法 上の桁から決まっていく．暫定的な答えを \(ans\) とおく． 桁ごとに Union-Find を用いて計算して間に合う． 下から \(i\) 桁目を決めたい．\(i\) 桁目より上の桁に対して \(ans\) が既に求まっている事になる． このとき，使ってよい辺は，\(…

ABC036D 解法 木DP の基礎問題． \(dp_{i,c}\) を， vertex \(i\) を root とする subtree について， \(i\) を color \(c\) にした場合全体 とする． 答えを子から親に計上するときの注意として， 子の答えたちは独立であることから積になる． 使っている記…

ABC418D 解法 xnor は xor に帰着できる．実際，与えられた文字列を反転すれば xor に帰着できる． また，\(\{0,1\}, xor, 0\) は群であるから，\(\{0,1\}, xnor, 1\) も群になる． 特に結合律が成り立つので，先頭から計算してもよい． 先頭から計算したDP …

ABC409D 解法 \(l\) と \(r\) を別々に求める． まず \(l\) は，\(s[l] > s[l+1]\) となる最小の \(l\) とすればよい． 次にサイクルは互換の積とみなせるので， \(r\) は \(s[r] > s[r+1]\) となる最小の \(r\) とすればよい． 使っている記号，マクロ等 "h…

ABC411C 解法 0: white, 1: black とする． 連続する pair (1,0) の個数 = 1の区間の個数 となる． ここで，v[n] = 0 とする． クエリ高速化の鍵となるのは， 連続する1の区間が変化するのは，与えられた a の前後2箇所のみという性質． よって，差分を更新…

ABC413C 解法 Run length encoding に近い．実際には，結合までは不要． 例えば，\( (x,2), (x,3) \) と並んでいるときに \( (x,5) \) の形に直す必要はない． 実装 pop_back は用いないので，deque でなく queue で十分． int main() { int q; cin >> q; de…

ABC413D 解法 必要に応じてソートしておけば，absは単調増加と仮定してよい． また，必要条件として，\(C[i] := abs(a[i])\) と定めた数列 \(C\) に対して， \(C\) の並べ替えが等比数列になる必要がある． この必要条件を満たしているとき，\(A\) の並べ替…

ABC360D 解法 数えるべき組 \( (i,j) \) は， 向きに関する条件: \(S_{i} = '1'\) かつ \(S_{j} = '0'\) 距離に関する条件: \(x_{j} - x_{i} \leq 2T\) を満たすもの． これは \(x\) について sort しておく事で，尺取り法で求まる． 使っている記号，マクロ…

ABC406D 解法 \(x\) 行目に落ちているゴミの列座標たちを \(ys_{x}\) とおく． \(y\) 列目に落ちているゴミの行座標たちを \(xs_{y}\) とおく． \(ys[x], xs[y]\) のサイズを取得して，削除できればよい． 実装 行と列を入れ替えただけなので，一つ実装を作…

問題概要 非負整数の重み付き有効グラフが与えられる． 始点と終点が指定されるので，walk のうち，辺の重みの XOR を最小化する． 解法 同じ辺を重複して使うことが出来ることに注意． もし 1回しか使えないのであれば DFS で良い． 今回求めたいのは path …

ABC410E 解法 まずは \(O(NHM)\) の解法を考える． \(i \in N, h \in [0,H], m \in [0,M]\) に対して \(dp_{i,h,m}^{0} \in Bool\) を， \([0,i)\) まで終えた直後において \(h,m\) 以上残すことが出来る と定める． 次に，\(O(NM)\) に高速化する． \(i\)-t…

ABC379E 考えた事 素直に考えれば，累積和を使えば解ける． 今回は，その方法だと桁が大きくなるのが問題で，足し算にO(1)でなくO(N)程度かかる． 何を全探索するか考えると，10 の指数 \(k \in N\) になる． 繰り上がりを無視すれば，答えは \(N\) 桁の自然…

ARC177A 考えた事 通貨 \(P\) が，\(P_{i} \leq_{div} P_{i+1}\) \(\forall i \in (P.size()-1)\) であるから， 高い通貨から貪欲に使えばよい． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { vll m =…

ABC110D 解法 \(N,M\) が固定で，\(M\) の素因数 \(p\) を重複込みで \(N\) 個の箱に入れる． より詳しくは，\(M = \Pi_{p: prime \\ e_{p} > 0}\ p^{e_{p}}\) としたとき， \(e_{p}\) 個の \(p\) を \(N\)個の箱に入れる場合の数を， 素因数 \(p\) の種類ご…