백준18571 Calculating Average

작성일 | In

문제 링크

  • http://icpc.me/18571

사용 알고리즘

  • 병렬 이분 탐색
  • 컨벡스헐 트릭

풀이

$\displaystyle \frac{\sum_{i=s}^{e}A_i}{e-s+1}$를 최대화하는 문제입니다.
$\displaystyle \frac{\sum_{i=s}^{e}A_i}{e-s+1} \geq k$가 될 수 있는지 판단하는 파라메트릭 서치를 사용합시다. $\displaystyle \sum_{i=s}^{e}(A_i-k) \geq 0$이 될 수 있는지 확인하면 됩니다.

$k$가 고정되어 있을 때 $\displaystyle \sum_{i=1}^{N}(A_i-k)$의 값은 쉽게 구할 수 있습니다. 그러므로 $\displaystyle \sum_{i=s}^{e}(A_i-k)$를 최대화시켜서 0 이상인지 확인하는 것보다는 $\displaystyle \sum_{i=1}^{s-1}(A_i-k)$와 $\displaystyle \sum_{i=e+1}^{N}(A_i-k)$을 각각 최소화시켜서 남은 부분이 0 이상인지 확인하는 것이 편할 것 같습니다.

두 함수 $f_t(k), g_t(k)$를 정의합시다.

  • $\displaystyle f_t(k) = -tk + \sum_{i=1}^{t}(A_i-k)$
  • $\displaystyle g_t(k) = -(N-t+1)k + \sum_{i=t}^{N}(A_i-k)$

두 함수는 $k$에 대한 일차함수입니다.
$\displaystyle \sum_{i=1}^{s-1}(A_i-k)$의 최솟값은 $f_1(k), f_2(k), \ldots, f_{t-1}(k)$의 최솟값과 같고, $\displaystyle \sum_{i=e+1}^{N}(A_i-k)$의 최솟값은 $g_{t+1}(k), g_{t+2}(k), \ldots, g_N(k)$의 최솟값과 같습니다.

Convex Hull과 Parallel Binary Search을 구현해주면 문제를 풀 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#pragma GCC optimize ("O3")
#pragma GCC target ("avx,avx2,fma")
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

namespace FastIO{
    inline int readChar();
    template<class T = int> inline T readInt();
    template<class T> inline void writeInt(T x, char end = 0);
    inline void writeChar(int x);
    inline void writeWord(const char *s);
    static const int buf_size = 1 << 18;
    inline int getChar(){
        #ifndef LOCAL
        static char buf[buf_size];
        static int len = 0, pos = 0;
        if(pos == len) pos = 0, len = fread(buf, 1, buf_size, stdin);
        if(pos == len) return -1;
        return buf[pos++];
        #endif
    }
    inline int readChar(){
        #ifndef LOCAL
        int c = getChar();
        while(c <= 32) c = getChar();
        return c;
        #else
        char c; cin >> c; return c;
        #endif
    }
    template <class T>
    inline T readInt(){
        #ifndef LOCAL
        int s = 1, c = readChar();
        T x = 0;
        if(c == '-') s = -1, c = getChar();
        while('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar();
        return s == 1 ? x : -x;
        #else
        T x; cin >> x; return x;
        #endif
    }
    static int write_pos = 0;
    static char write_buf[buf_size];
    inline void writeChar(int x){
        if(write_pos == buf_size) fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
        write_buf[write_pos++] = x;
    }
    template <class T>
    inline void writeInt(T x, char end){
        if(x < 0) writeChar('-'), x = -x;
        char s[24]; int n = 0;
        while(x || !n) s[n++] = '0' + x % 10, x /= 10;
        while(n--) writeChar(s[n]);
        if(end) writeChar(end);
    }
    inline void writeWord(const char *s){
        while(*s) writeChar(*s++);
    }
    struct Flusher{
        ~Flusher(){ if(write_pos) fwrite(write_buf, 1, write_pos, stdout), write_pos = 0; }
    }flusher;
}
using namespace FastIO;

struct Line {
    mutable double k, m, p;
    bool operator<(const Line& o) const { return k < o.k; }
    bool operator<(double x) const { return p < x; }
};
struct LineContainer : multiset<Line, less<>> {
    // (for doubles, use inf = 1/.0, div(a,b) = a/b)
    const double inf = 1/.0;
    double div(double a, double b) { return a / b; }
    bool isect(iterator x, iterator y) {
        if (y == end()) { x->p = inf; return false; }
        if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
        else x->p = div(y->m - x->m, x->k - y->k);
        return x->p >= y->p;
    }
    void add(double k, double m) {
        auto z = insert({k, m, 0}), y = z++, x = y;
        while (isect(y, z)) z = erase(z);
        if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
        while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
    }
    double query(double x) {
        assert(!empty());
        auto l = *lower_bound(x);
        return l.k * x + l.m;
    }
} st1, st2;

ll n, a[202020], all;
double l[202020], r[202020];

pair<double, double> f[202020], g[202020];
double v1[202020], v2[202020];

void go(){
    st1.clear(); st2.clear();
    for(int i=1; i<=n; i++){
        double m = (l[i] + r[i]) / 2.0;
        st1.add(-f[i].x, -f[i].y);
        v1[i] = -st1.query(m);
    }
    for(int i=n; i; i--){
        double m = (l[i] + r[i]) / 2.0;
        st2.add(-g[i].x, -g[i].y);
        v2[i] = -st2.query(m);
    }

    for(int i=1; i<=n; i++){
        double m = (l[i] + r[i]) / 2.0;
        double now = (all - m*n) - v1[i] - v2[i];
        if(now <= 0) r[i] = m;
        else l[i] = m;
    }
}

int main(){
    n = readInt();
    for(int i=1; i<=n; i++) a[i] = readInt(), all += a[i];
    int mx = *max_element(a+1, a+n+1);

    ll sum = 0;
    for(int i=0; i<=n+1; i++) f[i] = {1-i, sum}, sum += a[i];
    sum = 0;
    for(int i=n+1; i>=0; i--) g[i] = {i-n, sum}, sum += a[i];

    for(int i=1; i<=n; i++) l[i] = a[i], r[i] = mx;
    for(int iter=1; iter<=42; iter++) go();
    for(int i=1; i<=n; i++) printf("%.8f\n", r[i]);
}