# ARC100 B - Equal Cut

2019-05-15 

[chokudai さんの](http://chokudai.hatenablog.com/entry/2019/02/11/155904) で、
青色の半数が一時間でとける問題と紹介されていたもの。

累積和が使えそうなことと、まず LとRにわけて、さらにそれぞれを２つにわけるんだろうなぁというところは、
なんとなく想像がついたのだけど、そこから、方針たてられなかった。

最初の L と R を分けるのに等分するのかなぁと考えたのだけど、それについては、自分で反例を思いついてしまって、
そこで行き詰まり、解説読み。

なるほど。LとRを分ける位置について、すべて探索（O(N))、分けたあとに、それぞれまた O(N) だとダメなんだけど、
そこで、LとRを分ける位置 (i) が動くにつれて、つぎの分割 (j, k) の位置も一方向にしか動かないことを利用する。
（さらに、j, k それぞれ全探索せずに、凸であることを利用するとかかな）

解説読んで、自分で書いたのが [これ](https://atcoder.jp/contests/arc100/submissions/5405248)。

もっと上手に書けるべきだろうし、他の人のやつ読んで勉強しないといけないんだろうけど。ひとまず今日はこれで。