1월 11일 15년도 GP of China 연습

 오랜만에 좋은 결과를 얻은 연습입니다. 거의 3년 전 대회라는 것과, 그 사이에 상향평준화가 됐다는 점을 생각해보면 엄청 뛰어난 성적은 아닌 것 같지만, 그래도 만족스러운 결과입니다. 

~1시간

가장 쉬운 문제 J를 상수가 도토리가 AC, 직후 도토리가 풀린 A를 AC. 

이후에 쉬운 문제가 딱히 보이지 않았고, 이때부터 상수가 풀이가 나온 H를 틈틈히 코딩하기 시작했습니다. 

그 동안 B, F의 풀이와 C의 추측이 완성되었습니다.

~2시간

C에 시간초과가 날 것 같은 풀이를 코딩해보고, 최대데이터가 로컬에서 시간을 넘기는 것을 확인하여 다른 풀이로 AC.

직후 풀이가 나온 B와 F를 도토리가 빠르게 코딩하여 AC.

끝난 후 상수가 H를 코딩하고, 그 동안 E 풀이를 생각해보기로 합니다.

~3시간

E를 느린 알고리즘으로 코딩했으나 TLE를 받게 되고, 직후 시간복잡도를 약간 줄여 AC.

직후 지금은 사골국이 되어버린 D를 상수가 코딩하여 AC. 끝난 후 상수가 H를 코딩합니다.

~4시간

G의 완전한 풀이가 완성되어 도토리가 G를 코딩하고, 직후 I를 코딩합니다.

중간에 상수가 H의 틀린 점을 발견하여 (ppap 변수를 추가하면서) AC, 직후 도토리가 I를 AC 받아 연습이 끝났습니다.

---

신기한 문제 I 입니다.

정점 n개, 간선 m개인 그래프가 있습니다. 각 간선에는 빨간색, 파란색, 초록색 3개의 색이 칠해져 있습니다. 이 때 파란색 간선을 최대 B개, 초록색 간선을 최대 G개만 사용한 spanning tree의 가짓수를 구하면 됩니다. (1 ≤ n ≤ 40, 0 ≤ m ≤ 100000)

예제 입력

3 6 1 0 // n, m, G, B

1 2 1 // u-v 간선, 색 (1=빨강, 2=초록, 3=파랑)

1 2 1

2 3 1

2 3 2

3 1 2

3 1 2

예제 출력

10

예제 설명

2를 2개 이상 사용하지 않는 spanning tree의 개수로, 0개 사용하는 경우 2가지와 1개 사용하는 경우 8가지가 있습니다.

---

저번 Warsaw U Contest 문제 풀이입니다.

1번과 2번 정점에 대해 한 쪽에만 연결된 정점이 있는 그래프에 대해 생각해봅시다.

1번과 2번 정점의 번호를 바꿔도 minimum vertex cover는 바뀌지 않으며, 바뀐 그래프는 원래 그래프와 다릅니다. 때문에, "'1번과 2번 정점 중 한 쪽에만 연결되어 있는 정점'이 있는 그래프 중 minimum vertex cover가 k개인 그래프의 개수"는 짝수라는 것이 보장됩니다.

1번과 2번 정점의 인접한 정점 집합이 완벽하게 같은 경우만 확인해봅시다.

(1) 1번과 2번 정점 사이에 간선이 있는 경우.

1번과 2번 정점 중 하나는 선택되어야 합니다. 그리고 정점 하나를 minimum vertex cover에 추가한 것과, 그 정점을 없앤 그래프는, 값의 차이가 1이 됩니다. 때문에 이 경우는 정점이 n-1개, minimum vertex cover가 k-1인 경우의 가짓수와 같아집니다.

(2) 1번과 2번 정점 사이에 간선이 없는 경우.

minimum vertex cover를 1번과 2번이 동시에 선택되거나, 동시에 선택되지 않는 경우로 바꿀 수 있습니다. 때문에 1번 정점과 2번 정점을 합칠 수 있다는 생각을 할 수 있고, 문제를 weighted minimum vertex cover로 바꾼 뒤, 합친 노드의 가중치를 2로 배정하여 같은 문제로 바꿀 수 있습니다.

초기 상태는 가중치 1인 정점이 n개인 경우입니다. 같은 가중치의 정점 2개를 선택한 뒤, (1) 둘 중 하나만 고르거나, (2) 두 정점을 합칠 수 있습니다. (1)의 경우 K가 선택한 정점의 가중치만큼 줄어들고, (2)의 경우 K는 유지됩니다.

 위 스텝을 반복하면 2^0, 2^1, ..., 2^7의 가중치를 가지는 정점 각각이 최대 하나 남게 됩니다. minimum vertex cover의 값이 고정되어 있기 때문에 사용해야 하는 정점 집합은 고정되어 있습니다. 값의 개수가 몇 개 되지 않기 때문에 이 값을 전수조사를 사용한 뒤, 코드에 그 결과를 적어놓는 방법도 가능합니다.

(1) minimum vertex cover가 2개 이상인 경우. 그 정점 2개 사이의 간선의 존재 유무가 minimum vertex cover 값에 영향을 주지 않아 짝수입니다.

(2) minimum vertex cover가 남은 정점 중 최소 가중치가 아닌 경우. 그 정점과 최소 가중치를 가진 정점 사이의 간선 존재 유무가 영향을 주지 않아 짝수입니다.

(3) minimum vertex cover가 남은 정점 중 최소 가중치인 경우. 그 정점을 중심으로 하는 성게 모양만이 가능한데, 간선이 없는 경우를 제외해야 하기 때문에 홀수입니다.

(4) K = 0인 경우, 간선이 없어야 하기 때문에 1개입니다.

조금 최적화를 하면 시간 안에 나오고, 최적화를 하지 않아도 모든 입력에 대해 답을 계산하여 코드에 적어놓아도 문제를 해결할 수 있습니다.