[USACO Gold 2014 March] Sabotage (BOJ 10019)

문제 링크

 

문제 요약

prefix와 suffix를 잡는데, prefix length + suffix length < n이어야 한다. (단, prefix length와 suffix length는 모두 1 이상이어야 한다.)

이 때, (prefix sum + suffix sum) / (prefix length + suffix length)를 최소화시키는 문제이다.

 

Solution 1: 파라메트릭 서치

파라메트릭 서치를 떠올리고 나면 푸는 것은 크게 어렵지 않다.

#include <bits/stdc++.h>
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
using namespace std;

const int N = 1e5+3;
int n, m[N];
double ans, avg, b[N], p[N], s;

bool valid(double x) {
    rep(i,1,n) {
        b[i] = m[i]-x;
        p[i] = p[i-1]+b[i];
    }
    s = p[n];
    double Mp = -1e9;
    for (int i = n-1; i >= 1; --i) {
        if (Mp-p[i] > s) return true;
        Mp = max(Mp,p[i]);
    }
    return false;
}

int main() {
    scanf("%d", &n);
    rep(i,1,n) scanf("%d", &m[i]);
    ans = (accumulate(m+1,m+n+1,0.0)-*max_element(m+2,m+n))/(n-1);
    avg = accumulate(m+1,m+n+1,0.0)/n;
    double a = 0, b = avg, m;
    rep(_,1,80) {
        m = (a+b)/2;
        if (valid(m)) b = m;
        else a = m;
    }
    if (abs(a-avg) < 1e-9) printf("%.3lf", ans);
    else printf("%.3lf", min(ans,a));
}

 

Solution 2: 볼록다각형 접선 테크닉

처음 써봤다. 유사코 공홈에 나와있는 별해로 소개되어 있었다.

볼록껍질을 반복마다 조금씩 구성해나가는 디테일이 조금 까다롭다.

#include <bits/stdc++.h>
using namespace std; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
using P = complex<ll>;
#define X real()
#define Y imag()
#define cross(u,v) (conj(u)*(v)).Y
int ccw(P a, P b, P c) {
    auto v = cross(b-a,c-b);
    if (v < 0) return -1;
    else if (v > 0) return 1;
    return 0;
}

const int N = 1e5+3;
int n, k[N];
P p[N], q[N], lo[N];

int main() {
    scanf("%d", &n);
    rep(i,1,n) scanf("%d", &k[i]);
    rep(i,1,n) {
        p[i] = {-i,p[i-1].Y-k[i]};
        q[i] = {i,q[i-1].Y+k[n-i+1]};
    }
    int l = 1;
    double ans = 1e9;
    per(i,1,n-1) {
        int a = 1, b = l-1, m;
        if (a <= b) {
            while (a <= b) {
                m = (a+b)/2;
                if (m+1 < l and ccw(p[i],lo[m],lo[m+1]) < 0) a = m+1;
                else b = m-1;
            }
            ans = min(ans,double(lo[a].Y-p[i].Y)/(lo[a].X-p[i].X));
        }
        while (l > 2 and ccw(lo[l-2],lo[l-1],q[n-i]) <= 0) --l;
        lo[l++] = q[n-i];
    }
    printf("%.3lf", ans);
}

 

 

UPD - https://koosaga.com/162 이런 글이 있었다!!