[2020-09-13] Codeforces Round 576 (Div.1)

 

A에서 좀 헤맨게 아쉽지만 그래도 B,C는 깔끔하게 푼 것 같다. D는 풀이를 생각했음에도 불구하고 시간복잡도가 안 된다고 생각해서 시도를 안했다.. 이게 너무 아쉽다. O(N^5)가 안 된다고 생각해서 O(N^4)로 어떻게 줄여야할지를 한참 고민했는데, 생각해보면 O(N^5)는 맞는데 쌩 N^5가 아니라 상수가 많이 줄어서 충분히 할만하다. 이걸 마지막에 시도라도 해봤어야 했는데 시도를 왜 안 했을까.. 정확하게 / 타이트하게 판단하지 않고 적당한 경험에 의거해서 대충 판단하는 것도 나쁜 습관인 것 같다.

2100 초반에서 수렴하는 중.. 정말 바닥을 치고 있다... D를 풀었으면 꽤 올랐을만한 상황이었는데 시도를 안한게 너무 아쉽다. 끝나고 짜서 제출해보니 바로 맞던데 흑흑

A. MP3

서로 다른 수의 개수만 중요하니까, 수를 전부 좌표압축해서 N 범위로 만들자. 이렇게 만들고 나면, prefix sum을 통해 특정 구간의 수 개수를 빠르게 계산할 수 있다. 이제 문제에 주어진 I 비트 조건에 맞춰 수를 어느 범위까지만 남길 수 있는지 계산하고, 그 범위 안에 있는 수의 개수가 최대화가 되는 구간을 고르면 된다. 비트에 따른 수 범위 잘못 생각해서 한 번 틀리고 / 전체 수 표현하기 위해 필요한 최소 비트 수 계산 잘못 해서 한 번 틀리고 두 번을 틀렸다. 둘 다 굉장히 기초적인 건데 이걸 틀린게 참.. 코딩 실수가 왜 이렇게 많아졌나 싶다.

B. Welfare State

A보다 이게 오히려 훨씬 쉬웠다. 실제로도 더 많이 풀림. 각각의 수에 대해, 그 수가 마지막으로 바뀐 시점을 기억하고 있으면, payout은 그 마지막 시점 이후에 적용된 것만 고려하면 된다. 그래서 각 쿼리 시점 이후의 payout 최대치를 계산해주면 마지막에 값이 얼마인지를 바로 계산할 수 있다.

C. Matching vs Independent Set

 재밌는 문제였다. 좀 더 빨리 풀 수 있었을 것 같은데 시간이 약간 오래 걸린 점이 아쉽다. 우선, 모든 정점이 independent set에 속한다고 생각해보자. 각 간선이 추가될 때 아래와 같이 처리해줄 수 있다.

 

1. u와 v가 모두 indpendent set에 속하는 경우 - u, v를 전부 indenpendent set에서 제거하고, 매칭에 해당 edge를 추가

2. 그 외의 경우 - 무시.

 

이렇게 해주면, 두 정점이 모두 ind set에 있을 때에만 매칭으로 넘어가고, 그 외의 경우 ind set의 크기에는 변화가 생기지 않는다. 이 때 매칭의 개수가 >= n 이면 당연히 매칭이 가능하고, 매칭의 개수가 < n 이면 ind set에서 사라지는 정점은 최대가 2 * n - 2개가 된다. 남는 정점의 개수가 n 이상이기 때문에, 항상 크기 n 이상의 independent set을 유지해줄 수 있다.

D. Rectangle Painting 1

dp[x1][y1][x2][y2] = (x1, y1) ~ (x2, y2)로 구성되는 사각형을 전부 흰색으로 채우는 비용으로 생각해보자. 주어진 문제에서 어떤 사각형을 채울 때 항상 max(w, h)만큼의 비용이 든다고 했으므로, 채울 사각형은 반드시 정사각형 형태가 된다. 직사각형으로 채우나 정사각형으로 채우나 비용은 같은데 정사각형으로 채울 때 더 많은 칸을 채울 수 있으므로 이게 이득이다.

 

따라서 정사각형 공간을 하나 채워주고, 나머지 영역을 어떻게 채우느냐가 문제인데, 전체 사각형을 3등분 해서 맨 왼쪽 위 사각형을 나머지 두 사각형 중 어디에 붙여서 계산할지 두 가지 케이스를 고려해주면 된다. 부분문제가 O(N^4) 개에 각각을 해결하는데 O(N)의 시간이 걸리므로 O(N^5)에 문제를 해결할 수 있다.