Codeforces Round #320 (Div. 1) [Bayan Thanks-Round] C. Weakness and Poorness

問題

codeforces.com

解法

まず, 数列 a の weakness の値 w(x) は x に関する凸関数になることを把握します。
これは, w(x) が abs(S-x) (S は区間ごとの和) の最大値を取るような感じになっていることからわかります。

よって, この問題では w(x) の値をある程度高速に求められれば, あとは x に関する 3 分探索をするだけです。

ということで, w(x) の値を高速に求める方法を考えます。まず, a[i]-x が正のもので絶対値を最大化しようとするものと, a[i]-x が負のもので絶対値を最大化しようとするもので方向性を分けて考えます。
a[i]-x が正のもので絶対値を最大化しようとするほうがわかれば同様にして x[i]-x が負のもので絶対値を最大化する方もわかるので前者の方だけがんばりますが, 単純に連続した部分列の総和が正である限りとり続けて，負になったらリセットし, 最大値を記録するだけです。

例えば 100, -1, 10, 10 とかいう数列があったら, 100, 99, 109, 119 と求めていきます。

const int MAXN = 200020;
int a[MAXN];

double calc(double x, int n) {
    double ret = 0;
    {
        double sum = 0;
        int r = 0;
        while (1) {
            while (r < n) {
                sum += a[r++]-x;
                ret = max(ret, sum);
                if (sum < 0) {
                    sum = 0;
                    break;
                }
            }
            if (r == n) break;
        }
    }
    {
        double sum = 0;
        int r = 0;
        while (1) {
            while (r < n) {
                sum += x-a[r++];
                ret = max(ret, sum);
                if (sum < 0) {
                    sum = 0;
                    break;
                }
            }
            if (r == n) break;
        }
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    double low = -20000, high = 20000;
    for (int i = 0; i < 100; i++) {
        double m1 = (2*low+high)/3, m2 = (low+2*high)/3;
        double p1 = calc(m1, n), p2 = calc(m2, n);
        if (p1 < p2) high = m2;
        else low = m1;
    }
    printf("%.10lf\n", calc((low+high)/2, n));
    return 0;
}