눈물의 서울리저널 후기입니다. 결론부터 말하면 화끈하게 말아먹었습니ㄷr,,,,,

작년과 동일한 팀으로 출전했고 여름부터 본격적으로 팀연습을 했습니다. UCPC / Kaist Mock Competition 등을 포함해 대략 20개 정도의 셋을 돌았고 어느 정도의 기복은 있었지만 그래도 확실히 작년보다는 잘해졌고 리저널에서 좋은 성과를 낼 수 있겠다고 생각했습니다.

작년과 달리 월드파이널에서 사용하는 컴퓨팅 환경을 그대로 사용해 CLion이 제공되었습니다. 작년에 코드블럭에서 화끈하게 데인 기억이 있어 CLion을 쓸 수 있는 것이 마음에 들었습니다.

대회 당일, 2시간 10분 쯤에 6솔브에 도달했습니다. 이때까지 1번도 틀리지 않고 무난하게 흘러갔습니다. 제가 B에서 모든 정점간 거리의 제곱의 합이라고 문제를 잘못 이해해서 시간이 끌렸던게 좀 아쉽긴 했지만 엄청 말린 것 까지는 아니었습니다.

이후 조금씩 풀리고 있던 G, K를 봤고 저는 K로 들어가 약간의 고민 끝에 세 점을 잡아 평면을 만들어 아래 위를 나누는 O(n^4) 풀이를 착안해냈고 100% 완벽하게 정당성을 증명한 것은 아니었지만 적절한 평면으로 두 그룹을 나눔은 확실해보였고 그 평면을 살짝만 비틀면 세 점에 걸치게 할 수 있을테니 충분히 가능한 풀이라는 생각을 했습니다.

제가 공간 기하에 굉장히 약하지만 팀노트에 "삼차원에서 특정 점이 세 점으로 이루어지는 평면의 위에 있는가? 아래에 있는가?"를 구해주는 라이브러리가 이미 있었기 때문에 날로 먹는게 가능한 상황이었습니다.

n = 100이어서 시간이 살짝 걱정되었지만 로컬에서 테스트해보니 대략 0.8초 정도가 걸리길래 TLE는 발생하지 않을 것 같다 싶었습니다.

이런 상황에서 코드를 작성해 제출하니 Wrong Answer를 받았습니다. Wrong Answer는 예상하지 못했어서 굉장히 당황하며 혹시 "round to"의 의미를 잘못 이해했나 싶어 "round to"가 버림을 의미하는지, 반올림을 의미하는지, 올림을 의미하는지 물어봤는데 반올림을 의미하는 것이라고 답변이 왔습니다.

당시에는 세 점을 잡아 평면을 만들어 아래 위를 나누는 풀이가 아예 틀렸거나, 오차 문제일 것이라고 생각했습니다. 그래서 랜덤 데이터를 만들어 O(2^n)풀이와 정답이 일치하는지 확인하고, 식을 잘 정리해 오차가 발생할 수 있는 나눗셈 연산을 가장 마지막에 하게끔 코드를 고쳤습니다. 그런데 랜덤 데이터에서 반례는 전혀 잡히지 않았고, 오차를 줄이기 위해 식을 정리하고 제출해도 여전히 WA였습니다. 이후 double을 전부 long double로 고치고 냈는데도 또 WA가 나왔고 그대로 장렬하게 전사했습니다...

G는 틈틈히 다른 팀원이 열심히 풀고 있었고, K를 제가 포기한 이후에는 어떻게든 G라도 맞자고 하며 다같이 달라붙었는데, G도 계속 맞왜틀이었습니다. 그렇게 절망하며 대략 3시간 동안 한 문제도 추가로 해결하지 못하고 대회가 종료되었습니다.

월드파이널 진출을 노리고 열심히 하긴 했지만 "우리가 이만큼 노력했으니 월드파이널에 꼭 나가야만 해!"와 같은 마인드는 아니었습니다. 다른 팀들도 정말 열심히 했을거고, 저희 실력이 살짝의 운이 있어야 월드파이널에 나갈 수 있을 정도였기 때문입니다.

그래도 올해가 마지막 ICPC인데 월드파이널에 나가지 못하더라도 최소 "졌지만 잘 싸웠다" 정도는 되어야 기분 좋게 끝낼 수 있을텐데 작년 대학 기준 6등, 팀 등수 10등에서 올해 대학 기준 12등, 팀 등수 20등으로 미끌어진건 너무 충격이었습니다. 지금 보니 대학 기준 등수도, 팀 등수도 정확히 2배가 됐네요,,,,

