1월 10일 Warsaw U Contest 연습

 방학에 시간이 많이 남아서 연습을 많이 하고 있습니다. 이번 연습은 Dirt (= 틀린 제출수 / 전체 제출수)가 70%나 될 정도로 엄청나게 많이 틀렸습니다. 22번이나 WA를 받고도 4등이라는 건 그나마 다행이지만, 풀이를 너무 대충 증명해서 코딩에서 틀렸는지 풀이에서 틀렸는지 구분이 되지 않아 엄청나게 많이 헤맨 점은 많이 아쉬웠습니다.

 작년 칭화대에 비해 올해 칭화대는 전력이 약해졌을 줄 알았지만, 전혀 아니라는 것을 이번 연습때 알게 되었습니다. 아직 갈 길이 먼 것 같습니다.

~1시간: 도토리가 D, 직후 상수가 K와 J를 AC. 도토리가 H 풀이를 생각하여 코딩했으나, 시간초과와 WA를 받다가 밖에서 디버깅을 하고, 상수가 A를 푸는 동안 틀린 점을 찾아 AC.

~2시간: 풀이가 나왔지만 불확실한 E를 코딩했으나 WA. 나중에 보기로 하고 G를 도토리가 코딩하여 AC. 직후 풀이가 나온 C를 상수가 코딩을 시작하였지만, 풀이가 불확실한 상태에서 WA.

~3시간 반: 결국 3명이 다같이 C를 확인했고, 틀린 부분과 풀이가 불확실한 부분을 열심히 바꾸면서 망해가다가 결국 AC. 직후 E를 열심히 고치다가, 풀이가 잘못된 것을 찾은 뒤 수정하여 AC.

~4시간 반: 삽질하는 동안 풀이가 나온 B를 도토리가 코딩하여 AC. 엄청나게 예외케이스가 더러운 문제여서 오래걸렸습니다.

 너무 많이 말려서 아쉬웠던 연습셋이었습니다. 예제가 약할 때 어디까지 말릴 수 있는지 보여줬다고 생각합니다.

---

구데기 문제 I 입니다.

주어진 자연수 n, k에 대하여, 정점 n개인 labeled graph 중 minimum vertex cover의 개수가 정확히 k인 graph의 개수를 2로 나눈 나머지를 계산하면 됩니다. (1 ≤ k < n ≤ 255)

예제 입력

4 (= 테스트케이스 개수)

3 1

5 4

5 3

57 32

예제 출력

0

1

1

1

예제 설명

정점 3개인 그래프는 총 8개이고, 이 중 minimum vertex cover가 1개인 그래프는 6개입니다.

---

저번 NEERC 문제 풀이입니다.

간선 가중치(와 0을 포함하는) 집합을 S라 하면, S의 모든 원소 c에 대해 아래 설명할 값의 최솟값이 답이 됩니다.

(모든 간선의 가중치 w를 min(w-c, 0)로 바꾼 그래프에서 최단경로의 길이를 d라 하면, d + K*c)

(1) (구한 값) >= (답)

최단경로에서 사용된 간선 중 0보다 큰 간선이 K개 이상이라면, 답 이상임이 당연합니다.

K개 미만이라면, 답 이상임이 당연합니다.

(2) (구한 값) <= (답)

답에서 크기순으로 K번째 가중치를 c'이라고 하면, c'에 해당하는 값이 곧 답이 됩니다. 만약 더 짧은 길이 있다면, 그 경로의 가중치는 답보다 작아 모순입니다.

끝!