CodeForces Round 1012 - Div 1

https://codeforces.com/contest/2089

 

 

Performance Rating : 2500

 

A

예제에서 모두 2부터 나오길래 2부터 순차적으로 소수들이 최대한 많이 나오는 방법으로 배치하는 것을 고려해봤으나 $n$이 커질수록 $n/3-1$개보다 적은 개수가 나올 것 같다는 생각이 들었고 다른 방법을 찾기 시작했다. 특정 $p$에서 시작하여 $p, p-1, p+1, \cdots$ 이런식으로 배치하면 $c_i$를 $p$로 유지시킬 수 있다는 것을 알게 되었고 $n=1$인 경우에만 예외처리를 해준 뒤 $n/2$와 가장 가까운 $p$에서 시작하여 $p-x$, $p+x$를 계속 출력해주는 풀이를 작성했다.

 

B1

처음에는 $b_i$가 줄어들지 않는 것으로 생각하고 풀이를 짰다가 $b_i$도 줄어든다는 것을 보고 다른 풀이를 생각하기 시작했다. $a_i$가 $0$이 되는 순간이 언제인지 관찰을 해보니 $a_i+\cdots+a_j\leq b_i+\cdots+b_j$가 되는 순간이었다. 그렇다면 $v_i=a_i-b_i$로 해놓고 $v_i$의 연속합이 가장 긴 구간의 길이를 구하면 되겠다는 생각을 했고 원형이기 때문에 $a$와 $b$를 각각 2배로 늘려 $v$를 만들고 연속합이 가장 긴 구간의 길이를 구하였다. 문제에서 $c_i=a_{(i-1)\mathrm{mod}\;n}$이라고 쓰여 있는 것을 $c_i=a_{(i-1)} \mathrm{mod}\;n$으로 읽어 WA를 한번 받았다.

 

B2

파라매트릭 서치를 써야겠다는 생각이 강하게 들었다. $k$개를 적절히 분배하는 것 보단 특정 횟수 이하로 수행하기 위해 줄여야 하는 값을 구하는 것이 더 쉬워보였기 때문이다. $v$에 B1에서 $v$의 누적합을 저장해 두었다. $0\leq i\leq n-1$인 $i$에 대해 $v_i<\mathrm{min}(v_{i+1},\cdots,v_{i+l})$이면 $l$번 이하로 실행하기 위해 $a_{i+1}$을 $\mathrm{min}(v_{i+1},\cdots,v_{i+l})-v_i$만큼 줄여주어야 한다. 최솟값을 구하기도 해야하고 줄인 후에는 누적합을 바꾸어야 하므로 레이지 세그먼트 트리를 활용했다. 누적합을 바꿔주는 범위를 잘못 설정하여 WA를 한번 받았다.

 

C1

특정 사람이 틀렸을 때 다음 사람이 어떤 행동을 해야하는지 분석을 시작했다. 결국 두 번째 사람은 틀린 사람이 고른 두 개중 하나를 골라야 하고 두 번째 사람도 틀렸다면 세 번째 사람부터는 앞에서 고른 것 중 겹치는 것을 계속 골라나가야 한다. $x$개의 쌍이 남았을 때 첫 번째 사람부터 $1/x$의 확률로 열 수 있는데 $dp[i][j]$를 $i$번째 좌물쇠를 $j$번째 사람이 딸 확률로 정의하면 $j$번째 사람이 여는 좌물쇠의 기댓값은 $dp[1][j]+\cdots+dp[l][j]$가 된다. $dp$ 전이는 $(j+1)$번째 사람부터 시작하고 $(l-i)$개의 좌물쇠가 남았을 때 $x$번째 사람이 $i$번째 좌물쇠를 따게 될 확률에 $dp[i-1][j]$를 각각 곱하여 더해주는 과정을 반복했다. dp테이블의 원소 개수가 $nl$이고 한 번의 전이에 $n$번의 연산을 하므로 시간복잡도는 $O(n^2l)$으로 아슬아슬하게 통과할 것 같았다.

 

C2

솔브수와 남은 시간을 봤을 때 못풀 것 같다는 생각이 들었다. case를 분류하다가 너무 복잡하기도 하고 $O(n^2lk)$가 안돌아갈 것 같아서 풀지 못했다.