ACM-ICPC Daejeon Regional 2016

ACM ICPC Daejeon Regional 2016에 다녀왔습니다. 당연하지만 고등학생이니 경기하러 간 건 아니고 그냥 놀러 갔습니다.

대학생이 아니라 처음에는 대회를 치르는 사람들이 정말 부러웠지만, 지금 다시 생각해보면 스트레스 안 받고 2층에서 편하게 팝콘뜯으면서 입풀이하고 중계하는게 더 꿀인거 같네요. 아는 얼굴들도 워낙 많았고 재밌는 일도 많아서 오랜만에 정말 즐거운 시간 보낼 수 있었습니다. 특히 zigui님의 코스프레가 정말 인상 깊었습니다. 대전 리저널에 새 역사를 쓰신...

총 12문제가 출제됐는데, 중계석에서 풀면서 느꼈던 점은 어렵고 재미있다는 점이었습니다. 생각에 조금 더 비중이 맞춰졌고, 재미있는 아이디어도 많았던 좋은 세트라고 생각했습니다. 물론 잘 풀었다는 건 아니고, 알고스팟 중계 기록을 보면 저의 뻘짓 로그를 보실 수 있습니다 (...) functionx 형이 정말 잘 푸시더라고요. 이걸 다 푼다는건 정말 대단한 거라고 생각합니다. 관중석 난이도와 실제 참가자 난이도가 다르다는 걸 감안하면 더... 

대회 참가자는 아니지만 뷔페 식단과 상품들을 얻을 수 있었습니다. 쿠키런 쿠션 너무 좋아요 >___< 상품은 못 가져갈 뻔했지만 데브시스터즈의 여성 직원 한 분이 코스프레하신 zigui님과 함께 사진을 찍는 대가로 (?) 주셨습니다. 유명인 옆에 붙어있던 보람이 있네요.. 버린 줄 알았던 중계용 problemset도 나중에 보니 저에게 있더라고요. kriii형의 친필 싸인은 가보로 간직하겠습니다. 오른쪽 아래 종이에 "koosaga" 라고 써진거.. 

대전 리저널 1등인 서울대학교 ACGTeam은 끝나기 20분 전쯤 모든 문제를 다 풀고 노는 게 포착되었습니다. 이번 대전에서 본인들이 보통 사람이 아니라는 것을 제대로 입증하고 간 것 같습니다. 월드 파이널 진출 확정. 4등(2등 대학 대표팀)인 카이스트 hYEAHyea 역시 월파 가능성이 매우 높습니다. 저랑 IOI 2015 같이 나갔던 사람들이 전부 이번 대전에서 잘해줘서 굉장히 기쁩니다. 해외 리저널에 따라서 나머지 팀들의 월파 가능성이 결정될 것입니다. 참가하신 모든 분들이 이후 리저널이나 월드 파이널에서 본인들이 원하는 결과를 낼 수 있기를 바랍니다. 

재밌는 기억 많이 쌓아서 좋았고, 앞으로도 이런 기회가 있을 때마다 올 수 있었으면 좋겠습니다. 마지막으로 대전에서 여러 방면으로 저를 도와주신 분들이 많이 계셨는데 다시 한번 감사합니다.

(사진은 누르면 고화질로 보실 수 있습니다. 전체 사진은 현재 ICPC 페북에 있는데, 만약 그쪽 링크가 죽으면 저에게 이메일 (구사과 골뱅이 지메일) 보내주시면 제가 보내드리겠습니다. 몇개는 제가 찍은거라 ICPC 페북에 없습니다.) 

광명역에 처음 가봤는데 ~~광명공항~~ 공항같아서 신기했습니다. 가기만 쉬우면 참 좋을 거 같네요.

저는 내내 오른쪽 상단 난간에 있었습니다. 왠지 모르겠는데 사진에는 없네요.

중계석

우승팀 ACG. 이 사진이 찍히는 걸 멀찍이서 본 중계진은 올솔브를 확정지었습니다 (...)

ㅋㅑ ~~~~ 미쵸~~~~~~~~~

전리품 1

전리품 (?) 2

스코어보드 (줌은 한계까지 했습니다 ㅠㅠ 이보다 작으면 검색창이 튀어나와서 깨져요)

Problemset / Spoiler

http://icpckorea.org/2016/REGIONAL/problemset-2016.pdf

