Codeforces Round 665 (Div. 2)

:god: tlsdydaud1님이 세팅하신 라운드이다. 역시 버츄얼로 돌았다.

A. Distance and Axis (0:03, +)

\(A\)의 위치는 \(x = 2y+k\)꼴이 되어야 한다. \(n\)이 \(k\) 미만이면 \(k\)까지 옮기고, 아니면 최대 1칸 이동해 조건을 만족시킬 수 있다.

 

B. Ternary Sequence (0:10, +)

비용이 2-1인 경우와 1-2인 경우가 아니라면 다 0이라는 것을 알 수 있다. 따라서 2를 최대한 써주고 -2를 최소한으로 쓰면 된다.

 

C. Mere Array (0:15, +)

최솟값을 \(m\)이라 하자. \(gcd(m,mk)=m\) 이므로 \(m\)의 배수들끼리는 위치를 자유롭게 바꿀 수 있다. 따라서 \(m\)의 배수들끼리 정렬해준 후 전체 배열이 정렬되었는지 확인하면 된다.

 

D. Maximum Distributed Tree (0:39, +3)

약간 전형적인 유형인데, 여러가지로 많이 말렸다. 우선 정점에 숫자를 적는 줄 알아서 한 번 말렸고, 다 짠 후에는 \(m > n-1\)일 때의 처리를 잘못해서 많이 틀렸다. 각 간선의 사용 횟수를 Tree DP 등으로 구해줄 수 있고, 재배열 부등식에 의해 횟수가 많은 것부터 그리디하게 매칭해주면 된다. \(m \leq n-1\)일 때는 빈 자리만큼 1을 넣어주면 되고, \(m > n-1\)일 때는 큰 수들을 모아 곱해주고 한 번에 사용하면 된다.

 

E. Divide Square (1:23, +1)

각 선분이 벽에 항상 닿는다는 점 때문에, 가로선과 세로선이 만나면 항상 하나의 직사각형이 생긴다. 따라서 x좌표를 따라 스위핑하면서, 가로선은 해당하는 y좌표에서 세그에 추가/삭제로 처리해주고, 세로선은 해당 범위의 가로선 개수를 구해 답에 더해주면 된다. 약간의 예외 처리가 필요하긴 한데, 잘 해주자.

 

F. Reverse and Swap (upsolved)

어디서 많이 본 세팅이다. 관찰을 통해 이 문제로 바꿔줄 수 있다. 일단 이 관찰이 꽤 오래 걸렸고, 저 문제를 본 대회때 뭔가 다른 풀이로 풀었던 것이 기억나서 정해로 다시 짜려다 보니 대회 시간 안에는 풀지 못했다. 2번과 3번 쿼리가 저 문제와 어떻게 연결되는지 생각해보자. 굉장히 좋은 문제라고 생각한다.