CodeForces Round 1015 - Div 1.5

 

https://codeforces.com/contest/2084

 

 

 

Performance Rating : 2500

 

A

$n$이 짝수일 때에는 $-1$, $n$이 홀수일 때에는 $n,1,\cdots,n-1$을 출력하는 코드를 작성하였다. $n$이 짝수일 때 안 되는 이유를 증명하지는 않고 proof by AC로 했다.

 

B

우선 $\mathrm{gcd}(a_{i+1},\cdots,a_n)$는 $\mathrm{min}(a_{i+1},\cdots,a_n)$이하이므로 $a_i$ 중 최솟값은 좌변에 들어가야 한다는 생각을 했다. 그러면 $a_i$ 중 최솟값을 구해놓고 나머지 중 구한 최솟값의 배수인 것들은 모두 우변에 넣는 것이 최선이므로 최솟값의 배수인 숫자들의 최대공약수를 구해 최솟값과 일치하는지를 확인하여 답을 구했다.

 

C

$a_i=b_{n-i+1}$, $a_{n-i+1}=b_i$여야 하므로 $a_i=b_i$인 개수가 $n\&1$과 같아야 하므로 이를 먼저 확인했다. 그 후 $(x,y)$와 $(y,x)$가 모두 있는지 확인해 주면서 map에 $(x,y)$의 인덱스를 저장해 두는 방식으로 바꿔야 하는 인덱스를 찾아나갔다.

 

D

$k$개의 연속한 숫자를 $m$개 골라서 뺐을 때 남은 것들의 $\mathrm{mex}$ 값이 최대가 되도록 해야 한다. 처음에는 $k$격으로 $m+1$개씩 반복하는 숫자를 최대한 많이 만드는 풀이를 작성했으나 WA를 받고 생각해 보니 $n=8$, $m=1$, $k=3$인 경우에 잘못된 답을 내놓는 것을 확인했다. 따라서 $m+1$번 반복할 수 있는 가장 큰 숫자를 구해놓고 이를 $m+1$번 반복시킬 생각을 하고 $n<(m+1)k$인 경우에는 따로 예외처리를 해주었다.

 

E

각 subsegment별로 모든 permutation에서 $\mathrm{mex}$의 값 합을 구하면 복잡도가 $O(n^2)$로 딱 맞겠다는 생각을 했다. 우선 $\mathrm{mex}$의 값은 바깥에 포함된 가장 작은 수라는 점을 활용해야겠다는 생각을 했다. subsegment 안에 있는 $-1$의 개수와 바깥에 있는 숫자 중 최솟값 두 개의 값이 중요하다는 것을 알게 되었다. 그래서 $cnt[i][j]$에 $-1$ 중 $i$개를 선택했을 때 $j$번째로 작은 수가 최솟값일 경우의 수, $dp[i][j]$에는 $cnt[i][j]\times v_j$의 누적합을 저장하였다. 이렇게 하면 각 subsegment에 대해 바깥에 있는 $-1$의 개수와 바깥에 있는 숫자 중 최솟값을 바탕으로 누적합과 이분탐색을 통해 답을 구할 수 있다.