問題 https://atcoder.jp/contests/dp/tasks/dp_z 考え方 ConvexHullTrick を用いる。もらうDPを考えよう。 足場 に至るときの最小のコスト と定義する。この時DPの遷移は となる。 の部分は に関する1次関数と捉えることができて なる における1次関数たち…

問題 https://atcoder.jp/contests/dwacon2018-prelims/tasks/dwacon2018_prelims_d 考え方 まずは最小値に単調性があるので、最小値 を二分探索することにしよう。つまり以下の問題を考える。ディスク使用量をコストと呼ぶこととする。 「最小値を とすると…