CodeForces Round 960 - Div 2

 

https://codeforces.com/contest/1990

 

 

 

Performance Rating : 2300

 

A

생각보다 풀이가 바로 생각나지는 않았다. 가장 큰 숫자가 홀수개라면 첫 턴인 사람이 이긴다는 것으로 생각을 시작했다. 가장 큰 숫자가 짝수개라면 두 번째 큰 수가 홀수개인지 보면 되는데 이 생각을 이어나가다 보니 홀수개인 숫자가 하나라도 있으면 첫 턴인 사람이 이긴다는 결론이 나왔다.

 

B

경우의 수가 많다는 것, 그리고 B번 문제라는 것을 생각하여 어느 정도 정형화 된 풀이가 존재할 것이라고 예상했다. $y<x$이므로 $a_y$부터 $a_x$까지는 모두 1로 채울 생각을 했다. 처음에는 $a_1$부터 $a_{y-1}$까지 $a_i=(-1)^i$으로 채우고 $a_{x+1}$부터 $a_n$까지 $a_i=(-1)^{n+i+1}$로 채우면 될 것이라고 생각했으나 $a_1$과 $a_n$을 -1로 맞추는 것이 아니라 $a_{y-1}$과 $a_{x+1}$을 -1로 맞추어야 한다는 것을 알게 되었고 고쳤다.

 

C

모든 숫자가 0이 될 때까지 시뮬레이션을 할 수는 없으므로 우선 관찰을 시작했다. 한 번 실행하고 나서부터는 $a$가 오름차순이 되므로 규칙을 파악할 수 있을 것 같았다. 우선 한 번 실행하고 난 뒤 $a_{i-1}<a_i$, $a_i=a_{i+1}$을 만족하면 과정을 진행함에 따라 $a_i$가 한 칸씩 오른쪽으로 가면서 계속 나타나게 되는 것을 관찰했다. 이를 활용하여 답을 구했는데 처음에 식을 잘못 세워 WA를 한번 받았다.

 

D

우선 $2\times 2$ grid가 매우 작다는 것을 생각한 뒤 예제를 봤다. 2번 예제가 4인 이유를 생각해 보니 $a_i$의 값이 2와 4를 기준으로 생각해야겠다는 생각이 들었다. 우선 $i$번째 행부터 $j$번째 행까지 모두 흰색으로 만들 때 행을 칠하는 연산보다 $2\times 2$ grid를 칠하는 연산을 할 때 이득이 되는 경우를 생각해 보았다. 결국  $a_i$, $a_j\leq 2$, $a_k(i<k<j)\leq 4$라는 조건이 만족되어야 한다는 것을 알게 되었다. 이를 바탕으로 $a_i=0$, $a_i\leq 2$, $a_i\leq 4$, $a_i>4$인 경우를 나누어 처리해 주었는데 위 조건에서 $i-j=1(\mathrm{mod}\;2)$를 만족해야 한다는 것을 빼먹어 WA를 한번 받고 $i-j=0(\mathrm{mod}\;2)$인 경우 처리를 잘못해 WA를 한번 받았다.

 

E1

이분탐색 비슷하게 하면 되는지 생각해보았으나 끝날 때까지 적절한 풀이를 떠올리지 못했다.