\(\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\) の値の期待値 とする． 遷移を求める． \…