\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) \(\def \order #1{\lvert {#1} \rvert}\) 問題概要 \(N\) 頂点の tree \(G\) が与えられる． \begin{align} U &:= \set{(i,j,k) \in V(G)}{ i,j,k \text{は相異なる} }, \\ L &:= \set{(i,j,k) \in U}{i,j,k \tex…

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) ABC314F 問題概要 有向 tree \(T\) を構成する． \(N := \{0, 1, \cdots, N-1\}\) \(|V(T)| = 2N-1\) The set \(L := \set{\{i\}}{ i \in N}\) is the set of leafs of T. For any vertex \(x\) of \(V\) is a su…

ABC321F 問題概要 Muliset に対する部分和問題に，追加と削除クエリを与えたもの． 俗に戻すDPと呼ばれる． 解法 (0) まず，multiset が固定されている場合を考える． これは普通の部分和DP. とくに，配列を 1次元にした inplace DP で考えると， 今回の問題…

ABC324F 解法 平均の最大化なので，binary search が典型． \(I \subset E\) に対して， $$ f_{I} := \frac{\sum_{i \in I}b_{i}}{\sum_{i \in I}c_{i}} $$ とおく． \(x \in \mathbb{R}\) を固定したとき，\(f_{I} \geq x\) となる \(I\) が存在するか， と…

ABC325F 解法 まず，素直に bool 型 dp を考える． \( dp_{i,j,k} := \) 区間 \(i\) まで， センサー 1 を \(j\) 個， センサー 2 を \(k\) 個 で可能か \(\in Bool\) とする． 次に，bool 型 dp の定義域のいくつかを値域に移すことを考える． このとき，\(…

ABC326F 解法 移動自体は，\(i \in N\) 回目の操作について \(i\) mod 2 で座標軸ごとに独立に分けることができる． \(M := N/2\) なら，\(O(2^{M}\) は間に合う． 実装 簡単のため，\(N \equiv 0\) mod 4 となる様に \(A\) の末尾に \(0\) を追加する． 使…

ABC327F 解法 リンゴを固定して，それを覆う籠の位置を動かす． 籠の左上や右上を，籠の位置と一対一対応させる． 縦軸を時刻，横軸を座標として 2次元で考える． リンゴ1個に対して，籠の範囲を考えると， 長方形領域が対応する． つまり，長方形領域(2次元…

ABC332F 解法 簡単なバージョンで問題を考える． \(i \in N\) 毎に独立に解けるので，\(N=1\) として考える． \(y := A_{0}\) とおく． \(j \in [0,M]\) に対して， \(y_{j} := \) \([0,j)\) まで終えたときの \(y\) の値の期待値 とする． 遷移を求める． \…

ABC015D 解法 ナップザック問題の DPと同じで，部分和問題の DP. 状態数が少ない様に DP の定義域と値域を選ぶと， 空間計算量と時間計算量が小さくできる． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main(…

ABC019D 解法 木の直径を求めるアルゴリズム． 任意に頂点を選び，\(v_{0}\) とする． \(v_{0}\) から最も遠い点の一つを \(v_{1}\) とする． \(v_{1}\) から最も遠い点の一つを \(v_{2}\) とする． \(v_{1}, v_{2}\) が直径の一つ． 実装 始点を固定したと…

解法 2人のプレイヤーの座標の組を頂点にもつグラフ上でBFS． 実装 移動先の位置は，今のマスにも依存することに注意． 壁に向かって移動しようとしたときは，今の位置にとどまるが， もう一方のプレイヤーが移動できる場合がある． 使っている記号，マクロ…

\(\def \ra {\rightarrow}\) ABC338D 解法 1本封鎖されれば，通るべき path が一意に定まる． 相異なる vertices \(a,b \in N\) を固定する．\(a < b\) と仮定してよい． Edge \(e \not\in [a,b)\) を切断したとき，path は \(a \ra a+1 \ra \cdots \ra b\) …

ABC345D 解法 回転と裏返しも良いと書いてあるが，裏返しは意味がない． 回転が高々 \(2^{N}\) 通り， 埋める順番が高々 \(N!\) 通り． \(N \leq 7\) なので，遷移に時間が多少掛かっても間に合う． 判定問題を試すときは，取りこぼしさえ無ければ十分． 数…

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) ABC345C 解法 \(X := S\) から 1 swap で作れる string 全体の集合 とする．答えは \(|X|\). \(S \in X \iff\) for some \(i\) and \(j\) \(\in N\) such that \(i < j\) and \(S_{i} = S_{j}\) \begin{align} X …

ABC344D 解法 DP. 状態を，\(T\) の \([0,j)\) まで一致させたとして \(j\) をもつ． \(S_{i}\) を使えるかどうかは， \(T_{[0,j)} + S_{i} = T_{[0,j+|S_{i}|)}\) と同値． 注意 substr は，範囲外にならない様に． 使っている記号，マクロ等 "https://ecsm…

PAST12K 解法 Easy 削除のみの場合． クエリを先読みして，逆に処理すれば，union-find で解ける． Normal 追加と削除の場合． ただし，追加する辺が 10個以下． この場合もベースになるのは Easy版で，クエリ先読みと逆順処理をする． もとのクエリで追加す…

PAST12H 解法 貨幣の枚数を考える． 組(金貨，銀貨，銅貨) が辞書順で最大になるのがベスト． 銅貨の残り枚数を状態にもって DP すれば O(NX). 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" pll operator + (pll a,…

PAST12G 解法 何を全探索するか考える． 素直に \(T\) を全探索するのでは \(TLE\) ． \(T\) は全探索できないが，\(T\) の \(?\) の位置は，最大で \({}_{10}C_{5} = 252\)なので十分間に合う． まず \(S := S_{i}\) を一つ固定して考える． \(?\) の位置だ…

PAST15J 問題の言い換え ダメージの累計が最小になる様に手裏剣を使う． 思考の流れ いくつか思いつくことがある． まず暫定的な答えを出す．これは簡単に求まるというのが大事． 手裏剣を 0枚使ったときの求めて，その答えを修正していく． 手裏剣 1枚でど…

PAST14L 準備 \(A\) が \(B\) より強いと分かっているとき，かつそのときに限り \(A\) から \(B\) に矢を張ったグラフ \(G\) を考える． 問題 Easy 辞書順を無視して，強い順に並べる． これは \(G\) においてトポロジカルソートするのと同じ． Normal(本問)…

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) PAST15K 解法 コストの最小を求めるが，下界を求めてそれを実現する例を与える． 下界を求める過程は，必要条件を求めるのに近い． Sub problem: コスト無し コストを無視して \(P_{i}\) と \(P_{i+1}\) の swap …

ABC341E 解法 良い文字列である必要十分条件が， 悪い箇所が一つもないこと． つまり，悪い箇所の存在を高速に判定できれば良い． 変化した部分が少ないので，そこだけ更新． 答えるクエリでは，0,1が交互に並んでいるか (\in Bool) を判定する． 区間を反転…

PAST013E 解法 シミュレーション Stack \(t\) を使ったシミュレーションをする． 文字列 \(s\) を前から調べていき，今の文字で場合分け． ')'のとき: \(t\) が空なら，対応する'('が存在しないため失敗． 空でないとき，\(t\) の末尾が '('なら OK, ')'なら…

PAST013J 解法 部分問題: 直線 \(l\) を固定したとき 直線\(l: ax + by = c\) で，平面が2つの領域に分割される． 2点 \(P,Q\) が，同じ領域に属しているかを判定する． 同じなら直線を通らなくて済むし， 異なるなら直線を通らないといけない． 2つの領域は…

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のとき，移動先として今い…