오전 셋

혜아만 있었던 관계로, 혜아컵 몇개를 돌았다.

B. Mahjong

D. The Other Way

J. Communism

O(3 ^ {15})에 된다. 소팅하면 안되고, 잘 merge해가면서 해줘야 한다.

H. Too Many Traps

IMO 문제라고 한다.

I. Protocol

112345^{167} \equiv 1 (mod `10^9+9) 이다. 167크기의 행렬을 관리하면 된다.

오후 셋

ONTAK 2013을 돌았다.

A. ucz

사람이 N 명 있고 모두 원탁에 앉히려고 한다. 각 사람마다 오른쪽에 앉을 수 있는 k_i 명의 사람이 정해져 있을 때, 원탁의 개수의 최소값을 구하자.

이분그래프를 만들고, 수평 간선(i에서 i로 가는 간선) N개를 만든 후에 각 수평간선마다 끊고 확장경로를 찾는 것을 반복하면서 이분 완전 매칭을 해 주면 된다. 이런걸 어떻게 생각하는지…

B. meb

CHT를 적당히 잘 채워주면 된다. O(n^2m)정도에 된다.

C. mis

B_i=A_i + dep_i라고 하면, 각 노드에 자신의 부모 중 B_i의 최대값을 들고, 소팅해주면 된다. 되는 이유는 그래도 답이 변하지 않고, 소팅했을 때 위상정렬 순서와 동일하기 때문.

D. sko

한 점을 잡고 차수를 구한 다음에, 0,1,2,n-2,n-1일때는 적당히 처리해주고, 나머지 경우에는 연결된 점들과 아닌 점들을 나누어서 매칭(?)해보면서 가시를 찾으면 된다.