2020 UCPC 인터넷 예선 후기 / 풀이

Update : G번의 제한시간에 대한 정정을 두번 받았고, 생각난김에 코드를 추가한다.

[코드 링크]

* 대회 종료 시간으로 예약 작성하였습니다 :) *

작년의 Little Piplup 그대로 올해도 UCPC에 참여했다. 올해로 3번째 참여하는 UCPC고, 이 팀으로 참여하는 공식대회도 꽤 많았지만 나름 각별한 느낌이 좀 있는데, 팀원들의 병특 시작 등으로 (아마도) 이 3명 그대로 참여하는 마지막 대회일 수도 있어서.... 앞으로도 PS는 같이 할 것 같지만, ICPC에서 휴학생이 참여할 수 없다는 점이 크다. DHdroid의 병특 결과에 따라 내 ICPC 팀도 결정될 예정.

후기 느낌으로 쓰면서 풀이를 Discuss하는 글이기 때문에, 문제 풀이만을 확인하기에는 별로 좋지 않다. 생각하는 흐름 그대로 적는게 나중에 봤을때 제일 기억에 남는거 같다. ㅋㅋ

 

-1. Due to technical issues... + is it rated? (13시 30분~15시)

모여서 대회 준비 + 세팅 하고, 대기하면서 팀원 두명의 내일 정보처리산업기사 시험에 대한 얘기를 했다. 사실 예선은 어떻게든 통과할 거라는 생각을 했기 때문에... 현재 우리 팀의 전력을 생각해보면 사실 한명 없어도 (한명이 문제 하나를 들고 뇌절하기 시작해서, 사실상 아무것도 못하는 상황) 예선통과는 비빌수 있을거라고 생각했다. 

 

14시 대회 시작과 동시에 서버가 터졌다. 작년에도 비슷한 일이 있었고, 작년에는 서버가 끝날때까지 제대로 복구되지 않은 끝에 결과가 하루 뒤에 나오는 참사가 벌어졌기 때문에 팀원들 다같이 약간은 그러려니 하고, 욕좀 하면서 대충 기다리고 있었다. 30분동안 서버가 복구가 안되는건 너무하지 않나 생각하는 도중, 주최측에서 대회의 연기는 없으며, 서버 장애 시간만큼을 연장하여 치뤄질 것이라는 메일을 보내왔다. 

 

2019 UCPC, 2019 ICPC 등 주요 대회에서 서버가 터지는 것쯤은 이미 일상이 되었지만, 1시간여 동안 터지면 대회가 정상적으로 진행되기는 어려운 상황이다. 참가자가 많아서 그러려니 하긴 하지만, 평소 BOJ의 서비스를 이용하는 인원이나 이런 부분들을 생각하면 그렇게까지 서버가 힘들어야 할 부분인가 싶기도 했고.... 나는 네트워크나 이런 쪽에 대한 지식이 전혀 없고, 주최측 및 BOJ (Startlink) 의 운영진 분들이 정말 많은 노력을 하셨음은 알고 있기 때문에 불가항력적인 일일 것이라고 믿기로 했다.

 

0. 어쩌다 보니 Qualification Round (15시 - 16시)

15시쯤 메일로 이번 라운드는 Qualification 형식으로, 일요일 오후 12시까지 4문제 이상을 푼 팀을 모두 진출 처리하겠다고 결정 사항이 왔다. 약간의 문제라면 나를 제외한 2명이 내일 오전에 시험이 있고 산기 시험은 그냥 벼락치기로 중학교 기술가정마냥 외우는 거라서, 이걸 무한정 붙잡기는 애매하다는 점인데, 사실 작년이나 재작년 셋 기준 4솔브면 나혼자 돌아도 저녁중에 가능하기때문에 일단 그렇게 해보자는 얘기도 했었다. 서버가 돌아올때까지 딱히 할일이 없으므로 산업기사 얘기를 하거나, 롤토체스를 하는 등(...) 시간을 때웠다. 

문제지가 메일로 전송된게 15시 경인데, 이때 문제지를 메일로 전송했음을 몰랐기 때문에 그냥 1시간 정도 놀았다. 

 

