CodeForces에서 2개를 돌았다. 오전은 안했고, 5시 코포라 오후에 4시간, 2시간 반 으로 돌았다.

오후 셋 1

Russian Code Cup 2016 Finals를 돌았다. 뭔진 모르고 그냥 어려운 셋이었다.

A는 적당한 그리디를 쓰면 되는 문제다. 한 입구에서 가장 먼 점부터 생각하면 편하다.

B는 플로우나 이분 매칭으로 풀 수 있다. 모델링은 어렵지 않게 되고, 플로우는 <img src=”//s0.wp.com/latex.php?latex=O%28E%7Cf%7C%29+&bg=ffffff&fg=000&s=0” alt=”O(E f ) “ title=”O(E f ) “ class=”latex” />d에 되는데 f 가 작아서 되고, 이분 매칭을 할때는 정점을 많이 만들면 간선 수가 너무 많아지므로, 한 정점을 여러 번 보는 식으로 짜면 된다.

CDEF는 문제도 안읽었다.

오후 셋 2

CodeForces Round 500을 돌았다. 마스터갈줄알았는데..

A는 수들을 소팅하고,  앞에서 N개를 묶거나, 중간에 N개를 묶는 경우롤 생각하면 된다.

B는 각 행과 열을 나타내는 정점들을 만들고, Union-Find 해주면서 컴포넌트 개수를 세면 된다. 이게 되는 이유는 서로 다른 그룹에 속한 두 정점에 대해서, equivalence 관계가 생기기 때문이다. 혹은 귀납적으로 완전 이분 그래프에서 정점을 하나 추가하고 가능한 간선을 다 그어 보면, 여전히 완전 이분 그래프인것을 확인할 수 있다.

C는 적당히 DP를 세워주면 된다. 나는 잘 모르겠어서 12개의 경우를 나눠서 했는데, 보통 사람들은 1개 혹은 3개로 나눈 듯 하다.