그 와중에 Cafe Mountatin 팀은 올솔브를 하셨고 inseop is Korea top 팀도 넘사의 퍼포먼스를 보여주셨습니다 팬이에여,, 고대에서 저희와 같이 경쟁하며 여름을 불태웠던 지구이팀은 8솔에 성공했습니다. 특히 같은 대학의 팀이면 월드 파이널에 무조건 한 팀 밖에 못 나가니 어떻게 보면 참 애매한 사이지만 그래도 서로에게 긍정적인 영향을 주는 좋은 관계였다고 생각합니다. 같이 베트남 리저널 가서 잘해보자ㅠ

아 그리고 올해도 작년과 같이 먼저 시상을 한 후 스코어보드를 공개했습니다. 이건 진짜 너무 아닌 것 같은데 안바뀌나요..??

원래 기분이 우울할 땐 고기니 안암으로 돌아와 Alkor 동아리 동기들과 고기를 조졌습니다. 안암에 고품콩이라는 곳인데 조금 비싸지만 ㄹㅇ 맛있습니다. 다음에 안암올 일 있으면 드세요ㅎㅅㅎ

정말 다행히도 학교에서 베트남 리저널 경비를 지원해줘서 마지막 기회가 남아있습니다. 현재는 팀원들 모두 번아웃 상태여서 미리 논의한대로 잠시 ps에서 멀어져 롤도 하고 사람도 만나고 그러면서 쉬고 있습니다. 원래 알고리즘 강의를 완강내고 Django로 육목AI랑 육목을 할 수 있는 웹사이트를 만드는게 목표였는데 그건 귀찮아서 다음에 할게여,,,, 베트남 리저널에서 유종의 미를 거두고 알고리즘을 익절할 수 있으면 좋겠습니다.

스코어보드 : http://icpckorea.org/2019/regional/scoreboard/

-----------------------

리저널 테스트 데이터가 공개되어 확인을 해보니, K번 문제에서 답이 0일 때 "0.000000"을 출력해야 하는데 "0"을 출력해서 틀린 것으로 보입니다. 그럴거면 소숫점 아래 6자리까지 무조건 출력을 해야한다고 명시를 해놓던가 "Print exactly one line containing the minimum total color transfer, rounded to the sixth decimal point." 이라는 문장을 보고 "0.000000"대신 "0"을 출력해서 틀렸다는 것을 어떻게 알아차리라는건지, 애초에 실수형 문제인데 절대 오차/상대 오차로 해두지 않고 왜 저런 식으로 출력형식을 만들어놓았는지 정말 이해가 가지 않고 또 대회때 고통받은 것을 생각하면 화가 납니다. 정말 짜증나지만 이미 지나간거 징징거려봐야 의미없는 일이고 베트남 리저널에서는 잘 할 수 있도록 해야겠습니다.

https://www.acmicpc.net/problem/15293

NEERC 2017 기출인데 솔직히 만약 대회 중이었다면 이 문제는 무조건 버렸어야 한다고 생각합니다. 물론 로씨아 형님들은 강해서 무려 3팀이나 이걸 풀었지만..

1도 감이 안와 홈페이지에서 풀이를 찾아봤습니다. $N$이 42정도면 그냥 MITM으로 해결하고, $N$이 42보다 크면 $a[0]$이 $2^{64-N}$보다 작아야한다는 점을 이용해 $r$의 후보들을 구하고 해당 $r$에서 super increasing sequence가 되는지 체크하면 됩니다. inverse를 구할 때 __int128을 쓰면 시간초과가 발생하고 오일러 파이를 이용해야 합니다.

나름 암호학 전공하겠다는 사람인데 안풀고가긴 섭섭해서 풀고 가지만 정말 쉽지 않은 문제였습니다. 참고로 같은 대회에 RSA 부채널 공격도 나왔습니다. 정말 미친 것 같습니다. 참고로 $q = 2^{64}$로 제한되지 않은 Knapsack Cryptosystem도 P algorithm이 있다고 하네요.

https://github.com/blisstoner/BOJ/blob/master/15293.cpp

동아리 강의용으로 만든 자료입니다. 좀 열심히 만듬 ㅇㅈ? ㅇㅇㅈ