알고스팟 중계 : https://algospot.com/forum/read/4010/ 풀이에 대한 약간의 스포일러가 포함되어 있으니 이해가 안가면 참고.

난이도는 I < G < L < C < B < D < H < K < E < F < A < J라고 생각한다. K는 사전지식 문제라 이견이 있을수 있지만 나머지는 얼추 맞다고 생각. 초반 7문제와 후반 5문제의 격차가 커서 초반 7문제를 빨리 먹고 어려운 문제를 도전해야 한다고 생각했는데, 예상보다 풍선이 늦게 올라와서 (특히 D가 엄청 늦게..) 이걸 한 팀이 별로 없었다. 결국 초반 7개를 빨리 먹은 4팀이 최종 결과에서도 4등 안에 들었다. 중계석 입코더 관점임에도 불구하고, 11문제 이상은 정말 대단하다고 생각한다. 그런 면에서 ACG 너무 머시따.

이번 셋은 문제들이 다 상당히 괜찮은데, 특히 아름답고 재미있다고 생각했던 문제는 AFH이다. 

일부 문제는 구현했으며, 코드는 https://gist.github.com/koosaga/04608d210a26f5f3d0ba3679d2befc11 에 있다. 

 * (17.01.13) J 문제의 풀이와 정답 코드를 첨부해서 업데이트했습니다. 

A. Bridge Park

독특한 형태의 평면 그래프가 주어졌을 때, 이 그래프를 biconnected graph로 만들기 위해서 추가해야 하는 에지의 최소 개수를 출력해야 한다. 에지를 추가해도 그 "독특한 평면 그래프" 형태를 만족해야 한다.

먼저, 최적해는 원 상에서 인접한 정점 (i - i+1) 들만을 잇는다는 것을 알아야 한다. 이는 그렇지 않은 경우를 가정했을 때 해를 항상 개선시킬 수 있다는 형태로 보일 수 있다. 

목표는 어떠한 i - i+1 을 이어가지고 bridge를 전부 제거하는 것이다. 이를 위해서 dual graph를 생각하자. 일단 원 상에 있는 인접한 정점들이 이어지지 않았다면 다 이어주자. 이제 이는 N각형이 적당히 쪼개진 형태의 모습을 한다. 각각의 쪼개진 다각형의 영역을 정점, 서로 닿아있는 영역을 간선이라고 하면서 dual graph를 만들 수 있다. 이 dual graph는 트리 형태를 띈다. 각각의 쪼개진 다각형 중 일부는, 이어지지 않은 i - i+1 간선 하나에 대응된다. 그렇지 않은 다각형은, 테두리에서 사이클을 이룬다. (고로 bridge가 붙어 있지 않는다) 

bridge를 제거하려면, 어떠한 i - i+1을 이어야 한다. 이 때의 경우를 생각해 보면

 * bridge가 인접한 두 영역을 잇는다면, 두 영역 모두 i - i+1 간선에 대응되는 영역이다. 이 중 하나의 영역이라도 i - i+1이 이어져 있어야 한다.

 * bridge가 단 하나의 영역에만 연결되어 있다면, 그에 연결된 영역 하나에서 i - i+1이 이어져 있어야 한다.

앞서 정의했던 dual graph는 여기서 굉장히 유용하게 작동한다. 먼저, i - i+1 간선에 대응되는 정점만을 트리에서 추려내서 포레스트를 만들자. 추려진 모든 간선들은 bridge가 된다. i - i+1을 잇는 것을, 정점을 선택한다고 생각할 수 있다. bridge는 하나의 정점의 선택을 강제하거나, 인접한 두 정점 중 하나를 고르게 하는 역할(간선) 을 한다. 이는 변형된 Minimum Vertex Cover 문제이다. 포레스트니, 트리 dp로 풀 수 있다.

B. Football

사실 이거 왜 되는지 증명은 못하겠지만... 아무튼 정해도 똑같은 방법이다. 가장 승수가 높은 팀부터 그리디하게 뽑는다. 이 팀의 승수가 K라고 하면, 승수가 낮은 K개의 팀들에게 이 팀이 이겼고, 나머지 팀들에게 이 팀이 졌다고 가정한다. 이렇게 해서 이 팀을 제거하고 과정을 계속 반복하는 그리디 알고리즘으로 문제를 해결할 수 있다.

