일단 나는 모든 문제를 풀었고 검수했음

당연히 5시간안에 나혼자 저 문제 다푼건 아니고 몇주에 걸쳐 하나씩 풀어갔음

검토 및 출제하면서 대충 느낀것들 끄적여봄


A. 니은숲 예술가

원 출제자분께서 G1 난이도를 예상하고 냈다는 소리를 들었는데 문제를 보고나서 WTF소리가 나왔음

나를 비롯한 몇몇 검수진이 이거 다이아라고 강력히 주장했고 실제로 다이아찍힘


B. NPU 최적화

내가 제일 마지막으로 푼 문제이자 대회날 당일에 풀고 검토한 문제

너무 끔찍한 문제라 검토하기싫어서 미루다(굳이 한명이 모든 문제를 검토할 필요는 없으니) 이왕 전부 검토해보자 생각해서 마지막날 검토를 잡음

대회당일 자정부터 음 새벽까지 하면 풀수 있겠지 ㅎ 라고 생각했다가 수없는 맞왜틀끝에 새벽은 밝아오고

자료를 호스트에 있는걸 메모리로 넘기고 호스트로 넘기고 데이터빙글빙글돌리고 내 머리도 빙글빙글돌고

아무튼 6시간정도 걸려서 풀고 검토를 끝낸건 좋았는데 문제는 다 푼 시점이 대회 당일 아침 6시였고 1시간 쪽잠자고 바로 지하철타고 대회준비하러감 ㅠ

그래서 오늘 밤새서 상태가 내내 메롱해서 실수도 많았고 조금 그랬음


다시 문제로 돌아오면 이런거 풀지 마세요


C. 라즈베리 파이

아마 이 문제 검토한 검수진이 내가 처음이었을텐데 무언가 정해가 이상?한것 같아서 반례데이터 쭈욱 넣어보다가 정해가 틀리단걸 발견함

그 즉시 다른 검수진들 불러서 이 문제 어떻게 할지 논의했음

나 포함 3명이서 굉장히 진지하게 머리를 맞대고 생각한 끝에 풀이를 생각해내긴 했는데, 그 난이도가 최소 난이도가 D3인 끔찍한 케이스 워크 문제가 되었었음

그때 예상 다이아 난이도 문제들이 굉장히 많은 상태였는데 갑자기 플레예상이었던 문제가 다이아로 바뀌니 중간난이도가 멸망해서 검수진 전부 멘탈이 나가고(...)

그냥 13다이아 시원하게 내고 그랜절 박자는 농담도 했었음


문제로 돌아오면 진짜 정해를 발견한 뒤, 의외로 정해를 구하는 몇가지 방법이 더 있다는걸 발견했고 나름대로 구현을 해보니(300줄ㅎ)

굉장히 고약한 케이스워크 문제가 A_i==A_j 혹은 B_i==B_j일때 발생한다는걸 찾았고 A와 B사이의 중복을 전부 제거하자는 의견을 냈음

바로 채택됐고 채택된 상태로 문제를 푸니 꽤 깔끔했음(그러니 여러분들이 이번 대회에서 C풀며 이 문제 더럽다고 생각했겠지만 사실은 굉장히 깔끔한 버전이었단겁니다)

그상태로 문제에 이야기를 덧붙혀 만들어진게 이 문제. 이 문제에는 수많은 출제진의 피땀눈물이 섞여있답니다


혹시 이 문제의 원래 난이도를 맛보고 싶다면 라즈베리 파이 문제에 "한 유저가 정확히 1개의 라즈베리를 요구"하는게 아닌 "한 유저가 여러개의 라즈베리를 요구"하는 문제 버전으로 바꿔서 풀어보세요. 저는...그걸 풀었어요....


D. 수열과 쿼리의 부분합의 합

내가 출제한 문제. 내가 쿼리를 좋아하고 수학을 좋아하고 섞은 문제 생각하다보니 어떻게 나왔음

