ABC281E 解法 \(M\) 個の元を持っておき，小さい方から \(K\) 個の元の和も同時に保持しておく． 追加や削除をしたときに，一部の元しか更新されないので，それを利用して高速化する． つまり，差分を高速に更新出来ればよい． 実装 小さい方から先頭 \(K\) …

ABC152F 解法 条件の否定を考えると，黒が 0箇所となるので，扱いやすい． よって包除原理が使いやすい． 共通部分を求める包除原理を用いる． この場合，\(s \in 2^{M}\) を動かすとき，\(s = \emptyset\) を含むことと， 符号 \*1 return true; eset[i] ^=…

ABC294F 最初に 濃度を固定した方が簡単． また，2つしか混ぜない． 解法 0 自然な解法． 濃度 \(z\) を固定したとき， 2つの砂糖水 \(i \in N, j \in M\) を混ぜて濃度を \(z\) 以上に出来ることは， \[ \frac{a_{i} + c_{j}}{a_{i} + b_{i} + c_{j} + d_{j…

ABC076D 解法 時刻と速度を軸としたグラフを書くと面積が距離となり， これを最大化する． 時刻 \(t\) と速度 \(v\) を状態とする DPができる． \(\ (t,v)\ \) が同じなら，次にできる遷移は同じになるため， そこに至るまでの道中を同一視できる． 簡単な問…

本問(shift のみ): ABC307C類題(回転あり): ABC322D 解法 置き方を全探索したいが，少し減らす必要がある． 何も考えずに置くと， A, B, X それぞれについて \(30^2\) 通り調べるので， \(30^6 = 729,000,000\) となって厳しい． 考えてみれば，\(A\) は固定…

ABC176D 解法 01-BFS. 移動A のコストが 0, 移動B のコストが 1. Queue の代わりに deque を用いる． コスト 0の方が優先されるので，queue の先頭に入れる． コスト 1は後回しなので，，queue の後ろに入れる． 実装の注意 移動 Bのとき，移動先として今い…

ABC096D 解法 \( 5\)個選ぶとか，\(55,555\) 以下とかは，あまり意味の無さそうな条件で， 分かりづらいだけなので，一度無視する． 簡単な問題として， \(K\) 個以下選ぶ，\(K = 2,3\) を考える． \(K = 2\) のとき， \(a_{i}\) を全て \(1\) mod \(2\) と…

ABC164E 解法 制約に注目すると，\(N \leq 50, a_{i} \leq 50\) と小さいので， これを利用したい． 素直にDPを考えると， 小さい部分を状態に入れたい． \(a\) が小さいことので，お金を状態に入れた DPをしたい． そこで，dp : (vertex, 所持金) \(\righta…

ABC178F より簡単な類題 「Size が \(2N\) の multiset \(c\) が与えられる． この中からペアを \(N\) 個作る． ただし，異なる元同士をペアにしなければならない．」 という問題を考える． これが可能である必要十分条件は， \(c\) における一番多い元 \(x\…

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) ABC285F 解法 \(S,T\) の持つべき性質を調べる． \(S_{l,r} := S_{[l,r)}\) とおく． 文字列 \(U\) と \(a \in \Sigma := Alphabet\) に対して， \(cnt_{U}(a)\) を，文字列 \(U\) に現れる \(a\) の個数とする．…

ABC214E 解法 閉区間 \([l,r]\) で考える． 貪欲法． 基本は \(l\) が小さい順に， \(l\) が等しい場合は，\(r\) が小さい順に処理する． \(l\) が小さい順に \(r\) をストックしていき， 小さい \(r\) から使っていく． \(r\) 達を priority queue に入れて…

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) \(\def \ra {\rightarrow}\) ABC296F 解法 1回の操作で \(A\) の \(i,j\) の部分を swap して， 同時に \(B\) の \(i,k\) の部分を swap する． 一致できるかどうかだけが問題なので， \(A\) を固定して \(B\) だ…

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) \(\def \ra {\rightarrow}\) ABC322F 解法 (交わらない)隣の二つの区間 \(I,J\) を結合したときを考える． 基本的には，\(I,J\) それぞれの 1 の連続区間の最大が \(I \cup J\) における最大となる． しかし，結…

ABC334F スタートとゴールの vertex を \(0\), それ以外の vertex を \(1, \cdots , N-1\) として， \(N\) 個の頂点で書き直したバージョンで説明する． \(d_{i,i+1}\) を \(i\) から \(i+1\) への距離とおく． 解法 0: Segtree まず簡単なバージョンの問題…

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) ABC282F 解法 0: Sparse table 長さ \(2^{i}\) の区間を用意して，それらの組み合わせで 区間を覆うことができる． 区間を指定されたとき，sarse table から使う幅 \(w\) を全探索する． \([l, l+w) \cup [r-w, r…

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) ABC147E 解法 absでなく差で考える． 基本は部分和と同じ様に解ける． つまり， \(dp_{i,j} := \) マス\(\ (i,j)\ \) にいるときの 偏り全体 とする． 実装 集合でなく bitset を使うと高速化出来る． 使っている…

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) 問題の性質 まずは問題の性質から探る． 同じ種類の寿司なら，美味しさが高い物から食べるのが最善． 同じ種類を食べるときは，最初の 1個だけは種類ボーナスに影響するが， 2個目以降は影響しない． 簡単な問題 …

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) 解法 Lazy segtree. 文字列を 10進数とみなすので，segtree に乗せる． 区間の書き換えを保留しておくのがポイント． Segtree の積が，文字列の結合に対応する． 10進数で考えるので，結合する前の桁数を持ってお…

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) ABC225E 解法 問題文を翻訳すれば，区間スケジューリング問題と同じ． 区間の両端を，直線の傾きと考えればよい． 整数のペアとして，傾きを有理数で扱うと比較も整数でできる． 注意 分母が0になる場合と，既約…

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) ABC151F 解法 最小包含円を求めるアルゴリズムが知られている． 下に凸な関数に対して三分探索を二回用いる． \(P := {P_{i}}_{i \in N}\) を平面の点の集合とする． \(f_{P}(x,y) := \) 点 \(\ (x,y)\ \) から\(…

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) ABC331F 解法 ハッシュで部分文字列であるかを高速に判定する． 回文の判定として，通常の文字列と反転した文字列の2種類のハッシュを用意する． 文字列のハッシュを segtree に乗せることで， \(O(log N)\) でハ…

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) ABC321E 解法 1-indexed で complete binary tree の頂点に番号を付ける． LCA \(v\) を全探索． \(v\) を root とする subtree において，\(v\) からの距離が \(d\) である頂点全体の個数 \(f(v,d)\) を求める．…

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) ABC061D 解法 0: コストを -1 倍することで，min cost の問題に帰着できる． ただし，負のコストがあるため，Dijikstra は使えない． Bellman-Ford に近い解法なら，負のサイクルも検出できて \(O(NM)\) . 負のサ…

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) ABC128E 簡易化: 変数の固定 まずは人と座標を固定して考える． 時刻と座標の二つの単位があるので，一方に統一して判定式を作る． ここでは，時刻に注目した式で判定する． 人 \(i \in Q\) が座標 \(x\) を訪れ…

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) ABC333F 鍵 巡回しているため，無限に同じ局面になる可能性がある． しかし，確率を計算すれば収束するため，値は有限になる． 巡回部分をどの様に回避するかが鍵になる． 解法0 等比級数の公式を用いる方法． \(…

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) ABC146E 解法 \(a\) の累積和を \(s\) とおく． \(a\) の空でない連続する区間を \([l,r)\) とおく． ans は，\(\ (l,r)\ \) の組であって \(s[r] - s[r] % K = r-l\) and\(0 \leq l < r \leq N\) を満たすものの…

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) ABC162E 解法 約数系包除原理に近い考え． まず gcd \(d\) を全探索して， \(d\) の倍数になる個数を数える． 丁度 \(d\) に対して調べるのが本問の答えだが， 簡単のために 最大とは限らない公約数 \(d\) に対し…

ABC083D 解法 答え \(K\) について単調性があり，小さい \(K\) であれば成立する． Flip する区間を一つだけずらして再び flip すれば，両端だけ flip することが出来る． 基本はこれを繰り返せばよい． しかし，真ん中はどうやっても flip できない． 左端…

ABC203D 解法 答えの候補を二分探索する． 集合 \(A\) に対して， \(min(A) \leq x\) である事は， \(A\)のある元で \(x\) 以下となるものが存在することと同地． また， \(min(A) \geq x\) である事は， \(A\)の任意の元が \(x\) 以上であることと同値． い…

ABC165E 解法 \(l\)を偶奇で2つ取って，\(k\)を動かして \(\ (i+k,i+l-k)\ \) の形で選ぶ． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll n,m; cin >> n >> m; vector<pll> ans; rep1(i,m/2){ ans.empla</pll>…