仮のブログ

仮です

AGC034-C Tests

思考の流れ

高橋君の取る点数を固定する. (この値を $a_i$ とする.) このとき, $a_i\ge b_i$ なら $c_i=u_i$ に, $a_i\lt b_i$ なら $c_i=l_i$ にするのが最適.
つまり, $c_i$ の取りうる値を $l_i,u_i$ に限った問題を考えても答えは同じ.
今度は $c_i=u_i$ とする $i$ の集合 $(=:S)$ を固定し, $a_i$ の値を変動させる. $i$ 番目のテストを $1$ 勉強すると, $i\in S$ なら $u_i$ だけ, $i\notin S$ なら $l_i$ だけ, $A$ の値が増える.
よって, この増加分が大きいテストから勉強するのが良い. つまり, あるテストを $X$ まで勉強して, 次のテストを $X$ まで勉強して......という最適解が存在.
つまり2. に加えて, 高々 $1$ つの番号 $i'$ を除いて $a_i\in\lbrace 0, X\rbrace$ に限った問題を考えても答えは同じ.
4.で除く $i'$ を固定する.
$i$ と書いたら $i'$ を除いているとする.
$a_i=0$ のとき, このテストによる $A-B$ への寄与は $-b_il_i$ , $a_i=X$ のとき, このテストによる $A-B$ への寄与は $(X-b_i)u_i$ である. よって, $a_i$ を $0$ から $X$ に変えると, $A-B$ は $(X-b_i)u_i+b_il_i$ だけ増える.
よって, 最初全ての $i$ について, $a_i=0$ としておいて, $(X-b_i)u_i+b_il_i\ (=:p_i)$ が大きい $i$ について $a_i=X$ にしていくのが良い.
$p_i$ を降順に並べ, 累積和をとる. これを $0=S_0,S_1,\dots,S_{n-1}$ ( $i'$ を除いているので $S_{n-1}$ まで)とする.
$\displaystyle \sum_{k=1}^{n}b_kl_k\ge S_{j}$ なる最大の $j$ を $M$ とすると, $M$ 個のテストを $X$ まで勉強して, 残り足りない分を $i'$ 番のテストを勉強すればよいことが分かる. $i'$ をどれだけ勉強する必要があるかは簡単な計算で求まるのでこの場合の総勉強量は $MX+(i'$ の勉強量) と計算できる.
ただし, 足りない分を賄え場合があるが, その時は $i'$ を固定するのが最適でない場合なのでそれはそれで良い. また, 上記の値が $i'$ を固定した場合の最適解でない場合もあるが, これも7. で全探索をする過程で回収できるので放っておいてよい.
$i'$ を全探索する. $p_i$ の値は $i'$ に依らないため, 最初に降順に並べておけばそれを使い回すことで, 各 $i'$ に対して $O(\log{N})$ で 6. の値を計算できる. (前から $M$ 項の中に $i'$ が含まれるかで場合分けすれば良い. )
全体 $O(N\log{N})$ になったので解けた.

気持ちよく解けたので記事にした.