이를 그대로 구현하면 N^2lgN이지만, 승수 count 순으로 counting 배열을 관리하면 N^2로 줄일 수 있다. counting 배열을 관리하는 게 조금 까다롭다고 생각했다. 

여담으로, https://en.wikipedia.org/wiki/Tournament_(graph_theory)#Score_sequences_and_score_sets 에 훨씬 간단한 O(N) 알고리즘이 나와있다. 저 조건을 만족하는 것과 필요충분이라고 한다. 

C. House Rental

수직선 상에 K 종류의 시설물이 각 종류마다 1개 이상 존재한다. 임의의 위치에서 i 종류 시설물과의 거리는, 가장 가까운 i 종류 시설물과의 거리로 정의된다. 적당한 정수 위치에 집을 지어서, 각각의 K개의 시설물에 대해, 가장 먼 시설물과의 거리를 최소화해야 한다. 그러한 여러개의 정수 위치 중, 가장 작은 위치를 출력해야 한다.

시설물들을 모두 x축 크기로 정렬한다음에, |시설물|^2개의 구간을 전부 확인해서, 그 중 K 종류의 시설물을 전부 포함하고, 구간의 길이가 가장 작은 (같다면 중점이 가장 작은) 것을 찾는 식으로 해결하는 것이다.

물론 이걸 이대로 짜면 시간 초과다. 여기서 sliding window를 사용하자. 결국 구간의 길이를 최소화해야 하니, 현재 위치에서 K개를 포함하면서 구간의 길이를 최소화하는 형식으로 전체 시설물을 한번에 훑는 것이다. 정확히는, 각각의 시작점 S에 대해서, 이 시작점에서 K개를 포함하는 최소 끝점인 E를 O(|시설물|) 에 구하고, 유의미한 N개의 구간에 대해서 길이를 비교하는 것이다. 여기서 설명하기는 참 애매한 개념이고 sliding window, inchworm, two pointers 같은 키워드로 찾아보는 걸 추천. K개를 포함하는지 판별하는 건 그냥 크기 K 짜리 배열과 서로 다른 원소 개수를 변수로 갖고 다니면 쉽게 할 수 있다.

a + b < 0 일 때 (a+b)/2를 계산하면 틀리는 게 함정이었다고 한다. 조심하자.

D. Independent Edges

길다. 개인적으로 문제 카테고리를 "독해" 에 넣어야 한다고 생각한다. 하지만 요약하면 엄청 짧은데, 이분 그래프에서의 Independent Edge Set과 Independent Vertex Set을 출력하는 것이다. 

Independent Edge Set은 최대 매칭을 잘 꼬아놓은 말장난에 불과하다. 이분 그래프에서 최대 매칭과 최대 독립 집합은 모두 O(nm)에 구할 수 있음이 잘 알려져 있다. 최대 독립 집합을 구하는게 까다로울 수 있으나, 이 글에 잘 설명되어 있다. (최소 정점 덮개의 여집합이 최대 독립 집합이다.) 

여러분 koosaga.com 읽으세요. 두번 읽으세요.

E. Memory Cell

expression이 주어졌을 때, 이를 문제에 정의된 트리의 형태로 정규화 한후, 가장 큰 common subtree를 출력하는 문제이다. 

문제에서도 나와있듯이 트리의 형태로 어떻게든 만들어야 한다. 이는 한땀한땀 parser를 짜면 된다. N의 크기가 작아서 parser를 짜는게 그렇게 어렵지는 않다. 

parser만 짜면 문제는 어렵지 않다. subtree가 완전히 동일해야 같다고 치기 때문에, euler tour를 적어두는 등으로 subtree compare를 string compare로 환원하자. 이제 N개의 문자열 S1 .. SN 중, i != j이며 Si == Sj인 문자열 i, j를 찾으면 된다. 이는 단순 sorting으로 N^2lgN에 해결할 수 있다. 여담으로 카이스트 모 팀은 용자스럽게 N^3을 그냥 돌리고 한번에 AC맞았다고 한다 (...) 

F. Meteorites

겹치지 않는 빌딩 ( = 수평선 위에 세워져 있는 높이가 있는 구간 ) N개가 있다. K개의 쿼리가 주어진다. 쿼리마다 충분히 높은 하늘에서 유성이 직선으로 떨어져서 건물을 덮친다. 유성은 시작점과 방향으로 주어진다. 유성이 가장 먼저 치는 건물이 무엇인지를 쿼리마다 출력해야 한다. 유성우 쿼리는 건물을 부수지 않는다 (쿼리는 독립적이다.)

