티스토리 뷰

공부

Opencup 2017 - GP of Poland

구사과 2017.03.27 15:23

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

몰라

신고

'공부' 카테고리의 다른 글

Coder's high 2016 - Checkpoint 풀이  (0) 2017.05.07
Atcoder Regular Contest / Atcoder Grand Contest  (0) 2017.04.01
Opencup 2017 - GP of Poland  (4) 2017.03.27
ONTAK 2016  (0) 2017.02.26
Facebook Hacker Cup 2017 Round 3  (1) 2017.01.30
지하철 1호선 (트리와 쿼리 8) 풀이  (0) 2017.01.26
댓글
댓글쓰기 폼
공지사항
Total
94,775
Today
200
Yesterday
200