2019 UCPC 본선 (Onsite Final) 후기

아직 문제지도 안 올라왔고, 풀이 슬라이드랑 스코어보드도 안 올라왔지만 후기는 최대한 기억이 살아있을때 쓰고 싶어서 일단 쓰기로 했다. 

그리고 UCPC 계정 정보를 챙겨놓지 않아서 우리 팀이 짠 코드도 볼 수 없고, 가장 심각한 E번은 절대로 다시 코딩하고 싶지 않기 때문에(....) 그냥 대략의 풀이 + 후기 느낌으로 갈 생각이다. 혹시라도 팀원의 노트북에 계정 정보가 남아 있다면 코드를 백준에 다시 제출해서 솔브 수를 몇개 먹을 수 있겠지만 ㅋㅋㅋ

 

https://ucpc-kr.github.io/final/

 

여기에 아마 곧 (늦어도 며칠 내로) 결과 / 문제지 / 풀이가 올라올 듯 하다.

---

B. 비트베리

Solve : Gratus907, Coffeetea, DHdroid (내가 거의 다 풀고, 이상하게 해석한 부분을 팀원들이 약간 교정해줬다)

Code : Gratus907

 

대회 시작 직후 내가 A~D를 받아들고 읽었는데, A는 일단 무슨 소린지 잘 모르겠어서 던지고 B를 읽었다. B가 딱 보니 쉬워 보이길래 그냥 바로 코딩한 다음, 문제 이해를 잘못해서 1WA, 조건을 잘못 봐서 1TLE를 적립하고 쓸데없이 페널티를 쌓았다.

$p$개의 '비트' 와 $q$개의 '베리' 가 주어지고, 이걸 다른 단위인 '코인' 과 

비트 : 코인을 $a$ : $b$, 베리 : 코인을 $c$ : $d$ 로 교환할 수 있다.

이때, 비트와 코인 중 적은 것의 개수를 최대화해야 하는 문제.

어차피 베리는 결과적으로 도움이 전혀 안 되므로, 최대한 코인으로 바꾼 다음, 교환비를 적용하면

주어진 수 $x, y, a, b$에 대하여

$\min(x + at, y - bt)$의 값을 최대화하는 문제이다.

두 직선의 교점 근처에서 최대값을 얻을 수 있다는 것을 간단히 알 수 있으므로, 그 교점을 계산한 다음, 교점의 $t$가 정수라는 보장이 전혀 없으므로 좌우로 몇개 값을 돌면서 최대화하면 된다.

---

이 다음 잡아야 할 문제에 대해서는 고민이 조금 있었다. 한 팀 (결국 우승한 팀으로, 대충 실력을 아는데 정말 엄청난 팀이다. ICPC World Final에서도 아마 메달권에 들 정도 레벨... 3명의 CF 레이팅 합이 9천점 가까이 되는걸로 안다.) 이 L을 먼저 잡아서 풀었었는데, 그 문제가 이 팀한테만 쉬운 건지 그냥 쉬운 건지를 알 수가 없기 때문이다. 예를 들어, 2017 대전 리저널 H번 같은 경우 FFT의 간단한 활용 문제라고 하던데, 이런 경우 최상위 팀에게는 거의 주는 문제지만 우리한테는 늪이 될 수도 있다. 그래도 일단 우리는 별로 선택의 여지가 없고, C랑 D는 문제도 너무 길었기 때문에 버리고 L을 읽기로 했다. 

---

L. 대진표

Solve : DHdroid, Coffeetea, Gratus907

Code : DHdroid

다행히 L번은 그냥 쉬운 문제였던 걸로(?)...

대략 요점은, 최대한 공정하게 (경기를 많이 치르는 팀과 적게 치르는 팀의 경기수가 1경기 이하의 차이가 나게) 토너먼트 대진표를 만드는데, 가능한 경우가 여러 가지면 최대한 앞으로 밀어넣으라는 문제이다.

 

몇가지 작은 예시를 해 보고 나서, $k = \lceil\log_2(n)\rceil$ 이라고 할 때, $k/4$개를 오른쪽 슬롯에 주고, 나머지를 최대한 앞으로 당기는 경우가 최선이라는 확신이 들었다. 예를 들어, 10명인 경우 다음과 같이 할 수 있다.

 

######..  ####....

 

이러면 많이 치르는 팀은 4경기, 적게 치르는 팀은 3경기를 치르며, 저것보다 나은 답을 얻을 수 없다.

$2^n$을 잘 이용하면 재귀적으로 어렵지 않게 코딩할 수 있으므로, 빠르게 DHdroid가 컴퓨터를 잡았다.

---