문제를 해결하기 위해서는 몇가지 가정이 필요하다. 코딩을 조금 추가해서 이 가정을 만족하게끔 문제를 수정할 수 있다.

 * 유성은 x축이 증가하는 방향으로 떨어진다.

 * 건물은 왼쪽 테두리, 오른쪽 테두리만 있으며, 수평선 덮개를 건물에서 없는 것으로 취급한다. 즉 메테오가 건물 옥상을 치지 않고, 건물 안으로 들어와서 오른쪽 벽을 친다.

문제는 유성 (반직선) 과 높이가 있는 2N개의 수직선에 대한 문제로 바뀌었다. 유성이 가장 먼저 치는 수직선은, 그 꼭지점이 유성이 만드는 반평면 위에 있는, 가장 x좌표가 작은 점이 될 것이다. 이제 문제는 수직선도 아니고 점에 대한 문제로 바뀌었다.

유성이 만드는 반평면 위에 있는 가장 x좌표가 작은 점을 구하기 위해서, parametric search를 생각할 수 있다. 구간 [1, T] 상에서 유성이 만드는 반평면 위에 있는 점이 존재하는 지를 lgN번 구함으로써 반평면에 속하는 가장 x좌표가 작은 점을 구하는 것이다. prefix에 그러한 점이 존재하는지를 빠르게 구하기 위해서는 segment tree를 구성하면 되는데, 각각의 노드에는, 노드에 대응되는 구간의 점들을 모아서 upper convex hull을 만들어주면, 반평면에 속하는 점이 존재하는지를 노드마다 lgN 이진 탐색으로 구할 수 있으니, NlgN + Qlg^3N에 구할 수 있다. lg^3N은 물론 느리고, 트리를 루트에서부터 타면서 내려가면 Qlg^2N으로 이를 줄일 수 있다. 결론적으로, NlgN + Qlg^2N에 풀 수 있다. (정해는 분할 정복으로, 그냥 똑같이 푸는데 오프라인으로 푸는 것 말고는 차이가 없는 걸로 기억한다..)

G. Percolation

장애물 있는 격자가 있고 상하좌우로 움직일 수 있다. 맨 윗 줄에 있는 임의의 점에서 맨 아랫줄로 움직일 수 있는지 Y / N으로 판단해야 한다.

맨 윗줄에서 계속 flood fill을 시도해서 끝 줄에 도달할 수 있는지 체크하면 된다. BFS를 한다면 큐에 맨 윗줄 정점을 한꺼번에 넣고 돌리면 된다. 아무튼 기본 flood fill 문제. 

H. Power Supply

트리의 각각의 정점에 supply, demand가 존재하며, 각각의 간선에 flow capacity가 존재한다. 트리의 간선을 적절히 끊어서 서브트리로 분해한다. 각각의 서브트리는 

 * 정확히 하나의 supply에서, Vi 이하의 전원을 공급하고, 

 * demand에서 정확히 Vi을 공급받아야 하며

 * flow capacity 이상의 전기가 간선을 통해 흐를 수 없다.

는 세가지 조건을 만족해야 한다. 이러한 서브트리 분할이 가능한지 찾으면 된다.

입풀이라 검증이 안됐다.. 아마 될거다. 생각하기 편하게 하기 위해서는 flow capacity를 무시하고 생각해보자. demand를 단순히 -Vi라고 생각하면, 각각의 서브트리에 정확히 하나의 supply가 존재하고, 정점에 달려있는 값들의 합이 0 이상이게 서브트리를 나눠야 함을 뜻한다. 이는 리프부터 컴포넌트를 만들어서, 컴포넌트를 가능하면 최대한 루트까지 높이 올리는 형태로 그리디를 돌리면 된다. top down dfs로 어렵지 않게 구현할 수 있다. 이렇게 풀고 나서 flow capacity를 도입해도, 문제가 크게 달라지지 않는다. 

I. Robot

하라는 대로 로봇을 돌리고 움직이면 된다. 

J. Room

rectilinear polygon이 있는데, 각각의 변에 대한 정보가 완전히 주어지는 것이 아니라 "(x, y) 점을 가로 / 세로로 지난다" 의 형태로 주어지고 있다. 이 때 rectilinear polygon을 복원해야 하는 문제이다. (복원이 불가능하면 -1)