의외로 이 문제를 두고 검수진끼리 논쟁이 굉장히 치열했는데, UCPC는 추가시간을 안주다보니

C++에서 돌린 O(QsqrtN) 알고리즘의 시간 < Python에서 돌린 O(QlogN) 알고리즘의 시간이 되서 C++의 오답을 컷하면 Python의 정답도 컷되는 상황이 되버림

나중에 검수진이 피똥싸며 최적화해서 결국 통과되는 알고리즘을 짜긴 했는데, 실제 대회에서 참가자들이 이런걸 짜는건 매우 힘들고

나는 아무튼 파이썬 통과된걸 봤는데 파이썬 왜 더 배려해야함? 시간 칼같이 때림 ㅅㄱ 이라고 말했고

다른 파이썬 사용자 검수진은 파이썬유저도 사람이야 사람!을 외치며 굳이 루트막지말고 통과시켜주고 파이썬도 통과시켜달라 의견을 냄

정말 팽팽하게 의견싸움하다 갑자기 제3의 검수진이 "이거 O(QsqrtQ) C++풀이가 정해보다 빠른데요?"를 시전

갑자기 뜬금없는 풀이의 등장에 논쟁하던 나와 다른 검수진은 어이가 털렸고 나는 그냥 루트 통과시켜주고 파이썬도 통과시켜주기로 합의함(...)

N,Q 30만에 시간 4초가 그 흔적. 원래는 N,Q 50만에 시간 3초였음


E. 반도체 제작

값이 실수가 된다고? LP꼴이 나오네? 그럼 뭐다? 99.99999999999999% LP-dual이다 라고 문제 보자마자 떠올렸고 실제로 LP-dual이었음

그런데 LP-dual 바로 알아채고 행렬을 싱글벙글뒤집으니까 끔찍한 일이 벌어졌는데........

이거 LP-dual이란걸 알아도 식정리가 진짜 미친듯이 끔찍했음. 진짜 뻥안치고 4시간동안 식정리만 했고 답은 의외로 깔끔한 형태가 되었지만(flow with demands)

식정리 난이도가 너무 끔찍해서 내 마음속에서 보스문제 땅땅땅 판결내렸음

여담으로 구사과도 이 문제 식정리에 1~2시간 썼다고 하니 정말 끔찍한 문제가 아닐 수 없음.


F. 대충 카드로 몬스터 잡는 게임

원래는 Monotone Queue Technique이 정해였다고 하고, 그래서 난이도가 D3으로 예상되었었음

그런데 내가 푸니까 그런거 안쓰고 lazy segtree로 그냥 풀리는것 같았고, 바로 출제자와 풀이 의논했음

그래서 정해는 Monotone Queue Technique에서 DP를 lazy segtree를 이용한 최적화 문제로 바뀌었고, 이 문제 예상 난이도는 플레로 바뀌었음

그러니까 오늘 여러분들이 들은 이 문제 해설 사실 그거 내 풀이임 ㅎ


G. Traveling Junkman Problem

Fast Zeta Transformation인거는 눈치챘지만 그거를 쓰기 전에 해야하는 사전 작업(어떤 bit에 어떤 값을 줄것인가?)을 하는게 굉장히 까다로웠음

D4정도 난이도가 될것이라 생각했고, 실제로 D4임


H. 특별상

난 의외로 이 문제 푸는데 1시간이나 걸림. 문제를 잘못 읽었기 때문에(...)


I. 사건의 지평선

그 세그먼트트리로 간선 개수 줄이는 테크닉? 나 그런거 모름 그런데 그냥 바로 그거 생각해내고 풀었음

왜냐하면 앳코더에 비슷한 류의 테크닉이 나온적이 있는데, n-SAT(?) 간선 줄이기 테크닉임

x_1 ~ x_n이 있고 이중 1개를 고르면 나머지를 전부 선택할 수 없는 그런 조건이 들어올때, x_i -> x_j for all j로 모든 간선 만들고 SCC 생각하면 되는데

