1월 9일 NEERC17 연습

 NEERC 17-18 연습 결과입니다. NEERC가 끝난 당일부터 한 번은 꼭 돌아보고 싶었는데, 결과가 좋지는 않아서 아쉬웠습니다. 초반 패널티 관리에서 꽤 준수한 모습을 보여주었지만, 뒷심 부족과 전략 미스로 벌었던 시간을 다 날렸습니다. GP of Spb때는 제가 코딩을 하고 상수와 도토리가 밖에서 풀이를 생각한 점, Eastern GP때는 도토리한테 코딩이 과하게 몰린 것, 이번에는 저와 상수가 도토리와 의견교환 없이 코딩을 들어가고 도토리 혼자 풀이를 생각한 것 정도가 지금까지 경험한 전략 미스입니다. 팀연습은 역시 어려운 것 같습니다.

 

~1시간: 도토리가 E를 푸는 동안 제가 C 풀이를 전달, 직후 B 수식을 계산한 것을 구현했습니다. 직후 도토리가 D를 혼자 풀었습니다.

~2시간: 도토리가 F 예외처리에서 고생하는 동안 저와 상수가 L을 엄청난 삽질 끝에 풀이를 생각, 스왑 후 상수가 구현했습니다. 직후 도토리가 버그를 찾아 AC.

~3시간 13분: 제가 A 풀이를 도토리에게 전달 후 구현했고, 그 후 팀노트를 활용하여 G를 AC 받았습니다. 무슨 이유에서인지 팀노트가 잘못되어 있었고, 때문에 약간의 시간을 날렸습니다.

~4시간 30분: 상수와 제가 I 코딩을 들어가기로 합니다. 여기서 풀이에 확신이 없었는데도 도토리와 풀이 공유를 하지 않은 것이 후회됩니다. 로컬에서 테스팅 가능한 문제였는데 엄청난 삽질에도 AC를 받기에는 무리. 결국 도토리가 I 풀이를 다시 생각하여 코딩을 시작합니다.

~5시간: 도토리가 약 20분동안 코딩해서 I를 AC. J는 시간복잡도상 절대 나오지 않을 풀이였음에도 한번 코딩해보자는 생각으로 옆에서 따로 코딩해봤고, 결국 당연하게도 TLE로 마무리했습니다.

끝나고 나서 J 풀이를 확인했고, 코드에서 한 글자를 바꾸는 것으로 AC를 받을 수 있었습니다.

문제 성격이 후반지향형일수록 성적이 떨어지는 경향이 있는 것 같습니다. 월파에서는 그러지 않았으면 좋겠습니다.

---

가장 인상깊은 문제 J 입니다.

정점 n개, 간선 m개인 무방향 그래프와 자연수 K가 주어져 있습니다. 1번 정점에서 n번 정점으로 가는 최단거리를 구하는 문제인데, 거리는 최단경로에서 사용한 간선이 K개 이하인 경우 모든 가중치 합으로, K개 초과인 경우 크기순으로 큰 K개의 합으로 정의됩니다.

예제 입력

6(n) 7(m) 2(K)

1 2 6

2 3 1

2 4 3

2 5 5

3 6 10

4 6 9

5 6 8

예제 출력

14

예제 설명

1 -> 2 -> 5 -> 6의 경로를 사용하면 간선 가중치는 6, 5, 8이고, 이 중 큰 2개의 합인 14가 최단거리가 됩니다.

---

저번 호치민 리저널 연습 G 풀이입니다.

두 명이 가져간 숫자의 합이 고정되어있다는 점을 이용하면, 두 사람이 가져간 숫자 차이를 안다면 누가 이겼는지 알 수 있게 됩니다. 식을 잘 살피면, 차이를 2K로 나눈 나머지를 관리하면 된다는 결론을 얻을 수 있습니다.

2K로 나눈 나머지가 같은 것이 2개 이상 있는 경우에는 없애도 결과가 동일합니다. 따라서 2K로 나눈 나머지가 0, 1, ..., 2K-1인 것이 0개 또는 1개인 문제로 바꿀 수 있습니다.

마지막 순간에 숫자 2개 a, b가 남아있다고 해봅시다. a != b+K인 경우, 선수는 후수를 항상 지게 만들 수 있습니다. 때문에 후수는 자신의 승리가 불가능하기 때문에 선수를 패배시키는 것이 유일한 목적이 됩니다. 마지막 순간에 3개, a, b, c가 남고, a, b, c가 mod K로 모두 다른 경우, 후수는 선수가 가져가면 이기는 숫자를 가져가는 방식으로 선수를 이기지 못하게 만들 수 있습니다. 이를 이용하면 c와 c+K가 동시에 존재하지 않는 숫자가 3개(혹은 2개?) 이상 존재하는 경우 무조건 비기리라는 것을 알 수 있습니다.

c, c+K가 동시에 존재하지 않는 숫자가 1개인 경우입니다. 선수가 차이를 c+(n-1)/2 * K로 만들어야 이기면, 처음에 c를 고른 뒤 후수의 행동을 따라하면 됩니다. (a를 고른 경우 a+K를 고릅니다.) 반대로 c를 골랐을 때 비기거나 진다면, 후수가 선수를 따라하는 방식으로 선수가 c를 강제로 고르게 할 수 있습니다.

정확히 기억은 안나지만, c, c+K가 동시에 존재하는 숫자가 0개인 경우, 1개인 경우, 2개 이상인 경우로 나누어 열심히 경우를 분석하면 풀 수 있습니다.