[알고리즘] Codeforces Global Round 19

이번에 본대회를 참가할 수 없어서 버추얼에 참가했다.

괜찮은 성적

A - Sorting Parts [Solved!]

길이가 $n$인 배열이 주어질 때 $1\le i\le n-1$를 정해 $[a_1,\dots,a_i], [a_{i+1},\dots,a_n]$를 정렬하여 이어붙일 때 내림차순이 아닌 배열을 만들 수 없는지 묻는 문제이다. (오름차순이 아닌 배열을 만들 수 있는지 묻는 문제)

 

주어진 배열이 이미 오름차순이라면 내림차순이 아닌 배열(오름차순)을 만들 수 있다.

 

B - MEX and Array [Solved!]

배열을 $k$개의 구간으로 적당히 나누어 $cost  = c+\sum_{i=1}^c mex(\{ b_{l_i}, b_{l_{i+1}}, \dots, b_{r_i}\})$ 라고 하자. 배열의 모든 부분배열에 대해 $cost$의 합을 각각 구해 합했을때의 최댓값을 구하는 문제이다.

 

구간의 길이를 1로 하여 $cost$를 구하면 최대가 된다.

(최소를 구하는 문제인줄 알고 시간을 좀 날렸다.)

 

C - Andrew and Stones [Solved!]

돌더미가 있을 때 $1\le i<j<k\le n$을 정해 $j$번째 더미에서 $2$개를 꺼내 $i,j$번째 더미에 각각 $1$개씩 준다. 이 작업을 반복하였을 때 $1, n$번째 더미에만 돌이 있게 할 수 있는 최소 횟수를 구하는 문제이다.

 

우선 초기 배열에서 $j$로 가능한 값이 $1$만 있을 경우 만들 수 없다.

또한 길이가 $3$인 배열은 $j$로 가능한 값이 1개이므로 그 값이 홀수인 경우에도 만들 수 없다.

그 외의 경우는 모두 만들 수 있는데 $\lfloor \frac{a_j}{2} \rfloor$값들을 더한 뒤 홀수의 개수를 더하면 된다.

(관찰로만 풀어서 증명은 생략한다.)

 

D - Yet Another Minimization Problem

WIP