CodeForces Round 939 - Div 2

https://codeforces.com/contest/1956

 

 

Performance Rating : 2950

 

A

문제의 설명이 길어서 문제를 이해하는데 시간이 오래걸렸다. 해석을 해보니 답은 $\mathrm{min}(a_1 - 1, n_i)$를 출력하면 되는 문제였다.

 

B

2개 존재하는 숫자의 개수가 정답이다.

 

C

가장 이상적인 해의 형태를 먼저 생각해 보았다. 예제에서도 볼 수 있듯이 $1$이 1개, $2$가 3개, $\cdots$, $n$이 $2n-1$개 존재하는 것이 최적일 것 같았는데 이를 만들 수 있는지를 생각해 보다가 $2i$번쨰 실행에서는 $i$번째 행을 $n, \cdots,1$로 만들고 $2i+1$번째 실행에서는 $i$번째 열을 $n, \cdots,1$로 만들면 예상한 최적의 해가 나온다는 것을 확인하여 제출했다.

 

D

$l$, $r$에 수행을 한번이라도 한다면 모든 숫자를 $r-l+1$로 만드는 것이 최선이다. 우선 재귀를 활용해서 $l$, $r$이 주어졌을 때 $a_l, \cdots,a_r$을 모두 $r-l+1$로 만든 과정을 찾는 함수를 작성해야 했다. $a_l, \cdots,a_r$을 모두 $r-l+1$로 만들기 위해서는 $a_i=i-l$로 설정하는 과정이 필요한데 이를 달성하는 함수를 먼저 작성했다. 이는 재귀적으로 해결할 수 있었는데 우선 $l=r$인 경우 $a_l=0$으로 만들어주고 아닌 경우에 대해서는 $[l+1,r]$을 재귀 호출한 뒤 $(l+1,r)$에 대해 한번을 더 수행하면 $a_r=r-l$로 만들 수 있고 마지막으로 $[l,r-1]$에 대해 재귀호출 해주면 완성이 된다. 이제 어떤 구간에 대해 수행을 해줄지 찾기 위해 dp와 백트래킹으로 어느 구간에서 수행을 할지 찾아 답을 구하였다. 

 

E1

E1과 E2의 차이가 $a_i$의 범위 차이라는 것이 큰 힌트가 됐다. 결국 $a_i=0$인 $i$를 기준으로 $a$를 분리했을 때 2개가 남으면 어떤 것이 살아남을지는 자명하게 결정된다는 점을 관찰했다. $a_i\leq 2\times 10^5$일 경우 1000번의 시뮬레이션을 해주면 3개 이상의 연속된 양수가 존재하지 않는다는 것을 증명했고 1000번을 시뮬레이션한 뒤 2개가 붙어있다면 앞의 인덱스를, 하나만 붙어있다면 그 인덱스를 출력했다.

 

E2

3개가 붙어있는 경우 계산을 통해 어떤 인덱스가 살아님을지 $O(1)$의 계산만으로 구할 수 있다는 것을 알게 되었고 $a_i\leq 10^9$일 때 1000번만 시뮬레이션을 하면 4개 이상의 연속된 양수가 존재하지 않을 것이라고 생각해 풀었으나 틀렸다. 고민을 해보니 2000번은 시뮬레이션을 해야 4개 이상의 연속된 양수가 존재하지 않는다는 결론이 나와 고쳐서 제출했으나 두 번째 WA를 받았다. long long을 사용한 것이 문제인가 싶어 __int128로 타입을 바꾸고 다시 제출했으나 세 번쨰 WA를 받고 고민을 시작했다. 세 개의 연속한 양수를 처리하는 부분에는 문제가 없다는 결론을 내렸으나 시뮬레이션 과정에서 3개의 양수 중 앞의 한두개만 하고 종료되는 경우가 있다는 것이 문제인 것 같아 시뮬레이션을 2000번 돌린 뒤 0을 만날 때까지 추가로 돌리는 것으로 코드를 고치고 제출하니 맞았다.