[Codeforces] Codeforces Round #789 후기

https://codeforces.com/contest/1677

 

SNUPS 개강총회가 끝나고 좀 제정신이 아니어서 코포를 하지 말까 하다가, 오랜만에 있는 div1이라 그냥 치기로 했다. 최근 두 번의 div1을 참여 안 했기 때문에 이번에도 안 하면 코포 공백이 너무 길어져서... 

개강 이후에도 ARC와 AGC는 모두 참여했었지만, 별로 후기를 올리고 싶은 대회는 없었다. (사실 딱 한 번 있었는데 인스타에 올리고 귀찮아서 여기엔 안 올렸다.)

오늘 문제는 다행히(?) 조합 문제 위주여서 하드 코딩이 필요 없었다. 그리고 전체적으로 문제들도 무난했던 것 같다. 나도 (D에서 있었던 예외처리를 빼면) 그냥 무난무난하게 풀었다. 덕분에 적당한 등수로 마감했고, 54가 올라 IM이 되었다.

 

A

여러 풀이가 있겠지만 $\displaystyle c_{i,j}=\sum_{k=j}^{n} [p_i>p_k], s_{i,j}=\sum_{k=1}^{i} c_{k,j}$라 정의하면

$\displaystyle ans=\sum_{i=1}^{n-3} \sum_{j=i+2}^{n-1} [p_i < p_j] \cdot (s_{j-1,j+1}-s_{i,j+1})$이다.

 

B

행과 열을 따로 생각하자.

1열만 생각하자. $nm$ 크기의 binary string $s$가 주어졌을 때, $c_i=(c_{i-m}) \vee (s_i)$는 1열의 좋고 나쁨을 나타낸다.($i \leq 0 : c_i=0$)

열에 의한 답 배열은, $c$ 배열을 $0, 1, 2, \cdots , m-1$ 만큼 뒤로 미룬 것들의 합이 됨을 쉽게 알 수 있다. 즉, $\displaystyle sc_i=\sum_{k=i-m+1}^{i} c_k$가 열에 의한 답 배열이다. 이는 누적합으로 빠르게 계산할 수 있다.

행도 비슷한데, 여기서는 $\displaystyle r_i= \vee_{k=i-m+1}^{i-1}r_k \vee s_i$이고 행에 의한 답 배열은 $r$ 배열을 $0, m, 2m, \cdots , (n-1)m$ 미룬 것들의 합이므로 $\displaystyle sr_i=sr_{i-m}+r_i$라 하면 쉽게 구할 수 있다.

$sc_i+sr_i$를 출력하면 된다.

 

C

permutation으로 생각하고 orbit들을 생각하자.

$sz_i$를 $i$번째 orbit의 크기라고 하면, 이 orbit에는 $\lfloor sz_i/2 \rfloor$개의 local max와 local min이 있다.

이를 고려하면 답은 $\displaystyle c=\sum \lfloor sz_i/2 \rfloor$라 할 때 $2c(n-c)$임을 쉽게 알 수 있다. (local max에서 local min으로만 연결된다고 생각해보자.)

 

D

예전에 풀었던 버블정렬 문제와 비슷한 아이디어를 사용하여 쉽게 접근할 수 있었다. 한 번의 operation이 있을 때마다, 각 원소의 $v$값은 양수라면 1씩 감소한다. 때문에, 최종 $v$값이 양수인 경우 그 숫자의 원래 $v$값은 결정되어있고, $0$인 경우와 $-1$인 경우만 고려해보자.

우선 $0$인 경우에서 맨 뒤의 $k$개 중 하나인 경우가 있다. 이 경우 $i > n-k$번째 원소는 $i$임이 자명하므로, $v$ 값은 $[0, n-i]$가 가능하다. 즉, $v$값으로 가능한 경우의 수가 $n-i+1$가지이다.

$0$이면서 위의 경우가 아닌 경우, $i \leq n-k$번째 원소의 $v$값은 $[0, k]$가 가능하다. 즉, $v$ 값으로 가능한 경우의 수가 $k+1$이다.

$-1$인 경우, $i \leq n-k$번째 원소의 $v$값은 $[0,i+k-1]$가 가능함을 쉽게 알 수 있다. 즉, $v$ 값으로 가능한 경우의 수가 $i+k$이다.

위 세가지 경우는 독립적이고, 임의로 위의 조건을 만족하도록 $v$값을 정했을 때, 즉 inversion sequence가 정해졌을 때 자명하게 원래 배열도 정해진다. 따라서 위 세 가지 경우를 잘 나눠 경우의 수를 모두 곱해주면 답이 나온다.

여담으로 불가능한 경우를 예외처리해야 하는데, 입력으로 $v_i \leq i-1$이 들어와 앞쪽은 해줄 필요 없고 뒤쪽의 $k$개가 모두 $0$ 또는 $-1$인지 확인해야 한다. 내 생각에는 문제 description에 따라 최소한 한 개의 복구가능한 배열이 있어야 할 것 같은데.. 이것 때문에 패널티를 먹어서 좀 억울하다.