Codeforces Round 865 (Div. 2) - C. Ian and Array Sorting (1300)

C. Ian and Array Sorting

내 풀이

오른쪽으로 한번 갔다가 왼쪽으로 한번 돌아오며 만들 수 있는지를 검사한다.

$i=0$ 부터 시작일 때 $i \coloneqq 1 \to n-2$ 까지 보며 $a_i < a_{i-1}$ 이라면 $d=a_{i-1}-a_i$ 를 $a_i$와 $a_{i+1}$ 에 더해준다.

반대도 유사하게 한다.

이 과정에서 non-decreasing array를 만들 수 있다면 YES이다.

그냥 직관으로 풀었다.

void solve() {  
   int n;  
   cin >> n;  
   vi a(n);  
   fv(a);  
   for (int i = 1; i < n - 1; i++) {  
      if (a[i] >= a[i - 1]) continue;  
      int d = a[i - 1] - a[i];  
      a[i] += d;  
      a[i + 1] += d;  
   }  
   if (a[n - 1] >= a[n - 2]) {  
      cout << "YES\n";  
   } else {  
      for (int i = n - 2; i >= 1; i--) {  
         if (a[i] <= a[i + 1]) continue;  
         int d = a[i] - a[i + 1];  
         a[i] -= d;  
         a[i - 1] -= d;  
      }  
  
      if (a[0] <= a[1]) {  
         cout << "YES\n";  
      } else cout << "NO\n";  
   }  
}

에디토리얼 풀이

$a_2-a_1, a_3-a_2, \dots$ 를 고려한다.

non-decreasing array라면 이 값들이 모두 $0$ 이상이다.

$b_i=a_{i+1}-a_i ~ (0 \le i <n-1)$ 을 고려한다.

$a_i, a_{i+1}$ 을 $1$ 증가시키면 $b_i$은 $1$ 감소하고 $b_{i+2}$ 는 $1$ 증가한다.

$1$ 감소시키면 반대이다.

$b$ 의 합을 고려한다.

$n$이 짝수이고 $b$의 합이 음수인 경우만 NO 이다.

$n$이 홀수라면 가령

a=5 4 3 2 1

여서 b=-1 -1 -1 -1라 하자.

우린 $b_2$ 이나 $b_{n-2}$ 을 무한히 증가시킬 수 있다.

$a_1, a_2$ 를 계속 더하거나 $a_{n-1}, a_n$ 을 계속 빼면 된다.

따라서 $+1, -1$ 을 $b$ 에서 계속 같은 parity에 대해 전파시킬 수 있어서 모두 $0$ 이상이 되게 할 수 있다.

$n$ 이 짝수라면 다음과 같은데,

$a=2,1,4,3$ , $b=-1,3,-1$

중앙의 $3$ 은 여전히 무한히 증가시킬 수 있지만, 나머지 $-1, -1$ 은 $+1, -1$ 을 해줘도 합이 항상 일정해서 제일 처음에 $0$ 이상이지 않으면 불가능하다.

그렇지 않으면 항상 일련의 연산을 통해 모두 값을 분배시켜줄 수 있다.

void solve() {  
   int n;  
   cin >> n;  
   vi a(n);  
   fv(a);  
   if (n % 2 == 1) {  
      cout << "YES\n";  
   } else {  
      int sum = 0;  
      for (int i = 1; i < n; i += 2) sum += a[i] - a[i - 1];  
      if (sum >= 0) cout << "YES\n";  
      else cout << "NO\n";  
   }  
}