1. 라운드 시작 + A D G H (16시 - 16시 30분)

16시쯤 문제지가 메일로 왔다는걸 알았고, 그쯤에는 서버가 정상화되었다. 일단 문제지를 인쇄한게 16시 10분 정도고, 바로 스코어보드를 보고 쉬운 문제 4개를 빠르게 쳐내기로 했다. 쉬운 문제가 A D G H임을 알았기 때문에 내가 A, Coffeetea가 G, DHdroid가 H를 일단 맡았고, A를 코딩하는데 2분 정도 걸렸기 때문에 그냥 내가 D를 마저 하기로 했다.

 

1.1 A : 수학은 비대면강의입니다

Solve : Gratus907

Code : Gratus907

해가 존재함이 보장되는 일차연립방정식을 푸는 문제. 해의 범위가 $(-1000, 1000)$ 안의 정수임이 주어져 있고 맞춰야 하는 수가 $x, y$ 밖에 없어서, 생각할 필요 없이 모든 경우의 수를 돌면 된다. 만약 해의 범위가 크거나 구해야 하는 수가 많다면 행렬을 이용한 뭔가를 구현해야 했을 것이다.

코드 : [추가 예정]

 

1.2 D : ㄷㄷㄷㅈ

Solve : Gratus907

Code : Gratus907

Tree가 주어지고, 정점이 4개인 ㄷ자 형 (1자 형) 이나 ㅈ자 형 (정점 하나에 다른 정점 3개가 달려 있는 형태로, ㅈ보다는 Y자형으로 생각하면 된다. Y의 중심과 세 끝점에 하나씩) Subtree가 원래 트리에 몇개나 들어 있는지 찾는 문제이다. 

각각을 나누어 찾자. ㄷ자형의 개수는, 각 간선 $e \in G$ 마다, $e$를 중심간선으로 하는 ㄷ자의 개수를 센다. $e$가 $(l, r)$ 간선이라면, $l$의 왼쪽에서 점 하나 더, $r$의 오른쪽에서 점 하나 더 고르면 되므로 $d_t$를 $t$의 Degree라 할 때 $(d_l - 1)(d_r -1)$ 이 $e$를 중심간선으로 하는 ㄷ자의 개수이다. 

ㅈ자형의 개수는, 중심정점을 기준으로 중심정점의 degree $d_x$에 대해 $\binom{d_x}{3}$개를 찾을 수 있다.

코드 : [추가 예정]

여담으로, 두두둥장~이라는 meme에서 따온 문제라서 제목도 그렇고 출력 내용이 두두둥가 트리라는데 난 뭔지 몰라서 계속 둥가둥가 트리라고 읽었다. 다행히 예전에 한번 당한 이후로 정해진 출력은 최대한 복붙하고 있다.

 

A D를 풀고 나니, 팀원 두명 다 각각 G, H 풀이 알았으니 구현하겠다고 말했다. 본선 쉽게 가네 ㅋㅋ 라고 생각하며 남은 문제중 그나마 많이 풀린 J를 잡았다.

 

1.3 H : 사과나무

Solve : DHdroid

Code : DHdroid

안 읽었는데 끝나고 들었다. +1과 +2를 항상 동시에 쓰는 연산을 +연산이라고 할 때, +연산만 써서 주어진 최종상태를 맞출 수 있는지 묻는 문제. +2를 한번 쓰는 대신 항상 +1 두번으로 대체할 수 있으므로, 최대한 많은 +2 연산을 쓰면서 가보려고 시도하면 되는 Greedy 문제라고 한다.

코드 : [추가 예정]

 

1.4 G : 루머

Solve : Coffeetea

Code : Coffeetea

안 읽은 문제 2. 뭔가 BFS를 쓰면서 따라가면 된다고 한다. 이제 보니 제한시간 1초인 문제에 500ms 가까이 썼던데, 코딩 문제인지, Python 같은 언어로는 못 풀게 낸 건지 잘 모르겠다. 

제한시간이 10초고 BFS를 쓰면서 따라가게 낸게 맞다

코드 : [추가 예정]

 

