Day 305. SUAPC 2023 Summer 출제 후기

SUAPC 2023 Winter 참가 후기에서 남긴 여담이 이렇게 빠르게 실현될 줄 몰랐다.

자기실현젹 예언?

Call for Task에다 골드 한 문제, 다이아로 예상되는 한 문제를 들고 있다고 신청을 했는데, 결과적으로 가지고 간 문제가 전부 무탈하게 출제되어서 기쁘기 한량없다. 실력이 부족한 초보 코더를 넣어 줘서 너무 감사하고...

그리고 본인의 실력이 부족한 탓에 상호 검수 과정에서 빡센 문제를 거의 손도 못 대어서 다른 출제진 및 검수진에게 약간 죄송한 마음이 있다. 내가 한 검수라 해 봤자 그리 대단한 것도 못 되어서...

동일한 날에 브실컵까지 열려서릴 뻔 해서 두 대회를 오고 가느라 정신없이 바빴다. 막바지까지 일이 끊어지 않아서 더욱이.

포스터. 이번에도 간지난다.

지난번 SUAPC와 UCPC를 나갔던 :blobsad: 팀은 내가 출제진으로 나서면서 자연스럽게 와해되고 말았다. 톡방에는 개인사정으로 출전 불가라고 뻥을 쳐 놨던 탓에 지금 후기 쓰는 동안에는 팀을 이뤘는지. 참가하기는 했는지 알아보기도 무엇하고... 알아서 잘 했기를 바랄 수밖에 없다. ㅋㅋ.

+) blobdead(ez_code)는 가오당 팀으로 가서 4등 상을 받았다. blobglitch(piico)는 어느 팀을 갔지? 뉴비팀이었나? 분명히 들었는데 벌써 까먹었다. 이 놈의 기억력... 그와 별개로 출제진 갔다고 연막 친 게 전혀 쓸모가 없었다. ez_code는 B번 문제를 보자마자 내가 냈다는 걸 눈치챘다고 한다. 지문인가 보다.

 

소감

이렇게 기업에서 후원하고 상금 규모까지 큰 대회에 참여하게 될 줄은 몰랐다. 큰 대회 운영에 참여하면 배울 점이 많다는 후기를 얼마 전에 보았는데 역시 그러하다. 검수가 어떻게 이루어지는지, 상호 검수는 어떻게 하는지 등등을 이번에 제대로 배웠다. 이번 대회에서 배운 것들을 발판삼아 추후 출제 혹은 검수 경력이 쌓이게 되면 십분 활용할 수 있지 않을까.

내가 낸 문제에 대해서는 꼴에 할 이야기가 많지만 그건 조금 아래에 있는 문제별 후기에서 다루기로 하고. 본 대회 막바지까지 검수하느라 생활 패턴이 뒤집어졌지만 검수한다는 과정이 매우 즐거웠으니 그것으로 되었다. 본래 즐거움은 피로를 잊게 해 주니.

 

문제별 후기

스포일러가 있으므로, 업솔빙을 하려는 사람은 이 뒤를 읽지 않는 것을 권한다.

 

A. A→B (dhlee1031)

　애드혹 구성적인 문제인데, 이건 한 번 말리면 진짜 끝까지 말린다는 소리와 동치인 것 같다. 페그 게임과 비슷한 풀이 방식으로 풀린다는 정보가 바탕이 되고서야 적절한 해를 구성할 수 있었다. 머릿속으로만.

　본대회와 오픈 콘테스트에서 정말 수많은 사람들이 수많은 방법으로 말렸다. 페그 게임으로의 치환이 굉장히 익숙치 않은 문제라 삽질을 조금 했던 사람들 눈에는 굉장히 고난이도 문제로 보였을 것이고 그게 전혀 이상한 일은 아니라고 생각한다. 본격 푸는 것보다 SPJ 다는 게 더 어려운 문제.

B. 기초적인 문제 (nflight11)

　내가 낸 문제다. 제목에 낚여서 들어갔다가 피를 봤다면 미리 심심한 사과의 말씀을 전한다. 매우 어려운 난이도의 문제 제목에다가 쉬운 문제라고 붙이는 선례가 있어서 괜찮으리라 판단했다. 그래도 초안인 '간단한 문제'보다는 나으니 그것으로 충분하지 싶다. 아니라고? 죄송하다. 돌을 던져라.

　이 문제는 애초 \(\left(\binom{a_i}{b_j}\right)\)의 행렬식을 구하는 조금 더 레벨이 높은 문제로 구성할 예정이었으나, closed form이 이쁘게 나올 것 같지 않다는 생각을 했고 Lindstrom-Gessel-Viennot Lemma를 이용하는 문제는 바로 전 대회 L번(의 별해)에도 있었으니 Call for task에 내기 전에 마음속으로 너프를 시켰다. 그래서 나온 게 이 문제인데, 그럼에도 불구하고 매우 어려운 플래티넘에서 다이아 경계선을 넘나드는 정도 될 것 같다는 생각을 했다.

