ICPC Seoul Regional 2018

2018. 11. 4. 11:37알고리즘 문제풀기/대회 참가기

우리 팀 789가 대회 1등을 차지했다.

내가 푼 문제는 C, I, J, K 이다.


J. Starwars (32 min., +2, First Solve; 2nd AC from 789)

n(≤1,000)개의 정점(solar system)이 있고, 그중 일부는 human-controlled이며, 또 다른 일부는 military base가 설치되어 있다.
human-controlled와 military-base-installed 여부는 독립적이다.

또한 각 정점 사이에 m(≤8,000)개의 간선(wormhole)이 있다. 간선을 사용할 때마다, 그 간선에서 인증서(certificate)를 발급해 준다.
여러 간선을 사용하면, 그 경로에 의해 얻는 인증서가 순서대로 쌓인다.
인증서는 총 C(≤20)가지가 존재한다.

이 때, 어떤 human-controlled 정점에서 시작해 임의의 military-base-installed 정점으로 도달하는 경로와,
어떤 non-human-controlled 정점에서 시작해 임의의 military-base-installed 정점으로 도달하는 경로가
같은 certificate 수열을 가지게 되는, 두 경로 쌍이 존재하는지를 묻는 문제이다.
(두 경로의 마지막의 military-base-installed 정점은 서로 달라도 된다.)




이 문제는 2018 서울 리저널 인터넷 예선 K번 문제(Suffix-freeness)와 거의 똑같은 문제이다.
같은 certificate 수열의 경로 쌍이 존재한다면, 두 개의 말(駒)을 각각 human-controlled 정점과 non-human-controlled 정점에 놓고,
매 step마다 같은 certificate를 얻게 되는 정점으로 양쪽 말을 동시에 움직였을 때,
두 개의 말이 각각 military-base-installed인 정점에 도달하게 되는 움직이는 방법이 존재하게 된다.

즉 모든 human-controlled 정점 i와 non-human-controlled 정점 j에 대해 (i, j)의 쌍을 정점으로 잡고,
두 개 모두가 military-base-installed인 곳에 도달할 수 있는지를 BFS를 통해 확인해주면 된다.

모든 (i, j) 쌍에 대해 (i에서 시작하는 간선의 수)×(j에서 시작하는 간선의 수)만큼 탐색하게 되는데,
임의의 두 쌍의 간선이 고려되는 경우는 최대 1번 뿐이므로 O(n²c + m²)의 시간복잡도를 가진다고 말할 수 있다.


문제를 이해하고 나서는 인터넷 예선과 너무나도 똑같은 문제라서 당황했다.
그 때도 IJKL번을 담당했던 내가 풀었고, 그 때도 First solve였는데, 이번에도 완벽히 똑같았다.

s에서 t까지 움직일 때 c의 인증서를 받는데, s-t-c 순서가 아니라 s-c-t 순서로 입력이 들어오길래
왜 굳이 순서를 바꿔서 주는지 불평했는데, 오히려 '이 생각의 방향이 맞다'는 힌트가 되었던 것 같다.
(s, c) 쌍에 대해 하나의 t만 존재한다고 생각하고는 배열에 단순 대입을 해버렸더니 WA를 두 번 받았다.


K. TV Show Game (58 min., +0; 3rd AC from 789)

어느 TV 쇼에서는, red 혹은 blue 색의 lamp가 k개 주어져 있다. 불이 꺼져 있어 색을 알 수는 없다.
n명의 참가자가 각각 (i번째 lamp의 색은 X이다)의 추측을 정확히 세 개 하며, 이들 중 두 개 이상이 맞으면 상품을 받는다.
램프의 색깔을 잘 조절해 모든 참가자가 상품을 받을 수 있도록 할 수 있는가? 있다면 그 방법 중 하나를 출력하라.



참가자의 세 개의 추측 중 하나가 틀렸다면 나머지 두 개가 반드시 맞아야 한다.
각각의 추측을 (i가 blue이다)를 명제 i로 생각하고, (i가 red이다)를 명제 ¬i로 생각하면,
(¬a⇒b) 및 (¬a⇒c)는 항상 성립해야 한다.
각 참가자의 요구사항마다 이러한 조건식을 6개 세울 수 있다. (실은 이중 2개씩 세 쌍은 각자 대우 명제이다.)

