ABC102 D - Equal Cut - ツバサの備忘録

解法

パッと見とっつきにくい問題。
まずは、3つのうち、どこか1つの仕切りを固定して考えるとして、どの仕切りを固定すると見通しがよくなるかを調べます。

f:id:emtubasa:20190425010205p:plain

まず、右端の仕切りを固定することと、左端の仕切りを固定することによる見通しの良さに差はありません。
ので、端の仕切りを固定したパターンと、真ん中の仕切りを固定した2つのパターンで見比べていきます。

端の仕切りを固定したパターン
このパターンでは、最終的な4つの数列のうち、1つの総和が確定します。今回は、右端の仕切りを固定して、 $S$ が固定されたと考えます。
すると、残った1つの長い数列を3分割して、うまく最適解を求める問題に帰着できます。が、この問題を解くのはあまり効率的ではないです。
真ん中の仕切りを固定したパターン
このパターンでは、数列が2つにわかれ、それぞれで、もう一つずつ仕切りを置く形になります。
この時の最適な2つの仕切りの置き方を考えます。このとき、 $abs(P-Q)$ 、 $abs(S-R)$ がそれぞれ最小となるように仕切りを置けばよいです。
簡単のために $P \lt Q$ 、 $R \lt S$ とします。実際の求める値のパターンは $S-P,S-R,Q-P,Q-R$ の4パターンであり、どのパターンでも、 $abs(P-Q),abs(S-R)$ が最小になるようにすることで、値を小さくすることができます。こちらのパターンの方が、先ほどの仕切りの固定の仕方よりも見通しが良くなります。

ということで、真ん中の仕切りを固定して、そのパターンについての残りの2つの仕切りの置き方を探し、これを全探索すればよいです。
ということで、あとは、とある数列に対して、それを二分したときの、それぞれの総和の差の絶対値が最小になるような仕切りの置き方を求めることができればよいです。
$abs(P-Q)$ が最小となるような $P,Q$ の分け方は、2通りの方法で求めることができます。どちらの場合も、累積和をあらかじめ計算しておく必要があります。

尺取り法で求める
累積和は、数列の要素が増えるにつれて単調増加します。ので、尺取り法を用いると、 $r$ が数列の右端だった場合に、その数列の仕切りの最適な場所 $l$ が、 $O(N)$ で前計算した後、 $O(1)$ で参照できます。 $l$ と $l+1$ を見比べていって、 $l$ の方が差の絶対値が少ない場合、 $r$ に対する $l$ が求まったことになります。
二分探索で求める
$abs(P-Q)$ が最小になるということは、 $P,Q$ は、 $\frac{(P+Q)}{2}$ に最も近い値になっているはずです。ということで、累積和がこのような場所になる部分を二分探索で求めれば、 $O(logN)$ で求めることができます。