CodeForces Round 945 - Div 2

https://codeforces.com/contest/1973

 

 

Performance Rating : 2150

 

A

3개의 수의 합이 홀수라면 불가능하고, 짝수라면 $\mathrm{min}(sum/2,p_1+p_2)$를 출력했다.

 

B

$a_i|\cdots|a_j=(a_i|\cdots|a_{j-1})|(a_{i+1}|\cdots|a_j)$라는 점을 활용하면 $k$에서 성립한다면 $k+1$에서는 성립할 것이므로 파라메트릭 서치를 사용할 생각을 했다가 한 번의 판단에 $O(n^2)$의 시간이 드는 것을 확인하고 다른 방법을 찾기 시작했다. 비트연산이므로 비트별로 보면 되지 않을까 생각하던 중 각 자리의 비트별로 $1$인 수가 하나라도 있으면 연속한 $0$의 최장길이+1 만큼의 길이가 필요하다는 것을 관찰하여 풀었다.

 

C

처음에는 모든 항이 $n+1$이 되도록 맞춰둘 생각을 했으나 답이 보이지 않아 다른 방법을 생각했다. 결국 $n/2-1$개를 만들 수 있을 것 같다는 생각이 들었고 홀수 번째 항과 짝수 번째 항을 나누어 생각해 보았다. $n$이 포함되어 있는 항과 인덱스 기우성이 같은 항들을 극대로 만들 생각을 해보니 각 항에 작은 항부터 $n$, $\cdots$, $n/2+1$을 더해주고 나머지 항들에는 큰 항부터 $1$, $\cdots$, $n/2$를 더해주면 극대를 많이 만들 수 있다는 것을 찾았다.

 

D

$ask(1, n\dot mx)$를 $mx$를 $n$부터 줄여가면서 물어보는 것으로 $a_i$ 중 최댓값을 찾을 수 있겠다는 생각을 했다. $m$의 값이 $mx$의 배수가 될 것이라는 생각까지는 했으나 $m$이 $mx(n/k)$ 이하가 된다는 것을 생각하지 못했고 E로 넘어갔다.

 

E

$(n+1)$이 포함된다면 $l\neq r$이기만 하면 된다는 것을 예제로부터 관찰했다. 앞에서부터 $pre$개가 맞는 위치에 가있고 뒤에서부터 $suf$개가 맞는 위치에 가있다고 하면 가능한 $(l,r)$ 조합은 $n-suf+1\leq x\leq n+pre+1$을 포함하는 $l<r$인 것의 개수라고 생각을 했다. 이를 세는 방법은 $ \binom{2n+1}{2}- \binom{n-pre}{2}- \binom{n-suf+1}{2}-suf-pre-1$인데, 이렇게 답을 작성하니 몇몇 예제가 1 차이로 답이 틀린 것을 확인할 수 있었다. $l=r$이어도 가능한 경우가 있기 때문이었는데, 이 경우에 1을 더해주는 코드를 작성했고, 처음부터 정렬이 되어있는 경우는 $ \binom{2n+1}{2}$를 출력하도록 했는데 틀렸고 1시간 동안 틀린 부분을 찾아내지 못해 D로 못 돌아가고 끝났다. 버추얼이 끝나고 틀린 테스트 케이스를 보니 $l=r$이어도 가능한 경우를 판단할 때 $a_i+a_j$가 일치하는지 여부만 봤는데 $2 1 4 3$과 같은 예시에서는 $a_i+a_j=5$로 모두 같지만 $l=r=5$일 경우 정렬이 안된다는 것을 빼먹은 것이었다.