아무튼 참가자의 요구사항은 이러한 "implies" 관계의 조건식으로 바꿀 수 있고,
V ≤ 5,000이고 E ≤ 30,000 × 2 인 2-SAT 그래프를 만들어 탐색하면 풀 수 있다.


"두 개 이상이 맞으면.."의 조건을 "한 개 이상이 맞으면..."으로 생각하고,
3-SAT인가? 특별한 경우에 성립하는 3-SAT인가? (실은 그러기에는 특별한 조건이 거의 없었기에 꼼짝없이 NP-Complete였다) 하고 넘겨버려서 늦어졌다.


C. Disk Arrangement (171 min., +0; 9th AC from 789)

직선 상에 원 n(≤1, 000)개를 나열한다. 직선 상이라는 말은, x축에 접하게 놓으면서 y≥0 평면에 놓이도록 한다는 이야기이다.
원들의 반지름만 정해져 있기 때문에 자유롭게 순서를 재배열할 수 있다.

이때, 이들을 최대한 tight하게 이어 붙였을 때 원들의 가장 왼쪽의 점과 가장 오른쪽의 점 사이의 거리(즉 max{x} - min{x})가 있을 텐데,
원들을 잘 재배열해서 이 값을 최소화하는 문제이다.
단, 원끼리는 서로 겹쳐서는 안 된다.

어떤 원이 너무 작거나 너무 크면, x좌표 상으로 서로 인접한 원끼리 겹치지 않더라도, 몇 개 떨어져 있는 원이 서로 겹치는 경우가 있을 수 있다.
가장 큰 원의 반지름이 가장 작은 원의 반지름의 4배 이상일 때만 이런 경우가 발생함이 알려져 있다고 문제에서 주어진다.
또한 그런 입력은 주어지지 않음이 보장된다.
즉 n!개의 배열 중 어떤 방법을 고르더라도, 인접한 것끼리 tight하게 붙였을 때, 원의 내부가 겹치는 경우는 절대로 없음이 보장된다.




수식을 가지고 엄청나게 고민했었다. 인접한 네 개 끼리의 순서 관계에 대해 (부등식을 세워) 규칙을 찾아보려고 하기도 하고...
하지만 대부분의 시도가 그럴 듯 하기만 할 뿐 확실하지가 않았다.

그래서 차라리, r을 랜덤하게 잡고, 작은 n에 대해 n!가지를 모두 해 봤을 때
혹시 크기 순서에 규칙이 나오지 않을까, 하고 코딩으로 확인해 보자고 팀원에게 제안했다.
처음에는 뭔가 다르게 나오길래 아닌가보다, 하고 포기했는데,
r값을 모두 다르게 하고(같은게 있으면 서로 순서가 섞여도 되기 때문에 헷갈릴 여지가 있었다) 보니까,
n이 짝수이면 한 가지 방법(n=8이라면 5 3 7 1 8 2 6 4)과 그것을 뒤집은 것(4 6 2 8 1 7 3 5)만이 답이 됨을 확인할 수 있었다.
n=10과 n=8에 대해 확인했다.

n이 홀수더라도 약 4가지 종류로 분류됨(가운데 값이 1인가 n인가 × 가운데 값에서 출발하는 방향과 그 옆에서 출발하는 방향이 같은가)을 찾았다.

r을 아무리 임의로 잡아도 n!가지 중에 항상 정해진 형태의 답만 값이 최소가 됨을 확인하자 자연스레
"대회 중에 확인은 못 하지만 신묘한 원리가 있겠지?" 라는 결론에 다다르게 되었다. 그럴 수밖에 없다.
그러고 보니 다른 팀들의 AC도 이런 느낌으로 빨리 나온 게 아닐까 싶었다. n이 작은 것은 위장전술이라고 생각했다.
아무튼 코딩해 제출했더니 아니나 다를까, AC를 받았다.


설마 이런 풀이일까에 대한 반신반의가 있었다.
하지만 대회 시작 후 약 1시간 시점(60 min.에 A: Circuits가 +1로 풀리고, 68 min.에 E: LED가 +3으로 풀렸다)에,
"패널티 말고 AC 갯수에 집중하자"라고 세 명 모두 의견을 모았다.
8 solve에서 9 solve가 되며 등수를 올렸던, 상당히 짜릿한 AC였다.

I. Square Root (294 min., +4, First solve; 11th AC from 789)