　검수를 맡아주신 (god-)kipa00님이 다이아 상위, (god-)lky7674님은 높아봐야 플래티넘 선에서 정리될 것 같다는 말을 하셨고, 딱 예상한 만큼 난이도가 나와서 다행이.

　여담으로 이거 \(\mathcal O(N\log^3 N)\) 풀이가 있단다. Multipoint evaluation과 분할정복에 FFT까지 끼얹는 풀이인데 저걸 쓰기 위해서 \(N\)을 키운다면 진짜 루비 될지도 모른다는 생각이 든다. 이거 하드 버전을 내려면 4000솔을 해야 한단다. 지옥 난이도의 저 알고리즘들을 배우는 게 빠를지 4000솔이 빠를지는 모르겠다.

　First solve는 겨우 82분밖에 지나지 않아 등장하였지만 본 대회에서 푼 팀은 단 세 팀에 불과했다. 이름값을 못 해서 기쁘다. 이걸 Redshift 팀이 끝나기 10분 전에 풀어내어 그 결과로 우승자와 준우승자가 갈렸으니 코딩 진짜 알 수 없다...

C. 2048 (starwh03)

　진짜 내가 아는 요소가 단 하나도 없었다. 커넥션 프로파일 DP에 전처리까지 잘 섞어서 정말 매운 문제가 탄생했다. 이 셋에서 가장 어려울 법한 문제 꼽으라면 이게 꼽히지 않을까.

　전처리 문제가 귀하다는 데에는 아마 이견이 없을 것이다. 특히 한국어로 된 문제에서. 동아리 팀연습에서 각종 리저널들 풀면서도 진짜 가뭄에 콩 하나 나는 정도. 그래서 이 문제, 굉장히 좋다고 생각한다(나는 못 풀지만).

D. 디지털 트윈 (dlguq0107)

　잘못된 그리디로 판단해서 그르치기 딱 좋은 DP문제이다. 28241번이랑 비슷하다고 착각할 수 있을 것 같지만 그것보다 살짝 순한 맛이 아닐까. 그래도 골드 최상위권 문제 혹은 플래티넘까지 밟을 수 있는 문라고 생각한다.

　에디토리얼의 DP 식이 정말, 정말 길고 어렵게 나왔다. 상호 검수 과정에서 아무리 식을 짜도 안 나오길래 에디토리얼을 훔쳐봤는데 DP 식으로만 슬라이드 하나를 먹을 만큼. 플래티넘 색이 보인다...

E. 성게밭 (dlguq0107)

　이분매칭 플로우라는데 어느 쪽도 몰라서 이번 기회에 (개념만) 배웠다. 초급 알고리즘에도 조금 약한데 상급 알고리즘만 마구 배우고 있다. 상호 검수 과정에서 이 문제도 거의 손을 못 댔다.

F. 작곡가 A의 시창 평가 (2093ab)

　게임 이론 문제인데, 나는 게임 이론에 무지막지하게 약하다. 스프라그-그런디 기초적인 것 몇 개 말고는 풀지를 못한다. 그런디 수 구하는 방법도 결코 간단하지가 않아 보여서 플래티넘 상위가 될 것이라고 확신했다.

　난이도와 별개로 태그 조합이 정말 좋다. KMP에 스프라그-그런디는 거의 처음 보는 태그 조합인 것 같다. 매칭시키기 결코 쉽지 않은 것들 가지고 좋은 문제를 만들어 주시니... 이 별개로 상호 검수 과정에서 손을 못 대어서 죄송한 감이 있다. 업솔빙 해야지...

G. 개발자 지망생 구름이의 취업 뽀개기 (2093ab)

　후원 문제. 본디 이것보다 조금 더 난이도가 높은 그리디한 실버가 될 예정이었는데 누가 봐도 브론즈 문제가 필요하다는 이유로 조금 낮아졌다. 개인적으로는 원본도 매우 재밌는 문제여서 조금 아까웠다. 혹시 하드 버전 개인적으로 출제하실 생각 없으신지?

H. 탭 UI (sjhow12)

　적절한 난이도의 prefix sum 구현 문제. 문제 셋의 허리를 담당하는 난이도가 이 셋에서는 많지 않았다. 기꺼이 허리를 맡아줘서 고마운 문제. 상호 검수 절차에서 짜다가 계속 TLE가 났는데, 20만 회 입력을 받는 데서 fastIO를 안 썼기 때문이라는 걸 깨닫기까지 무려 2시간이나 걸렸다. 대회를 나갔으면 내가 패널티를 전부 다 떠맡고 장렬하게 전사했을 것이다.

I. 폭탄 피하기 (maker29)