여기까지 상당히 빨랐다. 10등대 정도였고, 실제로는 B번에서의 많은 페널티 때문에 그런 거고 솔브 수가 3 이상인 팀이 별로 없었다. 앞서도 말했었지만, 최상위권 팀들의 스코어보드는 우리가 최상위권 실력이 아닌 한 믿을 수 없기 때문에...

나는 DHdroid가 코딩하는걸 보다가 K번이 문제가 어쨌든 이해할 수 있다는 생각이 들었고, Coffeetea는 G번 문제를 보고 있었다.

---

K. 옥토끼는 통신교육을 풀어라!!

Solve : DHdroid, Gratus907, Coffeetea, 

Code : Gratus907

K는 꽤 많은 팀들이 풀었었는데, 처음에는 회의실 배정 같은 문제라고 생각했지만 뭔가 슬롯 두개를 잘 채운다는게 좀 어려운 일 같았다. 그런 중에 DHdroid가 처음에 "이거 Parametric Search로 되지 않을까?" 라는 아이디어를 냈고, Coffeetea가 "사용된 시간을 조금 늘인 것으로 생각해도 답이 바뀌지 않는 상황" 에 대한 얘기를 했었다. 내가 두 아이디어를 합쳐서, 칸을 소모하는 식으로 생각하면 된다는 관찰을 했고, 셋이서 같이 풀이를 구체화했다.

 

어떤 시간 $T$ 가 답으로써 valid한지는 다음과 같이 생각할 수 있다.

- 어떤 문제가 $T$의 $k$배 정도 시간을 소모한다면 (이 부분을 실제로는 ceiling해 줘야 한다), 이것을 1짜리 칸을 $k$개 소모한다고 볼 수 있다. 즉, 타겟 시간 $T$가 4라면, 7짜리 일이든 8짜리 일이든 2칸짜리 일로 생각하겠다는 것이다.

- $T$에 맞춰 칸을 세었으므로, "모든 칸에 대하여, 그 칸을 끝으로 하는 일이 적어도 하나 존재해야 한다". 이게 필요충분조건이다.

두 슬롯 중 하나에는 1짜리를 넣어야 하고, 2짜리는 반대 슬롯에 넣을 수 있고... 이런 식으로 해 보면, 

1칸짜리 일은 +1, 2칸짜리 일은 0, 3칸짜리 일은 -1, ... $n$칸짜리 일은 $2-n$ 숫자라고 생각한 다음, 전부 합한 값이 양수이면 가능하고, 음수이면 불가능하다.

대충 생각은... 3칸짜리 일을 조건에 맞게 끝내기 위해서는, 1칸짜리 일 적어도 1개를 소모해야 한다. (처음에 1개를 쓰면서 한번 어긋나 있기 때문에, 반대쪽 슬롯에 1짜리 하나를 잘 넣어 주기만 하면 된다). 이런 식으로 생각해서, 1칸짜리 일들의 수가 충분한지 세겠다는 발상이다.

 

즉, 시간 $T$에 대한 검사를 $O(n)$ 에 할 수 있다는 말이 되므로, 

전체 문제를 $O(n \log A)$ 에 풀 수 있다.

코딩은 내가 빠르게 잡고 밀었고, 3솔브를 굉장히 빠른 시간에 받아서 순간적으로 10등 정도까지 했었다. B번 페널티 2개를 생각하면 초반 스퍼트는 우리 실력에 비해서 확실히 잘한듯.

---

스코어보드를 참고할 수 없는 상황에서, DHdroid의 선택은 A, Coffeetea의 선택은 G였다. 둘이 같이 G번을 조금 보다가, DHdroid가 "이거는 풀이도 잘 모르겠지만, 알아도 못 짜겠다" 라고 버리고 넘어간 것 같았다. (K번 짜느라 사실 정확히는 못 들었다) 아무튼, A번에 대해서도 뭔가 얘기를 하고 있는 것 같았다. 

K번 AC를 받아낸 다음 나는 사실 A도 G도 자신이 없었고, 이번 셋이 작년 UCPC보다 훨씬 어렵다는 생각도 이때쯤 했다. 작년 셋은 적어도 아기석환 뚜루루뚜루 / 더위 피하기 / Thinking Heap / Make Simillar 까지는 쉽게 풀었다는 생각을 했는데, 올해 셋은 2번째와 3번째 솔브부터 3명이 달려들어서 풀이를 조금 더 힘들게 하나씩 완성해 나간다는 느낌이 들었다. 푸는 재미는 이게 더 있긴 하지만, 4번째부터는...흠...

 

이렇게 시간이 지나다가, 1시 쯤 (대회 시작 150분 쯤) 상황은 대략 이렇다.

