Codeforces Round #633 (Div. 1) A.powered addtion

문제

길이가 n인 어떤 수열 a와 시간 x초가 주어집니다. 1~x초 동안 각 t(1<=t<=x)초 마다 2^(t-1)을 수열의 어떤 원소들에 한 번씩 더하거나 더하지 않을 수 있습니다. 수열 a를 비내림차순으로 만드는데 최소 몇초가 걸리는지 알아내는 문제입니다.

rating : 1500
tag : greedy , math

접근

그리디한 관점 + 약간의 예시를 통한 추론으로 수열에서 뒤에 있는 수의 증가가 많이 필요해 보였고, 가장 큰 차이만 극복되면 그보다 작은 차이는 모두 처리될 수 있다고 생각했습니다. 100퍼센트 확신은 없었지만 80퍼센트 정도는 확신이 있었습니다.

어려움

지문 이해

처음에 문제 지문을 이해하는데 조금 어려웠습니다. 문제에서 임의로 뽑은 인덱스를 i[j]로 표현하는데 j는 또 1~k로 주어졌어서 의미를 생각하지 않고 읽으면 이해하기가 좀 어려웠습니다.
"Note that you are allowed to not select any indices at all." 라는 의미심장한 문구도 있어서 더 어려울거라 생각했던 것 같습니다.

구현 착각

계속 틀려서 오버플로우 문제인가해서 long long 타입으로 고쳐도 틀렸습니다. 결국 테스트케이스를 확인해보니 엉뚱한 답이 나오고 있었습니다. 코드를 다시 보니 t초에 2^(t-1)이 더해지는 걸 t가 더해진다고 착각했습니다. 그래서 x*(x+1)/2 이 공식으로 더해질 수 있는 최대합을 구했습니다.
2^x-1로 계산했어야 했습니다.

피드백

해결하고 보니 어려운 문제가 아니었고 방법도 맞았었는데 너무 덤벙댔던 것 같습니다. 1500점 정도의 문제는 간단한 특징만 캐치하면 간단히 풀리는 건데.. 다만 그리디적인 생각에 100퍼센트 확신이 없었다는 점에서 틀릴만 했다는 생각도 듭니다.

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	
	int tc; cin>>tc;
	while(tc--){
		//가장 큰 차이만 극복되면 된다?
		
		int n; cin>>n;
		vector<ll> a(n);
		for(ll &i:a) cin>>i;
		
		
		vector<ll> pre(n+1,-1e17);	//prefix max
		vector<ll> suf(n+1,1e17); //suffix min
		
		for(int i=0;i<n;i++) pre[i+1]=max(pre[i],a[i]);
		for(int i=n-1;i>=0;i--) suf[i]	= min(suf[i+1],a[i]);
		
		
		ll mxdiff=0;
		for(int i=1;i<=n;i++){
			mxdiff=max(mxdiff,pre[i]-suf[i]);
		}
		
		
		ll t=0;
		for(;(1ll<<t)-1<mxdiff;t++){
			//cout<<t*(t+1)/2<<'\n'; //  error
		}
		
		cout<<t<<'\n';
	}

}