[2020-09-21] Codeforces Round 664 (Div.1)

오늘도 말아먹었다. 흠.. A번에서 멍청한 실수 두 번한 건 아쉽긴 한데, B 못푼 건 그냥 실력이어서 별로 할 말도 없다. 필요한 관찰 다 해놓고 못 풀었다.. 갈 길이 멀다.

 

A. Boboniu Chats With Du

값이 m보다 큰 것과 그렇지 않은 것을 구분해보자. m보다 큰 값이 하나도 없는 경우 전체 합이 곧 답이 된다.

m보다 큰 값이 하나라도 있는 경우, 그 개수를 c라고 하자. 하나를 고를 때마다 최대 d개의 다른 원소를 쓰지 못하게 할 수 있으므로, c개중에 (c + d) / (d + 1)개는 반드시 답에 포함이 되어야 한다. 이 값을 x라고 하자. m 보다 큰 걸 x ~ c개 쓰는 각각의 경우에 대해 값을 구해서 그 중 최댓값을 취하면 된다. 이 때 c개 중 k개를 쓴다고 가정했을 경우, 버리는 원소는 나머지 c -k개에서 최대한 선택하는게 좋다. 그러고도 더 선택해야한다면, 값이 가장 작은 것부터 순서대로 고르는게 좋다. 따라서 k가 고정됐을 때 값이 가장 작은 것부터 순서대로 버려야하는 개수를 구할 수 있으므로, 부분합 등을 이용해 각각의 k가 고정됐을 때 답을 O(1)에 구할 수 있다. 이걸 최대 N번 반복하면 되므로 O(N)의 시간 복잡도에 해결할 수 있다.

B. Boboniu Walks on Graph

 각 정점에서 최대 하나의 엣지를 고르게 되므로, 그래프는 function graph가 된다. 여기서 모든 정점이 자기 자신으로 돌아오는 경로가 있으려면, 모든 정점의 indegree가 정확히 1이어야 한다. 이 말은, 각 정점에서 간선을 통해 가는 다음 값(nxt)의 합집합을 취하면 정확히 1..n의 permutation이 나와야한다는 뜻이다.

 

 이 1..n permutation이 나오는지를 해시로 판별하자. 그러면, 각각의 c_i = j인 케이스에 대해 c_i 간선으로 형성되는 nxt의 집합을 하나의 수로 표현할 수 있다. 이제 K! 개의 모든 경우의 수에 대해 이 부분집합 합이 1..n 전체 한 번씩 나오는 것과 같은지 확인해주면 문제를 해결할 수 있다.

 

 이 문제에서 한 가장 큰 실수는 전체 경우의 수가 K!인데 10^K로 잘못 생각했다는 점.. 왜 그렇게 생각했는지 모르겠다. 이것때문에 K! 풀이는 시도할 생각도 못 했다. 그걸 생각했다고 해서 해시로 하면 되겠다 같은 발상을 했을진 모르겠지만.. 이런 문제에서 해시를 유연하게 쓰는 능력이 많이 떨어지는 것 같다. 비슷한 케이스에서 해시로 풀리는 걸 대체적으로 못 푸는 듯. 별로 안 풀어보기도 했고. 그래프에서 정점 집합 체크하는 걸 해시로도 충분히 할 수 있다는 걸 꼭 기억해두자. 내가 출제했던 Hello 2020 D도 비슷한 형태의 해시로 푼 사람이 많았는데.. 그 때 제대로 짚고 넘어가지 않은게 여기서 돌아온 것 같다.