AtCoder Regular Contest 067 - F. Yakiniku Restaurants (1000)
結果
自力 AC
考察 60 分
実装 30 分
解法
注: めちゃくちゃ雑な解説になってます
左端と右端を決めたときの最適解は$ O(M)で計算できる (簡単なので説明は省略)
このままだと$ O(N^2M)となってしまうので, 注目する区間をできるだけ少なくしたい.
愚直解を書いてランダムケースで試してみると, 次の画像のようになった.
縦が左端の index, 横が右端の index である. 左端を固定したときの最適解を赤くしてある.
https://gyazo.com/6c61ed5e050a258a7a1cf22f7a6dd362
右端は単調増加になっている.
左端$ l_1, l_2 (l_1 < l_2)に対して, 最適解をとる右端のうちもっとも左のものが$ r_1, r_2だったとする. $ r_1 \leq r_2が証明できる.
区間$ (l, r)に対する答えを$ f(l, r)で表すことにする.
$ r_1 > r_2を仮定すると
$ f(l_1, r_1) - f(l_1, r_2) \geq f(l_2, r_1) - f(l_2, r_2)は常に成り立つ. これと$ f(l_1, r_2) < f(l_1, r_1)から$ f(l_2, r_1) < f(l_2, r_2)となり矛盾. よって示せた.
あとは分割統治によって$ O(NM \mathrm{log} N)となる.
感想
精進は精進の役に立つ