- DHdroid랑 나는 A번이 Persistent Segment Tree를 짜서 풀 수 있다는 생각을 했다. PST를 팀노트에 넣어야 한다는 생각은 했는데, 솔직히 나는 이 자료구조를 아직 전혀 이해하지 못했고, "아무튼 어떻게 어떻게 잘 해서 $N$개의 세그먼트 트리가 있는 것처럼 쓰는데 공간은 아무튼 $O(N \log N)$ 밖에 안 쓰는 마법의 자료구조" 같은 느낌으로 생각하고 있어서, 도대체 뭘 어떻게 가지고 와야 할지를 몰라서 넣질 못했었다. DHdroid가 자기가 한 번 짜본 적이 있으니 구현 해보겠다고 말했고, 솔직히 본인도 자신 없다고 했지만 그냥 컴퓨터 주고 믿는거밖에 딱히 할 수 있는게 없었다.

- E번 (Taxi) 가 문제지가 무려 5페이지였다. 테스트케이스는 뭔지 모르지만 띄어쓰기가 포함된 String이 수없이 많이 주어지고 (...) 지문만 한 페이지가 넘으며, 아무튼 뭔가 이상하게 생긴 그림같은게 그려져있고, OUT OF GAS 니, 연료 가격이니 하는게 보이는 순간 지난 학기에 고통받은 컴프의 Flying Car 과제가 생각나서 도저히 하고싶지 않았다.

- 그치만 딱히 방법이 없기도 했고, PST를 이해하지 못한 나랑 Coffeetea가 도와줄 수 있는게 없었기 때문에 둘이 페어코딩해서 E번을 맞춰야만 한다는 생각을 하기 시작했다. 마침 DHdroid가 손으로 더 써보고 들어가야겠다고 말해서, 그동안 E를 어떻게든 해보고 싶었다.

---

E. Taxi

Solve : Gratus907, Coffeetea

Code : Gratus907, Coffeetea

진짜 통곡의 벽. Piet급 문제인데, Piet보다는 약간 쉽..나?

무려 14번을 틀린 끝에, 3.8KB의 코딩을 해서 AC를 진짜 간신히 받았다.

 

문제가 너무 긴 데다 수학적인 모델링이 되는것도 아니긴 한데, 대충 설명하자면

- 택시의 연료통 크기, 연비 (1갤런당 갈 수 있는 거리) 가 주어진다.

- 목적지가 되는 점들의 이름과 좌표가 주어진다.

- 주유소의 이름과, 그 주유소에서 주유를 할 때 연료 1갤런당 가격이 주어진다.

- 쿼리가 주어지는데...

쿼리 1 : 목표하는 지점이 주어진다. 그곳으로 이동을 시도한다.

쿼리 2 : 현재 지점에서 승객이 탑승을 시도한다. 승객은 각각 원하는 목적지가 있다.

이동과 탑승을 '시도' 하는 이유는,

- 연료가 모자라서 못 갈 수도 있다.

- 승객이 3명 이상 타 있는데 4명째가 타려고 시도하면 실패한다.

 

그리고 대충 주유소에 도착하면, 가득 채울 수 있으면 가득 채우고 돈이 모자라면 최대한 채우고 간다. 

 

시간 제한은 별 의미가 없으므로, 그냥 열심히 구현하면 된다!

 

이 문제가 힘들었던건 그냥 구현량이 많고 description이 긴 것도 있지만, 우리가 익숙하지 않은 문자열 파싱을 미친듯이 해야한다는 점이 첫 번째. 이름이 문자열로 주어지는데, 이름만 곱게 한줄에 주는것도 아니다. 만약 Seoul Univ 가 (10, 0) 에 있다면 주는 문자열은 "Seoul Univ 10 0" 이런 식이니까 파싱해야 하고, 쿼리도 "Go to Seoul Univ." 같은 식으로 줘서 끝에 점도 떼야 하고... 아무튼 넋을 놓고 코딩을 하기 시작했다. 

 

map <string, pii> 와 map<string, int> 같은걸 쓰고, scanf로 띄어쓰기 포함된거 받고 파싱하기 귀찮으니 getline과 섞어쓰고 C++ string으로 받은다음 필요할때마다 .c_str() 를 붙이는 등 극혐코드를 짰는데, 처음에 짠 코드는 당연히(...) 실패했고, DHdroid에게 컴퓨터를 넘기고 출력을 요청했다. 이때만해도 한두번 디버깅 해보면 될줄 알았다.

 

Coffeetea가 나보다 대략 10억 7배쯤 (...) 꼼꼼한 편이라서, 수없이 많은 테스트 케이스를 제공했다.

내가 놓쳤는데 Coffeetea가 알려준 것들이 대략 이런 것들이 있었다.

- 끝에 가서 승객을 태우면 어떻게 되지? 

- 끝에 가서 승객을 태웠는데 그 사람이 4명째면?

- 파싱할 때 $i+1$번째까지 해야 공백 날아가지 않냐?

 