G AC를 맞은 시간이 16시 30분 쯤으로, 대략 30분만에 4문제를 밀고 J를 그래도 풀어보자고 했다. 

 

2. J : 역학 조사 (16시 30분 - 17시 30분)

다 같이 풀고, 내가 코딩 잡았다.

$N$ 명 (10만) 의 사람들이 $M$번 (10만) 모임을 갖고 (단, 모든 모임의 참여자 수의 합 $\sum k_i$ 는 100만 이하), 병에 걸린 사람과 모임에서 만난 사람은 반드시 병에 걸린다. 최종적으로 병에 걸린 사람들의 정보가 주어질 때, 처음 상태를 알 수 있는가? 라는 문제. 

내가 살짝 미스난 풀이를 제시했는데 어설픈 확신으로 뇌절을 시작해서 많이 틀리고 시간을 많이 잡아먹었다. 

처음 생각한 부분은, clean과 dirty를 구분하자. clean은 확실히 처음에 걸려있지 않은 사람이고, dirty는 알 수 없는 사람이다. 만약, '최종적으로 아프지 않은 사람' 과 모임에서 한번이라도 만난적이 있다면, 처음부터 아팠을 수는 없다 (만약 그랬다면, '최종적으로 아프지 않은 사람'과 만났다는 점에 모순) 그래서, 시간 순으로 따라가며 모든 clean 한 사람을 제끼고, 나머지 모두가 일단 처음부터 아팠다고 가정한 다음, 시뮬레이션을 돌려서 진짜 그 결과가 나오는지 판정하는 방법을 썼다. 이 과정에서 많은 WA를 받았는데,

- 마지막에 아픈 사람이 단 한번도 모임에 나타나지 않고 그냥 끝까지 혼자 있는 경우를 고려하지 않아서 1WA

- dirty 라고 추측되는 사람만 생각하고 그 사람들과 만난 사람들을 마킹하지 않아서 1WA

등등... 이 코드들을 디버깅하는 과정에서, $2^n$개의 가능한 모든 조합을 이용해 시뮬레이션하는 Bruteforce를 짜서 10명, 5번의 모임으로 수백번의 Stress-testing을 했다. 디버깅에 상당한 문제가 있는 나한테는 괜찮은 방법인것 같다.

아무튼, Stress test + 손으로 반례들을 직접 돌리다 보니 알고리즘의 문제가 있음을 알게 되었다 (clean한 사람 중, 최종적으로 아프지 않은 사람과 만나지 않았어도, 이미 clean함이 보장된 사람과 만났던 사람은 clean함이 논리적으로 보장된다). Coffeetea랑 DHdroid가 틀린 부분을 고쳐서, 시간 순이 아닌 시간 역순으로 보며, clean함을 만난 사람들에게 전파하는 방식으로 로직을 고쳐서 맞았다. 

 

 

3. E : 감자 농장 (17시 30분 - 18시 30분)

E와 I 중 뭘 잡을지 고민하다가, E를 먼저 잡기로 했다.

1차원 지도상에 감자와 돌이 주어지고, 빈 칸에서 시작할 수 있는데,

- 감자를 만나면 감자를 캐서 없애고 반대 방향으로 돈다

- 돌을 만나면 반대 방향으로 돈다

각 시작점 (빈 칸)에 대해 캘 수 있는 감자의 개수와, 만약 농장 밖으로 나가게 된다면 그 시간을 출력하는 문제.

 

나는 보자마자 [ABC 136D]를 생각했다. 이때 대충 뭔가 비슷하게 좌우로 돌면서 시간에 따른 움직임을 tracking 하는 문제였는데, 내가 공식 솔루션과 다른 풀이를 짜서 맞았다. 그때 풀이는, dp[i][j] 를 i 지점에서 출발해서 $2^j$ 시점에 도착하는 위치라고 정하고, dp[i][j]를 갱신할 때 dp[dp[i][j-1]][j-1]을 이용해서 빠르게 갱신하는 방법으로, [블로그에 예전에 썼던 풀이 링크: D번] 이 문제는 지금 방향이 중요하므로 dp[i][j][k] 로 100만 * 20 * 2 DP를 짜려고 했다.