리저널 1위를 결정한 문제이다.
트리 T에 대해, 이 트리의 square라는 새로운 그래프 G를 구할 수 있는데,
정점 집합은 동일하고, T에서의 최단경로의 길이가 1 이상 2 이하였던 정점쌍들만이 G에서 연결되어 있다.

G가 주어지면, G가 T의 square인 트리 T가 존재하는지 판별하고, 존재한다면 T를 출력하시오.
G의 V ≤ 100,000이고, E ≤ 1,000,000.




일단은 정점을 하나 잡아야 하겠다. 트리의 루트를 r이라고 하자. (원본 트리는 사실 unrooted일 것이므로, 임의로 붙이는 셈이다)
r 근처(즉, r에서 거리 2 이하)의 점들이 r로부터 어떤 위치에 있는지를 확실히 판별하고 나면, 그 밑은 DFS로 바로 판별 가능하다.

그러면 r 근처의 위치 관계를 잘 확인하는 것이 중요할 것이다.
r과의 거리가 1인지 2인지를 판별하는 것이 매우매우 중요하다.
이를 위해, 나는 r과의 거리가 1인 점을 하나 찾아냈다. 그 방법에 대해 일단 설명한다.


먼저, r에서 거리 2 이하인 점(즉 입력으로 주어지는 그래프에서 r과 연결된 점)의 집합을 S라고 하자. (r 포함)
S - {r}의 각 정점 v에 대해, 주어진 그래프에서 연결된 인접 정점 중 S에 속하는 정점의 갯수를 세어 이를 각각 c[v]라고 하자.

c[v]가 최대인 v는 대부분의 경우 r과 직접 인접한 점이다. (즉 r과의 거리가 1)
왜냐하면, 깊이 2인 점에서는 자신의 서브트리 쪽 정점만 갈 수 있는데,
그 트리의 깊이 1인 노드(r의 자식)은 거기에 r의 다른 자식들까지도 갈 수 있기 때문이다.
단, r의 자식이 한 개라면 깊이 1이나 2나 같은 값을 가지게 되어 이 가정이 깨지는데, 이는 예외 케이스로 후술하기로 한다.
일단 c[v]가 최대인 v를 잡았고, 이것이 r과의 거리가 1이라고 하자.


이제 r의 직계 자손을 찾았다.
이때, v와 r 모두에서 갈 수 있는 정점들은 다음의 세 가지이다. 그림을 그려서 생각해보자.
1. v의 자식
2. r의 자식 중 leaf인 경우(즉 그 밑에 다른 자식이 없는 경우)
3. r의 자식 중 non-leaf인 경우, 즉 자식이 있는 경우

이 정점들의 집합을 E라고 하겠다.
이것저것 시도하다 보면, 1번과 2번 중 어느 쪽에 속하는지를 구분하기가 어렵고, 또 핵심적이다.
어느 게 어느 쪽인지를 결정하고 나면, 앞에서 말했듯이 그 아래쪽은 DFS로 처리 가능하다.


먼저, 3번 case에 해당하는 정점이 하나라도 있는지는 쉽게 판별 가능하다.
S의 점 중 v와 (입력 그래프에서) 연결되어 있지 않은 점이 있다면, 바로 3번 정점의 자식이다.
그러면, 그 점과 (입력 그래프에서) 연결된 점 중 E에 속하는 것을 찾으면 단 하나가 나올 것이며,
그는 3번 정점에 해당하는 점일 것이다.

3번 경우에 해당하는 점들에 대해서는, 그 아래쪽 서브트리를 모두 DFS로 바로 구할 수 있다.
또한, 1번과 2번 경우도 구분이 모두 되는데, 3번 정점과 (입력 그래프에서) 연결된 점이 2번, 아니면 1번 경우이다.
즉 E에 속하는 모든 정점이 어떤 위치 관계에 놓여 있는지를 모두 확정 가능하고, DFS로 트리를 구축한 뒤 답을 검증하면 된다.


즉 3번 case에 해당하는 점이 하나라도 있다면 1번과 2번이 구별이 되는데, 없다면 또다시 고민이다.
여기서, 1번 정점끼리와 2번 정점끼리는 서로 이어져 있으며, 1번과 2번은 서로 분리되어 있음에 주목했다.
즉 E에 속하는 점들을 서로 연결된 점들끼리 묶을 수 있다.
생각하기 편하게, 두 덩어리가 있다고 하면 하나는 1번, 하나는 2번 경우일 것이다.