아무튼 이것들을 전부 고치고, 드디어 예제가 나온다! 라고 생각했더니 약간의 실수 오차가 있었고, +0.00001을 더해서 오차를 적당히 잡아주니까 나오는 것처럼 보였다. 그리고 냈더니 40%에서 틀렸다.

 

DHdroid랑 우리 둘이 번갈아서 컴퓨터를 잡아 가면서, 조금씩 구현하고 조금씩 디버깅하고를 반복했다. 그러다 보니 코드가 4800바이트 (260줄 정도) 까지 가버렸고, 이걸 계속 제출해 보면서 (이때쯤 이미 페널티는 관심 없었다) 고쳤는데 14번을 틀렸다. 일단 뭔가 고쳤다는 착각 하에 막 내본게 한 5번 정도 있다는걸 생각해도, Coffeetea가 고쳐준 미스만 한 8개 정도 있다. 이건 진짜 코드가 틀렸던 게 맞다 (double을 써야 하는 자리에 int를 썼다든가, 캐스팅하고 넣어야 하는데 넣고 캐스팅 했다던가 하는 초보적인 실수들). 그니까 일단 뭔가 계속 고치고는 있었으니, 다른 뭔가를 해볼 수가 없었다.

 

이 시점에 대회가 40분 남았고, 침착하자는 말을 서로 하면서도 다들 반쯤 미쳐서 코드를 5번쯤 출력 요청해 가며 (매번 200줄 정도의 코드를 요청했는데, 받고 나니 정리하는 것도 꽤 일이었다) 보고 있었다.

 

결국 원인은 내가 찾았는데, 

"가득 채우기 위한 돈이 충분하지 않은 채로 주유소에 도착했을 때" 

올바른 방법은 

1. 가진 돈으로 살 수 있는 기름의 최대 양을 구하고

2. 그만큼 기름을 채운 다음

3. 돈을 비우면 된다.

 

그런데 뭔가 의식의 흐름대로 짜다 보니 순서가 뒤섞여서

1. 일단 가진 돈을 전부 버리고 (?) 

2. 가진 돈으로 살 수 있는 기름의 최대 양은 당연히 0이니까

3. 그냥 지나간다.

 

????????

아무튼 이런것들을 고치는데 코딩 시작 시점부터 대략 2시간 정도 걸려서, 2시간 만에 15번째 시도에 맞았고, 진짜 되게 좋아하는 표정이 인상적이었는지 (...) 스태프 분이 사진을 엄청 찍으셨다. :ft:

---

A번을 코딩해 보려고 했지만 20분 남아서 실패. 근데 진짜 직전까지 갔다. PST 구현 한번 해봤다는것치고는 잘 짜는거 같았는데, 아무것도 도와줄 수 있는게 없어서 너무 무력했다.

---

대회 끝나고 나서

처음으로 치러본 온사이트 대회 (SNUPC는 예선이 없으니까 제외하고..) 인데, 나름 재밌었다. 5시간짜리 셋이 너무 힘들긴 한데, 앞으로 ICPC나 다른 대회들 준비하려면 익숙해져야 하는 부분이기도 하니까...  좋은 경험이라고 생각한다 :)

 

후원사 설명회를 듣고, 풀이를 들었는데 정말 손도 못 댈 것 같은 문제들이 너무 많았다. A번은 PST 또는 오프라인 쿼리로 바꿔서 세그먼트트리 쓰는게 정해였고, 결과적으로는 DHdroid의 풀이가 맞는 풀이였다. 못 짜서 그렇지...

남은 방학 동안은 자료구조 공부에 신경을 좀 써야 할 것 같다. 세그트리, 펜윅, PST 같은것들..?

 

A번을 못 푼게 너무 아쉬웠지만, 결과는 31등으로 우리의 목표보다는 높았다. 같이 관찰들 제시하고 풀이를 만들어가는 과정이 잘 굴러가서, 혼자 풀었으면 엄청 오래 걸렸을 K번 같은 문제를 같이 풀 수 있었던듯 하다.

 

팀으로 치르는 다음 대회는 2019 ICPC Preliminary로, 목표는 딱 리저널 진출 정도. 지금 우리 실력으로는 약간 어려울 것 같고 10월까지 계속 연습 하면 해볼만 할수도 있다고 생각한다. 이 팀은 꽤 오랫동안 갈 수 있을 것 같다는 생각이 들어서... 아마 8월 중에도 한두번 더 팀연습 할 수도 있을 것 같다. 일정만 맞는다면? ㅋㅋ 

 

앞으로도 파이팅해서 리저널 꼭 갔으면 좋겠다 ㅋㅋㅋ 

 

+ 같이 팀연습 돌았었던 I HATE PS 팀이 무려 17등 했다. :fan: 이예요!