TCO 2016 Round 1B Hard. SettingShield

三分探索したけど本当に正しいかは分からない。

h 個の普通の区間 [left[i],right[i]] と全体を覆う特殊な区間がある。普通の区間に力 P を掛けるには P のコストが必要である。一方で特殊な区間に力 P を掛けるには tP のコストが必要である。

位置 i を覆う区間の力の総和を protection[i] 以上にするのに必要な最小のコストを求めよ。

特殊な区間に力 x を掛けたときのコストで三分探索をする。

i=0,...n-1 の順に見ていき protection[i]＞0 だったら、 i を覆う区間のうち最も右端の大きな区間に protection[i] の力を掛けるという戦略が最適になる。

たとえば protection[0]=1 で [0,5], [0,6], [0,8] という 3 つの区間があったら、できるだけ遠くまで巻き込める [0,8] を使うのが最善である。

三分探索はいつも自信なさげに使っている。