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\) が存在するか， という判定問題を解けばよい．\(i \in I\) に対して \(w_{i} := b_{i} - c_{i}x\) とおく． 与えられたグラフが DAG なので，このグラフ上で DP が可能． \(i \in …
