Codeforces Round 873 (Div. 2)

A. Divisible Array (800)Permalink

A. Divisible Array

$\displaystyle \sum_{i=1}^n i = \dfrac{n(n+1)}{2}$이므로 $2, 4, 6, 8, \dots$ 처럼 해주면 된다.

B. Permutation Swap (900)Permalink

B. Permutation Swap

$a_i=j$ 라고 할 때, $j$가 원래 있어야 할 위치는 $j$인데 $i$에 있는 것이므로 $p$는 $p \mid \vert j-i \vert$ 여야된다.

따라서 모든 $j$에 대하여 $\vert j-i \vert$들의 GCD가 정답이다.

C. Counting Orders (1100)Permalink

C. Counting Orders

$b_i$가 큰 순서대로 보면 $a$에 남아있는 $b_i$ 보다 큰 것의 개수를 정답에 곱해준다.

그리고 $a$에서 큰 것부터 하나씩 삭제한다.

이것이 가능한 이유는 $a$에서 남은 것 중 $b_i$ 보다 큰 것중에 아무거나 써도 정답의 경우의 수에 영향을 미치지 않기 때문이다.

D1. Range Sorting (Easy Version) (2000)Permalink

D1. Range Sorting (Easy Version)

이 문제는 아이디어가 어렵지 개수를 세는건 자료구조를 써서 쉽게 구현할 수 있다.

D2. Range Sorting (Hard Version) (2400)Permalink

D2. Range Sorting (Hard Version)

두 가지 관찰은 성공했지만 정확한 정답의 정의와 정답을 구하는 방법은 구하지 못해서 에디토리얼을 참고했다.

Observation 1Permalink

구간 $[l, r]$ 을 고려할 때, 최적의 해에선 어떤 교차하는 두 구간은 없다. 그렇다면 항상 그 두 구간을 하나로 합쳐주는 것이 이득이다.

Observation 2Permalink

구간 $[l, r]$에서 $l \le p < r$ 이 존재해 $\text{Max}{i=l}^p a_i < \text{Min}{i=p+1}^r a_i$라면$[l, p]$와$[p+1,r]$ 구간의 정답을 독립적으로 구해서 더해줄 수 있다.

IdeaPermalink

Observation 2에서와 같이 구간을 둘로 쪼갤 수 있는 pivot $p$를 찾았다면 우린 무조건 정답을 $r-l$에서 $1$감소시켜줄 수 있다.

즉, 가능한 $p$의 개수가 구간 $[l, r]$에 몇개가 있는지를 알면 $r-l$ 에서 그걸 뺀 것이 $[l, r]$ 에서의 beauty이다.

위 조건을 만족하는 $(l,p,r)$ 쌍들 중에 $0 \sim n-1$의 $i$에 대해 $\text{Min}(a[p+1, r])=a_i$ 인 $i$들을 고려한다.

즉, $[p+1, r]$ 구간에선 $a_i$가 가장 작고 $a_p$는 $a_i$ 보다 작아야 하므로 $i$의 왼쪽에서 $a_k < a_i$ 를 만족하는 가장 큰 $p$를 고려한다.

여기서 정의된 $p$를 $B$라고 하고 $i$를 $C$ 라고 하자. 그럼 모든 $i$마다 $(B,C=i)$ 를 구할 수 있다.

스택을 써서 $O(n)$에 구하자.

$A, D$를 정의해 $a_A>a_C, \ A < B$ 를 만족하는 $A$ 중 $B$와 가장 가까운 것으로,

$a_D < a_C \quad D > C$ 를 만족하는 $D$중 $C$ 와 가장 가까운 것이라고 하자.

$(l, p, r)$ 을 봤을 때 $A < l \le B$ 그리고 $C \le r < D$ 인 것이 위의 조건을 만족한다.

다시말해, 정답에 $(B-A) \cdot (D-C)$ 를 빼줄 수 있다.

처음에 정답은 모든 가능한 $r-l$의 합이다.

Idea 분석Permalink

$(B-A)(D-C)$ 가 정답에서 빼지게 되는 이유는 다음과 같다.

$(A,B,C,D)$ 가 있다면, $[A+1, B]$ 에서 아무거나 고르고 $[C, D-1]$ 에서 아무거나 고르고 그걸 $B', C'$라고 할 때

$(B-A)(D-C)$개의 구간들은 모두 $B$를 $p$로 하나씩 갖게 되는 것이다.

구현Permalink

$A$를 찾는데는 $B$에서부터 왼쪽으로 $C$ 보다 작은것까지 계속 진행해야하므로 Sparse Table 을 쓸 수 있다.

$C$를 갖고 $B,D$ 를 찾는건 스택으로 가능하다.

시간복잡도는 $O(n \log n)$인데 $B$도 두 개의 스택으로만 찾아서 $O(n)$ 도 가능하다고 한다.

못 푼 원인Permalink

$(l, p, r)$ 이 있을 때 $(l, r)$ 을 고정시키고 $p$가 몇개인지를 구할 수 없는 문제였다.

반대로 $p$를 기준으로 $l, r$ 이 어디까지 이어지는지를 파악해야 했다.

경우의 수 문제에서 이처럼 $[l,r]$에서 $x$가 몇개가 있는가를 구하는 문제에서 $x$ 를 가질 수 있는 구간 $[l, r]$ 은 어디일까를 반대로 생각하는 것은 중요한 테크닉같다.

void solve() {  
   int n, ans = 0;  
   cin >> n;  
   vi a(n + 2);  
   a = vi(n + 2);  
   for (int i = 1; i <= n; i++) {  
      cin >> a[i];  
      ans += i * (i - 1) / 2;  
   }  
   a[0] = -2e15;  
   a[n + 1] = -2e15;  
  
   int LOG = 20;  
   vvi mx(LOG, vi(n + 2));  
   for (int i = 0; i <= n; i++) mx[0][i] = a[i];  
   for (int k = 1; k < LOG; k++)  
      for (int i = 0; i + (1 << k) - 1 <= n; i++)  
         mx[k][i] = max(mx[k - 1][i], mx[k - 1][i + (1 << (k - 1))]);  
  
   vi left_first_small(n + 2), right_first_small(n + 2);  
   stack<int> s;  
   s.push(0);  
   for (int i = 1; i <= n; i++) {  
      while (a[s.top()] > a[i]) s.pop();  
      left_first_small[i] = s.top();  
      s.push(i);  
   }  
   s = stack<int>();  
   s.push(n + 1);  
   for (int i = n; i >= 1; i--) {  
      while (a[s.top()] > a[i]) s.pop();  
      right_first_small[i] = s.top();  
      s.push(i);  
   }  
   for (int C = 1; C <= n; C++) {  
      int B = left_first_small[C];  
      if (B != -1) {  
         int A = B;  
         for (int k = LOG - 1; k >= 0; k--)  
            if (A - (1 << k) >= 0 && mx[k][A - (1 << k) + 1] < a[C])  
               A -= (1 << k);  
         int D = right_first_small[C];  
         ans -= (B - A) * (D - C);  
      }  
   }  
  
   cout << ans << endl;  
}

E. Palindrome Partition (2600)Permalink

E. Palindrome Partition

F. Two Centroids (2800)Permalink

F. Two Centroids