_

1. Day1

1.1. Potemkin Cycle

문제

보통 사이클 문제는 DFS numbering 등으로 풀기 때문에 이런 방법을 사용해 보려고 노력할 수 있지만, 이런 접근 방식으로는 풀기가 어렵다.

기준 정점 \(v\)를 잡고, \(v\)와 직접 연결된 정점들을 \(c_1, c_2, ..., c_k\)라 하자. \(v\)와 \(c_1, c_2, ..., c_k\)가 아닌 모든 정점들에 대해 간선으로 연결된 모든 정점쌍을 union 해준다. 이렇게 나머지 모든 정점을 집합화할 수 있다. 마지막으로, \(c_i\)와 \(c_j\)가 직접 연결되어 있지 않고 같은 집합에 연결되어 있는 경우, \(c_i , v, c_j, ........, c_i\) 순서의 조건을 만족하는 사이클을 무조건 구할 수 있다.

1.2. Calvinball Championship

문제

여태까지 배열에 있는 최댓값이 i일 때 가짓수, i까지 고려 시 답, 2가지를 DP로 저장하면 된다.

1.3. Pipes

문제

단절선을 구하는 문제지만, 메모리 제한이 작기 때문에 모든 에지를 저장하지 않고 단절선을 구할 때 필요한 간선들만 저장해야 한다.

아이디어는 두 그룹을 합치는 간선은 3개 째부터 무시할 수 있다는 것이다. 1개인지 2개인지는 단절선을 구하는데 영향을 주지만, 2개 이상인지 2개인지는 단절선을 구할 때 영향이 없다. 이는 Disjoint Set을 2개 관리하면서 간선 (a, b)가 추가되면 첫 Disjoint Set에서 a와 b가 같은 그룹인지 검사하여 만약 같은 그룹이면 두 번째 Disjoint Set에서 a와 b의 Union 작업을 해주고, 같지 않으면 첫 Disjoint Set에서 a와 b를 Union 해준다. 만약 두 번째 Disjoint Set에서도 a와 b가 같은 그룹이면 간선 (a, b)는 무시해도 되는 간선이다.

2. Day2

2.1. Ice Hockey World Championship

문제

2.2. Nuclearia

문제

2.3. Calvinball championship, again

문제