ARC100 Equal Cut ~二分探索で解く(すこし非効率)~
最大20万の長さの自然数列を与えられ、そこにしきりを3ついれて、4つに分割する。4つの数列の和の最大値と最小値の差を最小化するとき、その差はいくつになるか。
例） 5 2 3 6 1 3 2
ベストな分割方法は{5}, {2, 3}, {6}, {1, 3, 2}にして和は5, 5, 6, 6 で答えは1となる。
この記事で書いてるのは想定解ではないすこし非効率なものです。想定解については別途書きます。
パッと見てまで通りそうだなー。「切り分ける数列は4でそう多くない上に2のべき乗だし二分探索的なことができそうかなー。logつけられるし」と考える。
真ん中決め打ちして左と右の最適化すればできそうだなーって考える。
証明してみる。
],
],
],
]と分割したとする。この時、真ん中は決め打ちなので、
だけは定数となり、ほかは自然数の変数である。
左で最善を尽くした時、左の二つの区間の和の差をとしてみる。左の二つは大小関係を[0, p] + A = [p+1, q]としても一般性を失わないのでそうする。
右の二つの区間も同様に大小関係を左と同じ順番でずれてるとして決める。
1. [0, p] <= \[p+1, q] <= \[q+1, r] <= \[r+1, N-1] の場合
簡単に上記の状況を表すと
[0, p]----A---[p + 1, q]
[q + 1, r]---B---[r + 1, N - 1]
--------------------------------------------------------------------------------------------------->
この時は最小の値でないとき、前述の
] と
]の大小関係から
]はさらに左へといく。
でも同様に
が更に]右へと行く。よって、上記の貪欲法が結果的に最善となる。
2. [0, p] <= [q+1, r] <= [p+1, q] <= [r+1, N-1] の場合。
簡単に上記の状況を表すと、
[0, p]---------A-----------[p + 1, q]
[q + 1, r]-----------B-------[r + 1, N - 1]
----------------------------------------------------------------------->
この時、1.の時と同様な理屈で上記の貪欲が最善となる
3. [0, p] <= [q+1, r] <= [r+1, N-1] <= [p+1, q]の場合
簡単に上記の状況を表すと、
[0, p]---------A-------------------------------[p + 1, q]
[q + 1, r]---B---[r + 1, N - 1]
----------------------------------------------------------------------->
この時、1. の時とまた同じ理屈で上記の貪欲が最善となる。
よって1~3が全事象のカバーができてるので上記の貪欲は正しい。
めでたしめでたし。恭喜！
具体的な実装のお話を考えてみる。
アルゴリズムとしては、
真ん中を決め打ちして、それぞれ左右に分かれた部分で差が最小となるような場所で分割する。それを真ん中の場所通り試す。計算量は
なんどの区間の和を求めることになるので累積和で加速する。
具体的な左右に分かれた部分の最小化は累積和配列からlower_boundで求める。この時、lower_boundで求めた分割点の一つ前も試してみる(こういう二分探索系は実数値を求めるものでない限り、解の前後も候補に入れよ)
あとはこれを正しく、素早く実装するだけだが、lower_boundしかり、累積和配列しかり、仕切りを入れる場所は前と後ろの添え字どれを参考にするかなどで、配列がずれそう。こういう時は、小さい例を手で試して、紙でとりあえず導き出される区間や数式を書いてみろ。
ＡＣコード
https://atcoder.jp/contests/arc100/submissions/4426396
しゃくとり法によるよりよい解き方。
以上。
