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\) を追加する． 使…