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