뭔가 그럴듯해서 (이 풀이를 빨리 떠올려서 팀원들이 꽤 감탄했었는데, 결국 아니었다. ㅋㅋ) 코딩을 시작했는데, 생각해보니 이렇게 하면 감자를 한번 캐면 없어져서 이제 그 지점에서 돌지 않는다는 사실을 반영하지 못한다. 결국 DP 풀이를 버리고 다시 생각하기로 했다.

 

셋이 같이 생각해서, 결국 '양쪽에 돌이 있는 경우', '한쪽에 돌이 있는 경우', '돌이 없는 경우' 로 나누어 풀면 됨을 관찰했고, 이중 경우 1은 쉽게 풀 수 있음을 알았다. 어차피 돌 밖으로 못 나가고, 그 안에 있는 감자는 다 먹을 수 있다.

Coffeetea가 2번 케이스를 잘 쳐다보다가, "시작점 $t$에서의 답을 알고 있다면, $t+1$에서의 답을 충분히 빠르게 구할 수 있을 것 같다" 라는 관찰을 했다. 구체적으로는, 어차피 한쪽에 돌이 있는 경우만 보고 있으므로, 시작점을 왼쪽부터 보면서, 감자를 하나 넘을때마다 경로의 모양이 조금 바뀌고, 그 외에는 경로의 모양이 거의 그대로이다. 감자를 넘을 때를 생각해 보면, '내 왼쪽에 있는 감자'와 '오른쪽에 있는 감자'를 deque같은 자료구조로 관리하면서, $r_0, r_1, r_2, \dots $ 와 $l_0, l_1, l_2 \dots$에 대한 식으로 결과값을 쓸 수 있다. 감자를 하나 넘는 연산을 오른쪽을 관리하는 deque에서 왼쪽을 관리하는 deque로 넘겨준다고 생각하면, 이에 맞는 결과값 업데이트를 $O(1)$ 에 할 수 있다. 식 정리를 나랑 DHdroid가 같이 해서, 이 문제를 이렇게 풀면 되지만 구현이 끔찍할 것 같다는 얘기를 하면서 시간을 보내다가 대회가 끝나고 저녁 먹으러 갔다. ㅋㅋ

 

밤에 구현을 시도해 봤는데, 6,500Byte를 코딩하고 실패했다. 그리고 그냥 포기하기로 했다. 다른 방법이 있는게 아니라면, 구현이 좀 지나치다는 느낌이...

 

 

4. I : 인버스 ㄷㄷㄷㅈ

Solve : DHdroid

Code : Gratus907 (사실 한거 별로 없다)

DHdroid가 (하라는 정처산기 공부는 안하고;;) 결국 I를 풀었다. DHdroid가 이런 관찰 / 패턴 찾기 / Construction 류에 굉장히 강한데, 그 덕을 많이 봤다. 풀이 대신 '이렇게 구현하면 된다' 라고 사진 한장이 딱 왔는데, 진짜 그대로 짜서 맞았다 (...) 진짜 패턴 그대로 구현하면 되기 때문에, 풀이 대신 DHdroid가 그려준 그림을 보고 내가 코딩하기 위해 다시 그린 그림만 올리면 충분한 것 같다. 

6k+8 형태가 약간 이상한 것은, $k = 1$일 때 일관성을 갖기 위해서이다. $k = 2$부터는 사실 왼쪽 십자가에 3개, 오른쪽에 2개 붙여도 된다고...

DHdroid가 저만큼 정리해서 줬기 때문에, ad hoc 식의 코드를 잔뜩 짜서 그대로 넣었다. ㅋㅋㅋㅋ

 

5. 예선을 마치고

본선에서 목표는 대충 20등대 등수인데, 올해는 팀연습도 몇번 못하고 (Japan ICPC Preliminary만 2번 돌았는데, 그건 나중에 포스팅하려고 한다) 본선도 비대면인 등 하여튼 뭔가 많이 꼬인 해라서 (사실 다른거 꼬인거에 비하면 이건 매우 잘 돌아가는 거라고 생각할수도 있겠다만) 어떨지 모르겠다. 파이팅! ㅋㅋ