- https://codeforces.com/contest/799 (div1+div2)
A. Carrot Cakes
$2$ 台使うときの最小時刻を求めればよいです.例えば二分探索で求まります.
としたがそもそも判定だけすればよいので二分探索の内側だけで良かった.
B. T-shirt buying
そのままシミュレーション.各色を含む値段を最小値から取り出せるようにしておけばよいです.
C. Fountains
CC, CD, DD というとりかたをそれぞれ解けばよいです.CC はひとつ固定するともうひとつは区間 max です.
D. Field expansion
$a$ が大きい方から順に使っていくとしてよいです.また答は非常に小さいはずです($O(\log(hw))$).dp[x]=yの最大値,というような dp で十分です.
E. Aquarium decoration
アイテムの種類は $(0,0)$, $(0,1)$, $(1,0)$, $(1,1)$ の 4 種で,それぞれ昇順ソートして手前から使うとしてよいですおきます.
$(1,1)$ の個数を決めるごとに解きます.$(0,1)$ や $(1,0)$ のうちいくつかは確定で使う.それ以外は全種類の中から貪欲に使うということになります.集合に要素を追加しながら,top-k-sum が $k$ についてスライドでとれるようなデータ構造があればよいです.
F. Beautiful fountains rows
$a,b$ の parity を止めてときます.
$a$ を決めたとき,各区間の条件は,$b$ に対する $O(1)$ 個の禁止区間という形になります.$a$ をスライドしたときの禁止区間の変化回数も,全体で $O(N)$ 回です.これらを丁寧に処理しながら,最小値とその個数を持つタイプの遅延セグメント木ですべてを計算できます.
G. Cut the pie
方向ベクトルの偏角が $t$ のときの,直線に関して左側の部分の面積を $f(t)$ とします.$f(0)+f(\pi)$ が全体の面積と一致することと $f$ の連続性から,$0, \pi$ の間で二分探索を行えば答を見つけられます($f$ に単調性はないと思いますが,境界をひとつとりたいだけなので不要です).
なので $f(t)$ を求められればよいです.凸多角形に対角線を引いたときの面積を計算するための累積和の前計算や,交点がどの $2$ 点の間にできるかなどの二分探索などを丁寧にやればできます.
二分探索のときに先に交わる辺を特定することで,たぶん $O(\log N\log (\varepsilon^{-1}))$ を $O(\log N + \log(\varepsilon^{-1}))$ にできると思うのですが,それをしなくても大丈夫でした.