codeforces global round 13 C. Pekora and Trampoline
대회 중에 못 푼 문제입니다.
그리디한 관점에서 단순한 풀이는 떠올렸지만 연산량을 줄이지 못했습니다.

rating : 1700
tags : brute force , data structures , dp ,graphs,greedy, implementation

문제 요약

일렬로 n개의 트램펄린(이하 점프대)이 있습니다. i번째 점프대는 강도 S[i]를 가집니다. 한 pass를 정의합니다. 한 pass 동안 일어나는 일은 다음과 같습니다.
아무 점프대에 올라갑니다. i번째 점프대에 올라가면 i+S[i]에 있는 점프대로 점프해서 이동하게 됩니다. 그러고 나서 점프대의 강도 S[i]는 max(1,S[i]-1)로 줄어듭니다. 즉, 1이면 변동이 없고 그보다 크면 강도가 1만큼 감소합니다. 점프대가 없는 곳에 도착할 때 까지 계속합니다.(i>=n일 때까지)
이 때 모든 점프대의 강도를 1로 만들기 위해 필요한 최소 pass는 몇번인지를 구하는 것이 문제입니다.

해결

문제 특성상 + 그리디한 관점으로 왼쪽에 있는 1이 아닌것부터 강도 1로 만들어 가는 것이 최적입니다. 좀 더 관찰해 보면 i번째에서 강도가 1이 아니면 min(i+S[i],n-1) ~ i+2 사이의 모든 점프대로 부가적인 점프가 유발됩니다.
문제에 기술된대로 시뮬레이션을 하면 O(n^2*sqrt(n)) ? O(n^3)) ? 정도의 시간복잡도가 나오게 됩니다. 시간복잡도를 줄이기 위해 좀 더 그리디한 관점으로 보는 것이 필요합니다.
한 pass를 그대로 시뮬레이션 하지 말고 왼쪽에서 오른쪽을 기준으로 시뮬레이션하면 O(n^2)에 구현이 가능합니다.
배열에 pass에서 부가적으로 발생한 덤으로 생긴 공짜 점프들을 기록합니다. 누적합 방식입니다.
이 배열을 가지고 공짜 점프들을 최대한 사용해가면서 답을 만들면 최소 비용이 됩니다.

피드백

문제 이해 및 특징 파악 : 양호

문제 이해는 크게 어렵지 않았습니다. S는 큰데 n은 작다는 관찰을 할 수 있었습니다. 그래서 n보다 큰 S는 확확 줄일 수 있음을 파악했습니다. 점프대는 인덱스가 증가하는 방향으로만 점프하므로 앞에서부터 1이 아닌 점프대를 처리해 나가야 한다는 관찰도 했습니다. 이러한 관찰을 통해 O(n^2*sqrt(n)) 정도의 알고리즘은 설계할 수 있었습니다.
사실 시간복잡도를 줄일 핵심적인 그리디한 관찰잉 있었는데 못했기에 특징 파악은 70점 정도였다고 볼 수 있습니다.

연산량 감소 : 실패

처음에 큰 S만 n 범위로 줄이고 그대로 시뮬레이션하는 방식이 O(n^2) 알고리즘일 줄 알고 설계했는데 아니었습니다.
아래 입력을 처리하는데 오래걸리게 됩니다.

n=5000,
S = [5000 4999 4998 ... 3 2 1]

나중에 적당한 배열을 가지고 덤으로 생긴 점프들을 관리해주는 아이디어는 떠올렸습니다. 하지만 그 배열을 이용해서 연산량을 줄일 방법까진 생각해내지 못했습니다.

종합적으로 약점이 많이 드러났습니다.
1. 설계+구현력 부족 : 적절한 자료구조(배열,누적합)의 사용
2. 정확한 시간복잡도 판단 실패

적절한 자료구조를 이용하면서 동시에 그리디한 관점이 섞이면서 훨씬 더 어려웠던 것 같습니다. 문제 특성 파악에서 그리디한 관점을 적용해서 그게 끝인줄 알았는데 한 번 더 그리디한 관점이 필요했습니다. 이것도 생각지 못한 부분입니다.

int main() {
  ios_base::sync_with_stdio(false); cin.tie(nullptr);	

//	freopen("input.txt","r",stdin);
  int tc; cin>>tc;
  while(tc--){
      int n; cin>>n;

      vector<int> s(n);
      for(int i=0;i<n;i++) {
          cin>>s[i];
      }

      ll ans=0;
      ll loopcnt=0;
      vector<int> pre(n+2,0);	// accumulated jump count

      for(int i=0;i<n;i++){
          int d=s[i]-1-pre[i];
          if(d>0){	//here's needs >accumulated jumps  => need to trigger.
              ans+=d;
              pre[i]=s[i]-1;	//here newly triggered

          }else{ //here's needs <= accumulated jumps =>not need to trigger. just use made jumps
         //inherit last total triggered jumps after subtracting here's needed jumps
              pre[i+1] +=-d;
          }

          for(int j=i+2;j<=min(n-1,i+s[i]);j++) pre[j]++; // secondary triggered : free

//			pre[i+1]+=pre[i]-(s[i]-1);	

      }

      cout<<ans<<"\n";


  }


  return 0;
}