AtCoder BC102 D: Equal Cut

問題

https://beta.atcoder.jp/contests/abc102/tasks/arc100_b

解法

長さNの数列の切れ目はN-1通りあるため、3つの切れ目を選ぶ組み合わせは_n-1C₃通りあります。Nは最大2x10⁵であるため、全ての組み合わせを試すのは現実的ではありません。

「P、Q、R、Sの最大値と最小値の差の絶対値が最小になる」は言い換えると、「P、Q、R、Sの大きさが出来るだけ近い場合」ということです。最適なのは、数列の総和の1/4になる場合ですが、実際にはなるべく1/4に近い値を目指すことになります。

ここで数列の三つの切れ目をi1、i2、i3とおきます。

そしてi2を固定した場合を考えます。

この時、PとQ、RとSの差が最小になる切れ目がi1とi3であったとします。

次に、i2を右に一つずらす場合を考えます。

この時、i1とi3は「そのまま」か「右にずれる」ことになります。（つまり単調増加）

そして、PとQ、RとSの差が最小になる新しいi1とi3に更新していきます。

このような処理をi1=0、i2=1、i2=3を初期状態として繰り返しながら、「P、Q、R、Sの最大値と最小値の差の絶対値が最小」になる値を求めることで解けます。

なお、配列の部分和については、累積和を事前に求めておくことで定数時間で計算できますので、全体としてはO(N)で解くことが出来ます。

実装

n = gets.chomp.to_i
a = gets.chomp.split.map(&:to_i)

# aa = 累積和
aa = [a[0]]
1.upto(n-1) do |i|
    aa << aa[-1] + a[i]
end

i1 = 0
i2 = 1
i3 = 2

ans = 10 ** 9

while(i2 < n-2) do
    while i1 < i2 - 1 do
        if (aa[i1] - (aa[i2] - aa[i1])).abs > (aa[i1+1] - (aa[i2] - aa[i1+1])).abs
            i1 += 1
        else
            break
        end
    end

    while i3 < n - 2 do
        if (aa[n-1] - aa[i3] - (aa[i3] - aa[i2])).abs > (aa[n-1] - aa[i3+1] - (aa[i3+1] - aa[i2])).abs
            i3 += 1
        else
            break
        end
    end
    pqrs = [aa[i1], aa[i2] - aa[i1], aa[i3] - aa[i2], aa[n-1] - aa[i3]]

    ans = (pqrs.max - pqrs.min) if ans > (pqrs.max - pqrs.min)


    i2 += 1
end

puts ans