[BOJ 28355] 무한 수열

https://www.acmicpc.net/problem/28355

28355번: 무한 수열

 

- 문제 요약

 

세훈이는 생일 기념으로 N개의 정수로 이루어진 수열 A를 선물로 받았다.  (A_i < 2^31 )$ 

하지만 수열의 길이가 너무 짧다고 생각한 세훈이는 다음과 같은 방식으로 무한히 긴 수열을 만들기로 했다.

우선 수열 A를 무한히 이어 붙인 뒤, 모든 양의 정수 i에 대해 i번째 수에서 i를 뺀다.

수열의 길이가 길어졌음에 만족한 세훈이는 이렇게 만들어진 수열에서 연속된 몇 개의 수를 선택해서 더해보기로 했다.

물론 큰 것을 좋아하는 세훈이는 이러한 합을 최대로 만들고 싶어졌다.

예를 들면, 수열 A가 [9, 1, 7]이었다면, 새로 만들어진 수열은 [8, -1, 4, 5, -4, 1,...]가 되고, 이 수열의 최대 연속합은 1번째 수부터 4번째 수까지의 합인 8−1+4+5=16이 된다.

 

 

- 알고리즘 정리

 

새로 만든 수열을 B라고 할 때, B는 연속된 N칸의 값이 규칙적으로 감소하고 있다는 걸 확인할 수 있습니다.

S를 B1 ~ BN의 합이라고 했을 때, B2 ~ BN + 1의 합은 S - B1 + BN + 1 = S - N이 됩니다.

이를 바탕으로 B에서 연속된 N칸의 합이 음이 아닌 수가 되는 가장 오른쪽에 있는 구간 [ p, p + N )을 찾으면 됩니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 500001
typedef long long ll;
ll n,arr[MAX],S,result;

ll f(ll x){
	return x*(x+1)/2;
}
tuple<ll,ll,ll>mxs(const vector<ll>&v){
    ll mx=0,le=0,ri=0;
    ll vm=0,vl=0,vr=0;
    for(int i=0;i<v.size();i++){
    	vm=max(0LL,vm)+v[i];
		mx=max(mx,vm);
	}
    for(int i=0;i<v.size();i++){
    	vl+=v[i];
		le=max(le,vl);
	}
    for(int i=(int)v.size()-1;i>=0;i--){
    	vr+=v[i];
		ri=max(ri,vr);
	}
    return {mx,le,ri};
}

int main(){
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    cin>>n;
    for(int i=1;i<=n;i++){
    	cin>>arr[i];
	}
    S=accumulate(arr+1,arr+n+1,0LL);
    vector<ll>v;
    for(int i=1;i<=n*4;i++){
    	v.push_back(arr[(i-1)%n+1]-i);
	}
    result=max(result,get<0>(mxs(v)));
    ll k=(2*S+n*n-n)/(2*n*n);
    if(k<=4){
		cout<<result;
		return 0;
	}
    vector<ll>le,ri;
    for(int i=1;i<=n+n;i++){
    	le.push_back(arr[(i-1)%n+1]-i);
	}
    for(int i=1;i<=n+n;i++){
    	ri.push_back(arr[(i-1)%n+1]-(k-1)*n-i);
	}
    ll sum=S*(k-3)-f((k-1)*n)+f(2*n);
    result=max(result,get<2>(mxs(le))+sum+get<1>(mxs(ri)));
    cout<<result;
}