[ICPC] ICL 2016 (GP of Tatarstan) 후기 & 잡설들

Intro

고려대학교 2020 ICPC 팀이 한 팀 결성되었습니다!

• ryute, 20학번, 퍼플
• seyun, 19학번, 오렌지
• cheetose, 군인, 오렌지

cheetose님이 저에게 팀 하자는 제안을 주셨고, seyun님도 cheetose님한테 팀 하자는 제안을 드린 것 같아서 영문도 모른 채 3인 팀이 구성되게 되었습니다. 저는 오렌지 둘의 버스를 탈 수 있으니 대만족이고, 현재 음료수와 간식을 배달하고 분배하는 업무에 숙달되기 위해 오늘도 열심히 노력하고 있습니다. 입학하기도 전에 버스팀이 생기는 사람이 있다? 

서로 얼굴을 본 적이 없다는 이유로 만나서 밥을 먹기로 했습니다. cheetose님이 밥 먹기 전에 셋을 하나 돌자고 하셔서 솔직히 불안했습니다. 오렌지 2명 사이에 끼어서 노솔브 하면 어떡하지? 고민을 줄창 하면서 걷다가 지하철을 잘못 탔습니다. 두분은 약속시간보다 30분이랑 15분 빨리 오셨는데 첫만남부터 20분 지각했습니다 :( 심지어 길도 잃어서 커피전문점 잘못 찾아갔습니다 ㅠㅠ

진짜 들어가서 급하게 커피 사오고 아무런 사전 대화 없이 자기소개 없이 무작정 대회 셋을 돌기 시작했습니다.

진행 상황

이번에 돈 셋: https://codeforces.com/gym/100942

컴퓨터는 3대를 모두 사용했습니다. 문제가 A부터 M까지 총 13문제 있었는데, 4/4/5로 seyun님, cheetose님, 그리고 제가 나눠서 읽었습니다. 

G - Pots (11 min)

쉬운 문제인 것 같았고, cheetose님이 쉽게 어셉 받았습니다.

M - The smallest fraction (18 min)

매우 쉬운 lcm/gcd 문제입니다. 분수들이 주어질 때 각 분수에 대해 나눠지면 모든 경우에 양의 정수가 나오는 최소의 분수를 출력하면 됩니다. 제가 보고 약간의 뇌절 후 바로 AC 받았습니다.

이 시점에서 seyun님이 C를 풀다가 WA를 받으셨습니다. 

H - Messenger (38 min)

Splay Tree 연습문제라고 합니다. cheetose님이 밀어주셨습니다.

cheetose님은 이 시점에서 F를 잡고 포함배제 풀이를 코딩하시기 시작합니다.

I - Manhattan Project (40 min)

간단한 관찰로, $|x-y|= \max (x-y,y-x)$ 입니다. max 쿼리는 처리하기가 귀찮고, 4개의 식이 모두 최대일 때 총 결과도 최대인 것이 자명하므로 각 식에 대해서 $x-y$가 최대, $y-x$가 최대인 두 경우에 대해서 다 해봐도 문제는 없습니다. 따라서 모든 좌표에 대해서 좌표를 그대로 둘 건지, 부호를 바꿔서 뒤집을 것인지를 결정합니다. 쿼리를 처리할 점이 주어지면, 기존에 저장해두었던 점들과 각 차원에 대해 (부호를 바꾼 여부)를 반대로 해서 차를 구합니다. $2^4$가지 경우에 대해서 모두 해 본 다음 결정하면 됩니다. 점 관리는 set으로 해주면 되고, 어차피 절댓값 떼고 다 더할 거니까 처음부터 더한 수를 집어 넣어도 상관이 없습니다. 빠르게 제가 읽고 코딩해서 AC 받았습니다.

여기서 seyun님이 C를 계속 AC를 받지 못하시면서 말리기 시작합니다. cheetose님은 계속해서 포함배제 코드를 짜고 계시고, 전 C와 K를 도전하다가 포기하고 푼 사람이 별로 없었지만 쉬워 보였던 J로 넘어갑니다. 여기서 시간을 많이 낭비합니다.

J - Liquid (104 min)

그냥 문제에서 하라는 대로 구현하면 되는 동적 세그 레이지 위에서 이분탐색하는 문제입니다. 디스크립션이 더러워서 초반에 많이 안 풀리긴 했는데, 결과적으로는 많이 풀린 것 같습니다. 처음에 세그를 잘못 짜서 좀 해멨는데, 고치고 바로 맞았습니다.

제가 liquid를 풀고 F를 같이 보기 시작합니다. seyun님도 F를 같이 보고 계셨습니다. 대충 이 쯤 E를 보고 예외처리의 개수를 확인한 다음 풀기를 포기합니다.

F - GCD and LCM (129 min)

포함 배제가 필요하지 않은 것 같이서 제가 다른 식을 찾아내 검증하는 동안 seyun님이 똑같은 식을 cheetose에게 전달합니다. 맞는 풀이라는 사인을 던지고 seyun님이 바로 코딩해서 조금 있다가 AC를 받습니다. 풀이는 LCM을 GCD로 나눈 다음 소인수분해하고, 각 소인수에 대해서 $(a+1)^k - 2a^k+(a-1)^k$를 모두 곱한 것입니다. 최소한 하나의 수에는 LCM이 있어야 하고, 최소한 하나의 수에는 소인수가 전혀 존재하지 않는다는 것을 식으로 정리해주면 됩니다. 소인수별로는 독립입니다.

셋 모두가 seyun님이 보던 C가 굉장히 쉬운 문제임에도 불구하고 왜 못 푸는지를 고민합니다. 저는 그 사이 B를 보러 튑니다. 문제를 보고 행렬 전이가 쉬운 꼴이라 벌레캠프를 박으면 풀지 않을까라는 킹리적 갓심을 합니다. 풀이를 전달하고 다시 seyun님의 C를 풀다가, 저 또한 맞왜틀을 하면서 심하게 말리기 시작합니다.

B - High-Speed Pedestrian walkway 1.0 (198 min)

제가 문제를 읽고, 요약하고 유의점을 체크해서 벌레캠프를 돌려달라고 cheetose님한테 전달합니다. cheetose님이 DP를 짜고, 항을 벌레캠프에 넣습니다. cheetose님이 몇 번의 디버깅을 진행하신 다음 마지막으로 제가 반례를 전달해 조금 고쳐 쉽게 AC를 받습니다.

cheetose님한테 L을 보여드렸더니 KOI에서 본 문제라면서 바로 코딩에 들어가셨습니다. 그 동안 저는 A를 읽고 문제를 전달했고, seyun님이 캐치해서 A를 들고 가셨습니다. 저는 C를 계속 코딩하다가 포기하고 K와 D 등을 기웃거리기 시작합니다. 

L - Three machines (256 min)

뭔가 두 차가 배수 관계면 된다고 합니다. 풀이를 잘 모릅니다.

K - Synonymous Words Number System (286 min)

왜 되는지 모르겠습니다. 저는 16N 조건이 있기 때문에 항상 가능한 모종의 constructive algorithm이 있지 않을까 생각했지만, 그렇지 않음을 찾았습니다. cheetose님이 미트인더미들처럼 혹시 둘다 정규화시켜서 왼쪽으로 최대한 밀고 되는지 확인하면 되지 않을까라고 하셨고, 그대로 코딩하셔서 마지막 솔브를 추가합니다.

이 시점에서 A를 seyun님이 잡고 계시고, 남은 둘이서 D - Camelogistics와 안 풀린 C를 계속 보고 있었습니다. 결과적으로는 D 풀이를 못 찾았고, A가 끝내 풀리지 않으면서 연습이 끝납니다. 최종 결과는 9 solve, 그러나 너무 많은 패널티 1360으로 9솔브 중 뒤에서 2등을 가져갑니다. C를 못 푼 것에 대한 많은 아쉬움이 남습니다. 

대회가 끝난 시점에서 문제 난이도는 푼 사람 수 기준 쉬운 문제부터 G-M-F-C-H-I-J-B-K-D-L-A-E 입니다. 어려운 문제가 다 앞에 몰려 있었는데, seyun님이 그것 때문에 많이 말리시지 않았나 해서 좀 슬픕니다. 뒤쪽 어려운 문제는 cheetose님이 다 밀어주셔서 행복했습니다.

마무리

저녁을 먹으면서 적당히 수다를 떨다가 헤어졌습니다. 처음으로 제대로 팀 짜서 돈 셋이었는데, 재밌었습니다!

다음 ICPC 연습이 기대됩니다. 공부 많이 해야지