atcoder ABC102

c問題は簡単だったが、D問題は600点ということもあり難しかった。
https://atcoder.jp/contests/abc102

C問題

方針

全てのa_{i-iとの絶対値が最小になるような値bを求める問題。
数列の個数が最大で10の5乗まであるので全ての値について絶対値の和を求めていくのは間に合わない。ここで、数列a-iとの絶対値について考えてみると明らかに数列をソートして真ん中の数値をbとしてやれば絶対値の和が最小になることがわかる。}

D問題

方針

まず3つの仕切りを全探索をしたくなるが数列の数に注目すると10の5乗なので明らかに間に合わないので、全探索できるのは一つの仕切りのみとなる。そこで、どの仕切りを選ぶか考えてみると、真ん中の仕切りを選べば、仕切りの左側は右側に関与できず、仕切りの右側は左側に関与できないので、高速で仕切りの最適場所がわかりそうである。よって、真ん中の仕切りを全探索した時に、高速で左の仕切りの位置と右側の仕切りの位置を求めることを考える。ここで、真ん中の仕切りより左側について考えると左側の数列の和は一定である。同様に右側の和も一定である。図にすると下のようになる。

ここで、左側のみについて考える(右側も同様にして求められる)。左側の和をS、左の仕切りより左側の和をA、右側をS-Aとし、数直線状で表すと次のようになる。

前述の通り、Sは変わらないので、S/2も一定である。題意を満たすには、このAからS-Aの範囲をできるだけ狭くすれば良い。すなわち、AをS/2に千和ければ良い、これは累積和を求めておいて、二分探索などで求められる。注意すべきは、二分探索をするとき、AをS/2を越えた時と、その一個前を両方求めて、よりAとS-Aの絶対値が小さい方を採用することである。