코딩하기 힘든 풀이를 생각해내는건 어렵지 않지만, 코딩하기 쉬운 풀이를 생각해내는 것은 상당히 어려운 문제이다. 에지들을 x축이 증가하는 순서대로 봐서, 위쪽 체인이나 아랫쪽 체인에 에지를 붙이는 형태로 다각형을 복원하는 방법을 생각할 수 있는데, 대부분의 경우 에지를 위쪽에 붙일 지 아랫쪽에 붙일 지를 결정할 수 있다. 여기까지는 괜찮은데, 케이스가 정말 많다....

조금 더 쉽게 코딩할 수 있는 방법은, horizontal한 직선에 대해서 왼쪽에 붙을 vertical한 직선과, 오른쪽에 붙을 vertical한 직선을 따로 결정해주는 방법이다. 똑같이 에지들을 x축이 증가하는 순서대로 보는데, horizontal한 직선을 최대 2개씩 가지고 다니면서, 만약 vertical한 직선을 만나면 이 직선과 붙여줄 horizontal한 직선을 결정해주고, horizontal한 직선을 지워준다. 이렇게 하면 horizontal한 직선에 대해서 오른쪽에 붙을 직선을 결정해 줄 수 있다. 왼쪽에 붙을 직선은 배열을 reverse하면 똑같이 결정해 줄 수 있고, 왼쪽으로 오른쪽으로 정당하게 붙여줄 수 있으면 답을 항상 복원할 수 있다.

대충의 아이디어는 이렇지만 완전히 맞는 설명은 아니고 디테일이 좀 있다. 그리고 솔직히 왜 되는지도 잘은 모르겠다... 코드를 보는 것을 추천...

K. Rounding

N * M 표가 주어지며, 각각의 column과 row의 합 역시 주어진다. 주어지는 모든 수는 실수 형태인데, 만약에 이 수가 정수가 아니면 ceil(x)나 floor(x) 중 아무거나 대입해서 정수로 만들어야 한다. 실수를 모두 정수로 바꿔서, consistent한 해가 존재하는지 판별하고, 그렇다면 그 해를 출력해야 한다.

만약에 row sum과 column sum이 정수라면 단순한 network flow로 풀 수 있지만, 경우가 두개라서 문제가 어려워진다. 이를 해결하기 위해서 L-R maxflow를 사용한다. L-R maxflow는 간선의 용량에 lower bound를 정해줄 수 있다. 고로, row sum과 column sum을 ceil(x)로 해놓고, lower bound를 floor(x)로 잡은 후 consistent한 flow가 있는지를 일반적 maxflow algorithm으로 찾으면 된다.

제한에 대해서 언급하자면 f, V, E = nm이다. ford-fulkerson은 잘 모르겠고 확실히 dinic은 될 거다. 물론 실제 order notation에서는 둘다 fail이다. 플로우의 오묘함... MCMF를 통해서도 L-R maxflow의 역할을 그대로 할 수가 있는데, f * SPFA 라서 얄짤없이 TLE가 난다고 한다. L-R maxflow를 유도하거나 공부해야만 풀 수 있는 문제라는 것이다. L-R maxflow는 얼마전 대전 인터넷 예선에서도 나왔고, koosaga.com에서도 다뤘던 주제다. 여러분 koosaga.com 읽으세요. 두번 읽으세요.

L. Virus

이진 트리의 루트에서 바이러스가 노드를 감염시키고, 자식 노드 중 하나를 선택해서 이동한다. 우리는 1초마다 임의의 자식 노드로 바이러스가 움직이는 것을 막을 수 있다. 바이러스가 감염시킬 수 있는 노드를 최소화해야 한다.

만약에 해당 정점의 자식이 1개 이하면, 그 자리에서 바이러스의 전파는 끝난다. 그렇지 않다면, 왼쪽이나 오른쪽 중 바이러스에게 불리한 쪽으로 이동을 강제할 수 있다. 이를 DP로 해결할 수 있다. D[i] = i번 노드를 루트로 한 서브트리에서 감염될 수 있는 최대 노드라고 정의하면, D[i] = min(D[L[i]],D[R[i]]) + 1 이다. 이런 식으로 DP를 돌려서 DP[1]을 계산하면 된다. i < L[i] / i < R[i]인 보장이 없는게 함정 아닐까 싶음.