kaage精進録

雑な解説とかライブラリとかおきもちの垂れ流しです。

AGC034-C Tests

問題リンク

解法

重要な考察がいくつかある

すべてのテストの重要度は $l_i,u_i$ のどちらかである。これは、どんな場合でも損失を最小化/得を最大化するのはこの2つの値のどちらかになるからである。
$T$ 時間勉強するとき、その内訳は、重要度が $u_i$ で $X$ 時間勉強する教科、重要度が $l_i$ で $0$ 時間勉強する教科、残りの余った時間を使うテスト1つ、となる。これは、重要度が決まっているとき、重要度の高い方から貪欲に勉強するのが得で、かつ $X$ 時間勉強するならその重要度は $u_i$ であり、そうでなければその重要度は $l_i$ である場合が最適だからである。

これらを踏まえて、次のような解法を取れる。

総勉強時間を二分探索する。
余った時間を使うテストを全探索する。このテストの重要度は貪欲に決められる。
$X$ 時間勉強する教科を、全体での得が大きいように貪欲に取る。これはならし $O(1)$ 時間で行える。

時間計算量は $O(N\log NX)$ となり、間に合う。

感想

貪欲法と二分探索、考察が適度に組み合わさったよい問題だと思った。