그럼 둘중 하나는 v, 하나는 r에 매달면 되는 것일까? 아쉽게도 그렇게 쉽게 끝나지는 않는다.
왜냐하면, 1번 경우의 정점은 자식을 더 가지고 있어도 되고, 2번은 그러면 안 되기 때문이다.
그런데 자식이 있는지 없는지를 알 수가 있나? 주어진 그래프에서 바로 알 수 있는 것은 아닌데?

한 쪽 덩어리를 r에 매달 수 있다면, 나머지는 무조건 v에 달아도 될 것이다. (자식이 있어도 ok, 없어도 ok니까)
r에 매달 수 있는가, 즉 모두 자식이 없도록 r과 연결할 수 있는가?
그 경우, 그 덩어리의 정점 수가 k라면, 그 덩어리의 모든 점들은 주어진 그래프에서 (k+1)개의 간선을 가질 것이다.
같은 덩어리에 속하는 (k-1)개의 점, v, 그리고 r과 연결되어 있으므로.
따라서 이 조건을 만족하는지를 확인해주고, 구분해서 덩어리를 양쪽에 붙인 후 DFS로 트리를 구축한 뒤 답을 검증하면 된다.


답을 검증하는 것은 실제로 모든 거리 2 이하의 정점쌍들을 모두 보면서 입력으로 주어진 것과 일치하는지 확인하면 된다.
모순이 있다면 많아야 주어진 그래프의 E (≤ 1,000,000) 번 돌고 나면 비둘기집의 원리에 의해 모순이 나올 것이기 때문에, TLE는 걱정할 필요가 없다.


생각하지 않은 예외 케이스는, r이 자식을 한 개만 가질 때이다.
그러지 않도록 r을 잘 잡아야 한다는 소리이다.

주어진 그래프에서 degree가 가장 큰 것을 r로 잡으면 어떨까? (←제안받음)
만약 그런데도 r이 자식이 한 개라면, 그 자식으로 움직이면 대부분의 경우
(거리 2 이하로 갈 수 있는 점의 수)가 더 많아지므로 모순이 생길 것이다.

즉 대부분의 경우에는 저렇게 r을 잡으면 자식의 수가 2개 이상이고,
(1-대부분)의 경우는 바로 성게 모양 그래프인데, 이 경우는 입력으로 주어지는 그래프가 완전그래프이며,
루트를 무엇으로 잡고 v를 무엇으로 잡아서 처리하더라도 맞는 그래프가 되므로 문제 없다.



v를 찾는 아이디어(max{ c[v] }), 그리고 1번과 2번 경우를 분류하는 아이디어
이 두 가지가 중요했던 것 같다.
전자는 정말 일찍 갑자기 떠올랐고, 후자는 토론하면서 정립해 나갔다.

케이스 나누기에서의 자잘한 실수들을 하나씩 고쳤다.
눈으로 찾지 못한 DFS 루틴의 치명적인 오류는 DM을 코딩해서 찾았다.
평소에 알고리즘이 틀린 것 같으면 곧잘 파이썬으로 DM을 짜곤 했기 때문에 그 습관이 큰 도움이 되었다.
약 20분 정도 남았을 때 DM을 짜기 시작해서, 틀린 데이터를 찾고, 오류를 찾고, 고쳐서 제출했다.


.......


그렇게 짜낸 5번째 제출이 294분에 AC를 받았고
789 팀은 I번을 푼 유일한 팀이자, 그 덕분에 유일한 11솔브 팀이 되면서
2018 ICPC 서울 리저널 우승을 거머쥐었고, 동시에 2019년 봄 포르투갈에서 개최되는 ICPC 월드 파이널에 참가하는 행운을 얻었다.


아직 실감이 잘 안 난다. 너무나 큰 행운이 찾아온 것 같아 그저 감사할 따름이다. 열심히 해야겠다.



'알고리즘 문제풀기 > 대회 참가기' 카테고리의 다른 글

UCPC 2018 후기  (0) 2018.07.30
NYPC 1회 후기  (1) 2016.10.29
Codeforces(618): Wunder Fund Round 2016 후기  (2) 2016.01.30
Codeforces(500): Good Bye 2014 후기  (0) 2014.12.31