$$\newcommand{\Z}{\mathbb{Z}} \newcommand{\R}{\mathbb{R}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\N}{\mathbb{N}}\newcommand{\C}{\mathbb{C}} \newcommand{\oiv}[1]{\left] #1 \right[} \newcommand{\civ}[1]{\left[ #1 \right]} \newcommand{\ad}[1]{\text{ad}(#1)} \newcommand{\acc}[1]{\text{acc}(#1)} \newcommand{\Setcond}[2]{ \left\{\, #1 \mid #2 \, \right\}} \newcommand{\Set}[1]{ \left\{ #1 \right\}} \newcommand{\abs}[1]{ \left\lvert #1 \right\rvert}\newcommand{\norm}[1]{ \left\| #1 \right\|}\newcommand{\prt}{\mathcal{P}}\newcommand{\st}{\text{ such that }}\newcommand{\for}{\text{ for }} \newcommand{\cl}[1]{\text{cl}(#1)}\newcommand{\oiv}[1]{\left] #1 \right[}\newcommand{\interior}[1]{\text{int}(#1)}$$

BOJ 10532, USACO 2014 March Gold II Sabotage::::Gratus' Blog

BOJ 10532, USACO 2014 March Gold II Sabotage

카테고리 없음 2020. 7. 6. 02:17

난이도 : Solved AC 기준 Platinum 3

사용 알고리즘 : Binary Search (Parametric), Kadane Algorithm, etc...

 

1. 문제 설명

최대 10만 개의 정수 수열이 주어진다. 이 수열에서 중간의 연속된 Segment 하나를 들어내어 없앰으로써 (단, 처음과 끝에 있는 수는 없앨 수 없다), 남은 부분의 Average를 최소화하고자 한다.

 

2. 풀이

남은 부분의 Average를 minimize하는 것은 매우 특이한 작업인 데 비해, 남은 부분의 Sum을 minimize하는 것은 매우 쉬운 작업이다. 안쪽 구간 중 Maximum sum subarray를 찾으면 충분하고 이는 $O(n)$ 에 가능하기 때문이다. 이를 이용하여 Average를 빨리 구하는 발상은 생각하기 쉽지 않은 것 같다. (예전에 Codeforces에서 한번 본적이 있는데, 출처는 잘 기억이 안난다. ㅋㅋ)

다음과 같은 질문에 빠르게 답할 수 있다면, 최적화 문제를 결정 문제로 바꾼 형태이기 때문에, 이를 이용한 Parametric search를 생각해 볼 수 있다. 답이 최대 1만 정도이기 때문에, 이 질문 한 번에 수백만 번 정도까지 연산을 해도 ($n \log n$ 정도 시간에만 답할 수 있어도) 충분하다는 생각도 해보면 좋다.

Q. 남은 부분의 Average를 $X$이하로 줄일 수 있는가?

$a_1, a_2, \dots$의 원래 수열 대신, $a_1 - X, a_2 - X \dots $ 를 생각하자. 이 수열에서 남은 부분의 합을 최소화하려고 노력했을 때, 그 합이 음수가 되게 할 수 있다면, 그 부분의 Average는 $X$보다 작아지게 된다. 이는 Kadane's Algorithm (이름이 붙어 있어서 그럴듯해 보이지만, 그냥 Maximum sum subarray) 으로 $O(n)$에 구할 수 있다.

 

3. 코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define eps 1e-6
vector<double> cur;
double kadane(vector <double> &arr)
{
	int nn = arr.size();
	double lm = arr[1], gm = arr[1];
	for (int i = 1; i<nn-1; i++)
	{
		lm = max(arr[i], lm+arr[i]);
		gm = max(gm, lm);
	}
	return gm;
}
int32_t main()
{
    usecppio
    int n; cin >> n;
    for (int i = 0; i<n; i++)
    {
        double x; cin >> x;
        cur.push_back(x);
    }
    double lo = 1.0, hi = 1e4;
    while(abs(lo-hi)>1e-5)
    {
        double mid = (lo+hi)/2;
        vector <double> newv = cur;
        double tot = 0.0;
        for (auto &it:newv)
        {
            it -= mid;
            tot += it;
        }
        double msum = kadane(newv);
        if (msum > tot+eps)
            hi = mid;
        else lo = mid;
    }
    printf("%.3lf\n",lo);
}

 



admin