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) を判定する． 区間を反転…