문제는 이 방법이 간선이 N^2개가 나옴. 이 간선을 6N개정도의 간선으로 줄이는 테크닉이 있고 그걸 그대로 썼음

이 방법을 응용하면 굳이 간선 줄이기 위한 방법으로 세그먼트 트리를 쓸 필요가 없음. 그래서 나는 이 방법에다 버킷을 응용해서

간선 개수 총 O(NsqrtN)개인 그래프를 만들어서 O(NsqrtN) 알고리즘을 짜서 이 문제를 핵했고, 출제자는 이 풀이를 굳이 막지는 않았음

(그러니까 이 문제는 O(NsqrtN)으로도 풀린다는거임. 도전 ㄱㄱ)


J. 교집합 만들기

내가 본선에서 제일 좋아하는 문제. 쉽지만 아이디어가 굉장히 참신하고 모두가 재밌게 풀 수 있는 문제라 생각함.

여담으로 본선 13다이아 시원하게 내고 그랜절 하자는 농담 할때 출제자가 이 문제 교집합만들기가 아니고 합집합만들기로 바꾸고 다이아 가자는 자학을 했는데(...)

나 합집합 만들기 어떻게 풀지 모르겠음............ 만약 이 문제 풀이 있다면 진짜 다이아 이상일듯


K. 전국 어쩌구 토너먼트

패자를 구하는건 쉬웠지만 승자를 구하는게 어려워서 꽤 귀찮은 케이스워크를 했던 기억이 있음. 그래도 문제 참신해서 난 좋게 평가함

케이스워크 문제도 하나는 있어야지


L. 커넥티드 카 실험

출제&검수진들이 전부 고이고 고일대로 썩은물이라 그런지 검수진이 보고 처음으로 답한 풀이는 여러분들이 아는 그 쉬운 풀이가 아니고

사건의 지평선에서 썼던 그 구간 줄이는 테크닉이었음(...)

아니 망자쉑들 뉴비시선 고려 못하죠? 태클먹고 그 풀이 막기 위해서 이 제한이 다른 문제보다 어마어마하게 큰걸 볼 수 있을거임

아무튼 이것도 재밌었음


M. x+ +x

FFT를 쓰는 문제겠구나 바로 감은 왔는데 식정리가 꽤 힘들었었음

그래도 침착하게 잡고 계산하니 식정리가 꽤 깔끔하게 됬었고 실제로도 꽤 깔끔하게 풀렸었음

다만 문제는 이 문제를 푸는데 앳코더 라이브러리에서 FFT 가져와서 썼다는것. 이 문제가 깔끔하게 풀린다고 해도

실제 대회에서는 참가자가 FFT를 직접 구현해야하기 때문에 최고난이도 문제중 하나로 예상됬었고, 실제로 딱 1팀 풀었음

백준에 이 문제가 올라와있는데, 거기서는 FFT 라이브러리를 가져다 쓸 수 있으니 난이도가 실제 대회에서 느끼는 난이도보다 훨씬 낮게 나올듯


대회 총평을 하자면, 굉장히 만족스러웠음

대회가 좋은 대회인지 판단하는 3가지 기준이 있는데

1. 모든 참가자가 1문제 이상은 풀어야 하고

2. 모든 문제를 푼 참가자가 없어야 하고

3. 모든 문제는 적어도 한 참가자에 의해 풀려야함

이 3개를 만족시키는 대회를 여는건 지이이이이이인짜 힘들고, 그런데 이번 본선이 이 3개를 전부 충족하는 대회가 되서 정말 대만족함

다만 스탭들 공간이 협소했던건 아쉽. 스탭들이 앞에서 알짱거리는건 놀러나온게 아니고 있을곳이 없어서 였습니다(...)

그리고 라즈베리 파이를 운영측에서 준비 못해서 모든 참가자들이 10분만에 올솔하는거 아닌가 매우 겁이났지만 다행히 그런 일은 없었습니다


이제뭐하지