Opencup 2017 - GP of Poland

A. CNF-SAT

몰라

B. Almost pattern matching

몰라

C. Two paths

http://codeforces.com/blog/entry/51228?#comment-351103

D. Mushrooms after rain strikes back

몰라

E. Epic Battle

alex9801 선배가 풀었다. 필요충분조건이 한정적이라 간단한 케이스 판별로 풀 수 있다고 함

F. Reachability

편의상 어떤 점들도 degree가 0이지 않다고 생각한다면, 각각의 starting point가 도달할 수 있는 정점의 개수가 구간의 형태로 나온다. starting point를 증가시키면서 가능한 다음 구간들을 모두 시도해 보면 (다음 구간은, S_i <= S_j <= E_i + 1이며 E_i <= E_j를 만족해야 한다) N^5 정도가 나오는데 그 "가능한 다음 구간" 이 이쁘게 나와서 2차원 부분합이 가능하다. 

실제로는 degree가 0인 정점이 있으니 그 개수를 iterate해서 이항 계수에 잘 비벼먹자.

결론적으로 N^3에 해결 가능

G. Reorganization

재귀적으로 문제를 해결한다. 현재 그래프에서 루트가 될 수 있는 후보인 점들은 그 어떤 사람들에게서도 미움받지 않아야 하며, 그 어떤 사람도 자신의 조상으로 오기를 원치 않는 사람이어야 한다. 이제 이 점을 그래프에서 지울 수 있는데, 조상으로 오기를 원하는 쌍들끼리 양뱡향 에지를 그어서 연결 컴포넌트를 만든다. 같은 연결 컴포넌트에 속하지 않는 쌍들끼리의 싫어함을 무시하고 각각의 컴포넌트마다 루트를 또 재귀적으로 계산해서 그 루트를 자신에게 이어주는 식으로 트리를 만든다. 답이 있는 경우에 항상 이 방법으로 답을 찾을 수 있다.

그래프에서 지울 수 있는 점의 후보가 여럿 있을 수도 있는데 그 중 아무거나 지워도 상관없다.

여담으로 대회 때 풀이를 찾고 못 풀었는데 그 이유는

(...) 

H. Matching

몰라

I. Words

버스가 품

J. Tournament

이길 수 있다 -> path를 통해 도달 가능하다 라서 floyd warshall 쓰면 쉽게 풀린다.

K. Scale

몰라