　상호 검수 과정에서 자력으로 풀어낸 가장 높은 난이도의 문제. 격자상의 경로 문제는 많이 봐서 익숙하고, 포함배제의 원리도 어떻게 적용해야 하는지만 알면 그렇게까지 맵지는 않... 다고 생각한다. 다만 이 둘을 엮으려니 플래티넘이 되었을 뿐.

　비트마스킹을 난 안 쓰고 풀었다. 정확하게는 비트마스킹 구현을 하지 않았다는 게 옳겠다. from itertools import combination 만세. 부분집합을 일일이 구현하기 조금 귀찮았는데, 파이썬에는 이런 훌륭한 도구들이 많아서 좋다. 대신 삐끗하는 순간 시간초과로 직행해야 한다는 위험성을 안게 되지만.

J. 큰 수 만들기 게임 (maker29)

　이 문제의 초안이 정해질 때쯤 굉장히 기시감이 많이 들었다. 분명 이 비슷한 문제를 어디선가 본 것 같은데... 그러다가 설명하신 풀이를 듣고 기시감이 어느 정도 해소되었다. 옛날에 \(\sum a_i\)가 한정된 상태에서 \(\prod a_i\)를 최대화하는 정수 \(a_1,\cdots,a_N\)을 구하는 수학 퍼즐을 푼 적이 있었다. 접근법이 완전히 다르지만 분명 그리디한 점만은 참 많이 닮아 있다.

　이 문제를 상호 검수하면서 나온 코드의 부산물로 문제 하나를 풀었다. 요즘 solved.ac 레이팅이 답보 상태였는데 덕분에 2점이 올랐다. 아마 이 문제는 플래티넘일 테니 이 문제로도 레이팅이 오를 것 같다. 고마워요!

K. 케이크 두 개 (nflight11)

　내가 낸 문제 2. B번과는 다르게 초안 그대로 나오지 않았다. 굉장히 크게 너프된 버전으로 매우 귀여운 그림과 함께 세상에 선보여졌다. 최고의 아티스트에게 박수를!

　나는 이 문제를 기하학 이분탐색 골드로 내려고 했었다. 영감을 받은 문제는 햄 샌드위치 정리라고 불리는 상당히 어려운 문제였다. 원본은 직사각형 하나 볼록다각형 하나였고, 잘만 구성한다면 둘 다 볼록다각형으로 문제를 내는 것도 이론적으로는 가능했다... 만 그렇게 되면 정작 문제를 낸 내가 세팅을 못 하는 불상사가 발생하는 터라.

　그러던 와중에 출제기간 초반, 실버라고 부를 수 있는 문제가 없었기에 하향을 결정했다. 생각해보니 데이터를 만들려면 convex hull 정도는 필요했었고, validator도 convex hull이 들어가야 했다. 문제는 내가 convex hull 배운 지 얼마 안 됐고, 심지어 validator는 (거의 모르는) C++이 강제라... 결론적으로 하향이 옳았다. validator를 못 짜서 다른 분 손을 좀 많이 빌렸다. 커피라도 사야지.

　까메오로 무단 출연시킨 Sinchon ICPC 회장과 Morgorithm 회장에게 미리 감사의 인사를 남다. 참. 실제 출제자들이 만난 장소는 연세대학교 공A527(아늑한 Morgorithm 동아리방)이 아니다.

L. 나의 FIFA 팀 가치는? (maker29)

　무난한 PQ 문제. 여담으로 상호 검수 절차에서 Python3로 시간초과가 난다고 보고를 했었는데 이것도 fastIO를 빼먹어서 난 시간초과였다. 이 놈의 fastIO 빼먹는 버릇은 언제 고칠까. 대회에서 시원하게 말아드셔야 고치려나.

　Parametric search 풀이를 봉쇄하겠다고 대회 직전에 출제자분이 여러 데이터를 넣으셨는데, 그 덕에 본 대회에서 원하지 않던 parametric search 풀이를 쳐낼 수 있었다고 좋아하셨다.

M. 트리와 케이 (starwh03)

　그냥 대놓고 매운 문제. 센트로이드라는 개념을 사용한다고 한다. 트리에서 분할정복이 가능하게끔 만들어 주는 도구인데... 이게 유일하기는 하는가? 들어만 본 개념이라 상호 검수를 전혀 하지 못했다.

　트리와 케이랑 K번 케이크 두 개. 발음의 유사성 때문에 난이도는 하늘과 땅 차이인 내 문제가 자꾸 소환되는 귀여운 해프닝이 있었다.

N. 북극여우는 괄호를 뒤집어 (dlguq0107)

　셋 중 세그트리가 없다고 해서 추가된 문제였는데, 막상 짜고 나니 이것도 세그트리가 아니게 된 비운의 문제. 분명 프리퀄(?) 문제인 북극곰은 괄호를 찢어는 이것보다 1만배쯤 쉬웠던 것 같은데... 정말 자연스럽게 제곱근 분할법과 스플레이 트리 문제가 되어버렸다. 확정 다이아가 아닐까.