CodeForces Round 1018 - Div 1.5

https://codeforces.com/contest/2096

 

 

Performance Rating : 2400

 

A

'<'와 '>'의 의미를 잘못 파악하고 문제를 풀었다가 틀린 것을 확인하고 다시 풀어 9분이라는 많은 시간이 들어갔다. 문제를 잘 읽자.

 

B

생각보다 헷갈려서 고민을 하다가 $\mathrm{max}(a_i,b_i)$는 모두 더하고 $\mathrm{min}(a_i,b_i)$ 중 가장 큰 $k$개를 더하면 된다는 것을 알게 되었다.

 

C

처음에 하나의 행 또는 열에 여러 번 공사가 가능한 것으로 착각해 고민을 하다가 문제를 잘못 읽었음을 알게 되었다. 그 후에는 특정 행에서 수행하는 것은 열끼리 비교에서 영향을 주지 않는다는 것을 바탕으로 $dp$를 활용해 풀었다. 행과 열에 대해 $dp[i+1][j]$를 이전 행 또는 열에서 $i$만큼의 변화를 주었을 때 비용의 최솟값이라고 정의하면 약간의 구현을 통해 답을 구할 수 있다.

 

D

결국 불변하는 것을 구해야 한다는 생각을 했다. 아무리 수행을 해도 변하지 않는 것은 $x=t$ 위에 있는 점 개수의 기우성, $x+y=t$ 위에 있는 점 개수의 기우성이다. 이를 통해 기우성이 홀수인 $x$, $x+y$의 값을 구해 풀었다.

 

E

inversion counting을 먼저 구해주고 inversion counting을 $1$밖에 줄이지 못하는 수행을 최소화할 생각을 했다. 처음에는 앞에 $P$가 홀수개인 $B$가 다음 $B$ 사이에 짝수개의 $P$가 있으면 묶어서 옮기고 아니면 $1$을 더해주는 풀이를 작성했지만 틀렸다.  반례를 찾아보니  PBPBBPB가 있었는데 이 케이스는 가운데에 붙어있는 BB를 먼저 옮기면 모든 과정에서 inversion counting을 2씩 줄일 수 있다. 이를 관찰하고 두 번째 풀이를 작성했지만 틀렸고 반례를 고민하다가 구현의 문제일 수 있을 것 같아 스택을 활용한 구현으로 코드를 고쳐서 냈고 AC를 받았다.