대회 끝난 지 며칠은 지났는데 아직도 끝났다는 게 실감이 안 난다.
체감상 11월 내내 대회 일만 한 것 같다. (기억왜곡일수도잇음)
올해 ALOHA는 봄/가을에 내부 대회를 한 번씩 열었었다. 쌓인 문제 목록 중에서 그래도 좋은 문제들을 HCPC에 내야 하니 선제는 여름방학 중에 단풍컵(가을 내부 대회) 선제하면서 같이 미리 끝내 두고, 11월부터 세팅을 시작했다. 지금 돌이켜보면 출제 일정이 좀 빠듯했는데, 인공지능 중간고사가 11월 4일이었어서 어쩔 수 없었다..
각자 문제 세팅은 11/13일 정도까지 끝냈고, 이때부터 검수를 시작했다. 11월 1일에 BOJ 홍보 게시판 / solved.ac 디스코드에 검수자 모집 글을 올렸었는데, 생각보다 신청해주시는 분이 적어서 작년 검수진께도 DM 싹 보내고 현중이가 히다 데려오고 하면서 겨우 모으기도 했다. 이 시점에서 세팅이 완벽히 되어 있었으면 그래도 검수 일정이 괜찮았을 것 같은데, 세터는 세팅이 끝났다고 생각했지만 지문이나 데이터나 여러 면에서 퀄리티가 충분하지 않은 문제가 몇 개 있어서 좀 많이 꼬인 것 같다.
개인적인 이유로 어떤 출제자가 낸 문제를 전부 내가 맡게 되었고, 그중 한 문제를 제외하고 지문을 전부 새로 갈아엎었다. 그러다 보니 16문제 중 혼자 8문제를 관리하게 돼서 좀 벅찼고, 세팅 마무리도 너무 늦어졌다. 모든 문제 지문 상태가 봐줄 만 해지고 검수 가능해진 시점은 11/20일 정도였고, 12/1 대회인데 그 전 주에 리저널도 있는 상황이다 보니 일정이 촉박했다. 다행히 마지막으로 지문 엎은 문제가 쉬운 문제라 검수는 별 탈 없이 마무리됐다. 미리 세팅되어 있던 어려운 문제를 빨리빨리 검수해주신 덕분이다. 정말 다행이라고 생각하고, 부지런히 일해주신 검수진 분들께 감사드린다. 다들 열심히 세팅하고 꼼꼼히 검수해주신 덕분에 본 대회는 문제 이슈나 질문도 거의 없이 평화롭게 마무리되었다.
선제 과정에서 난이도 분포에 가장 신경을 많이 썼다. 작년 Beginner Division에서 1등부터 6등까지 솔브 수가 똑같았던 참사가 생겼기 때문에.. 올해는 난이도 분포가 연속적이도록 문제를 고르려 노력했다. Beginner Division에는 특별한 알고리즘을 쓰는 문제를 내지 않아서 애드혹그리디파티가 되었는데, 개인적으로는 좋은 방향이라고 생각한다.
Beginner Division에는 작년보다 난이도를 대폭 낮춰 BBBSSSGGGP 정도로 출제하려 했고, Advanced Division도 작년 스코어보드에서 솔브 수가 뚝뚝 떨어지는 감이 있어 조금 낮춰 BSSGGGPPPP 정도를 예상하고 출제했다. 스코어보드도 작년보다 훨씬 이쁘게 나왔고, 매겨진 난이도를 보면 적당히 잘 낸 것 같아서 만족스럽다. 대회 시작하고 advanced에서 푸는 속도가 너무 빨라서 올솔 금방 나올까봐 잠깐 걱정했는데, 다행히 올솔하고 손빨고있는 일은 없었다.
생각나는 대로 쓴 문제별 비하인드(너무 길어져서 접음)
- 그런사람은없었습니다
열심히 구현하면 $O(N)$에도 될 텐데, 쉬운 구현 문제를 의도하고 $O(N^2)$에도 풀리도록 출제했다. 검수 과정에서 지문 관련하여 가장 말이 많았던 문제였는데.. 애초에 문제 상황 자체가 작위적이라 직관적으로 지문 쓰기 힘들었다. - 수수수수퍼노바
가장 쉬운 공통 문제를 의도했다. Beginner Division에서는 코인의 신 건모 문제가 더 쉬운 것 같긴 하다. 사실 선제할 때는 뻔한 양산형 문제라고 생각했는데, 지금 보니 적당히 잘 만들어진 쉬운 문제 같다. 데이터가 랜덤만 들어가 있었는데, 검수진 의견으로 z로 끝나는 / a로 끝나는 등 끝 부분을 집요하게 보는 데이터를 추가했다.
원래 노트 탭에도 노래 가사가 있었는데, Latex으로 옮기고 보니 가사가 혼자 한 페이지를 먹어서 그냥 지웠다. 지문 앞 부분에는 초신성과 관련된 TMI가 한 문단을 먹고 있었는데, 이것도 문제 넘겨받고 한 문단을 통으로 지웠다. 처음부터 내가 출제한 문제였으면 노래 가사도 한 줄만 남기고 다 지웠을 것 같긴 하다. 문제 풀이랑 관련없는 내용이 분량을 차지하는 걸 개인적으로 별로 안 좋아하는데, 참가자 입장에서 어떨지는 잘 모르겠다. - 순열 복원
이 문제도 두 Division에 모두 출제됐다. 처음에는 Beginner에 $O(N^3)$도 통과하는 Easy 버전, Advanced에 $O(N^2)$를 강제하는 Hard 버전을 출제하기로 정했었는데 출제자가 세제곱 풀이를 이해 못 하고, 제곱 풀이가 유의미하게 어려운 것 같진 않아서 똑같이 내기로 결정했다. 지금 생각해보면 세제곱 풀이가 안 떠오르긴 한다.
대회 끝나고 주어지는 행렬을 std::sort의 비교 함수로 넣어서 runtime error 발생 여부로 가능 / 불가능을 따진다는 충격적인 발상을 들었는데.. 막상 짜 보니 잘 되진 않는 것 같다. - 아무나 풀어주세요
[N][9][9][9] DP 짜야 하는 문제를 내는 게 맞냐? 로 많은 토론을 했었던 문제다. 난이도 커브상 Beginner에 낼 어려운 문제가 하나 필요했고, 다른 골/플 문제에 비해 사전 지식이 필요없는 문제라 선정했던 것 같다. 나는 무지성 상태늘리기 문제라고 생각하고 회의에서 반대했었는데, 막상 짜 보니 사고나 dp 전이 과정에서 생각할 부분이 많았다. 좋은 DP 문제라고 생각한다.
Advanced Division 문제 중 몇 안 되는 구현 빡센 문제였고, 맡은 역할을 충실히 수행했다. 시간 제한이 좀 빡빡했던 것 같긴 하다. - 점과 원
Beginner 문제 중 유일하게 안 짜본 문제다. 외심 구하는 식 정리를 어케어케 하다 포기했던 기억이 있다. 다행히 다른 멋진 검수진분들이 열심히 검수해주셨다. 지금 난이도는 G4로 매겨져 있는데, 이것보단 높아야 하지 않나 싶긴 하다.
이 문제의 출제 의도는 알고리즘 문제 풀이에 익숙하지 않아도 시간을 열심히 박아서 풀 수 있는 문제를 만들어주는 것이었다. 검수진분들이 대회에 내기 부적절하다고 혼내실까봐 좀 무서웠는데, 괜찮은 문제였던 것 같다. 본 대회에서 다른 문제 안 풀고 이 문제 푸는 조커 팀은 아쉽게 없었고, Beginner 1등 팀이 풀어주길래 대단하다고 생각했다.. - 지나칠 수 없는 지하철 게임
출제자가 지하철이라는 키워드로 이런저런 출제 시도를 하다 만들어낸 문제다. 적당히 쉽고 적당히 사고해야 하는 Beginner에 내기 딱 좋은 문제라고 생각한다.
지문 재작성이 가장 늦게 끝난 문제이다. 처음 버전에는 출발역 / 도착역 모두 환승역일 수 있었는데, 이러면 상황이 어색해지는 것 같아 문제 넘겨받고 이런 경우를 삭제했다. 넘겨받고 문제 재검토하면서 기존 MCS를 대충 봤었는데, 알고 보니 틀린 풀이였어서 식겁하기도 했다. - 컴소인의 크리스마스
컨셉 자체는 출제자가 꽤 오래 전에 가져왔는데, 문제가 정확히 확정된 건 선제 마무리하는 시점인 11월 초였다. 이 이후에도 문제 명세 관련해서 이슈가 있기도 했다. 이 문제도 지문 쓰기 어려웠던 기억이 있고, 관련 검수진 피드백도 많았다.
척 보면 그리디하게 정렬 / PQ 등을 써서 풀고 싶고, 대부분 그렇게 풀어 주셨지만 사실 정렬도 PQ도 필요 없는 문제이다. 이 사실을 에디토리얼 쓰면서 깨달았다. 단순 그리디처럼 생각해서 풀어도 괜찮고, 정렬 없이도 이쁘게 풀리는 괜찮은 애드혹 문제라고 생각한다.
지문에 빨강 녹색이 여기저기 있어서 크리스마스 분위기가 난다. 아님말구 - 코인의 신 건모
잘 뽑힌 쉬운 문제라고 생각한다. 정수 연산만 써서 풀 수도 있지만, 실수 쓰는 웬만한 풀이는 다 통과되도록 세팅되었다. - 피아노
비학술부 운영진이 피아노? 라는 키워드를 던져 줘서 열심히 생각해 보다 만든 문제이다. 구간 쿼리를 주면 플레 상위 정도의 자구 문제가 되는데, 난이도 분포 문제 때문에 일반 버전으로 출제했다. Beginner 기준으로도 어렵지 않은 그리디라고 생각했고, 실제 대회에서도 많이 풀어 주셨다. 검수 과정에서 거의 비슷한 G4 문제를 찾아 주셨는데, 다시 생각해도 골드는 아닌 것 같다. - HCPC 팀 짜기
올해 초에 학술부 아닌 다른 선배가 문제 아이디어 생각났다고 말해준 문제인데, 마음에 들어서 간직하고 있다가 이번에 출제했다. 적당히 어려우면서 어떤 사전 지식도 필요없고, functional graph와 관련되어 교육적이기도 하고,, 여러모로 괜찮았다. 다만 순수 케이스워크 문제다 보니 대회에서 많은 팀들이 말리긴 했다.. 무려 17번 시도해 맞춘 팀도 있었고, 한 번에 맞춘 팀은 한 팀도 없었다.
출제자 선배가 군복무중이라 다른 학술부원이 대신 세팅했다. 정확히 풀기 위해서는 7가지 케이스를 모두 고려해야 하는데, 대충 짜고 푼 팀이 하나도 없는 걸 보면 데이터를 강하게 잘 만든 것 같다. 나도 몇 번 틀리고 겨우 맞았고, 원 출제자도 한 번에 못 맞추기도 했다.
원래 Beginner에만 출제될 예정이었는데, Advanced에 출제하기로 했던 문제가 알고 보니 작년 내전 call for task에 제출되었던 문제라서.. 난이도 비슷하고 괜찮은 이 문제로 땜빵했다. 출제 과정에서 3인 팀이 아니라 K인 팀을 만드는 문제로 확장하면 풀 수 있는지에 대한 긴 토론을 했는데, FFT를 써야 한다는 결론이 나와서 원래 버전으로 내기로 했다. - 흑백조경사
초기 버전에는 ALOHA 회장 선거라는 컨셉의 스토리가 있었는데, 지문을 쓰다 보니 상황이 너무 작위적이라 갈아엎었다. 많은 고민 끝에 지금 버전의 스토리를 생각했는데, 지문이 나름 잘 뽑혔다고 생각한다. 아님말구
나는 리루팅 DP 할 줄 몰라서 에디토리얼에 적힌 정해를 생각하고 세팅했는데, 리루팅에 익숙하면 뻔해지는 것 같아서 아쉬웠다. 대부분 리루팅으로 푸신 것 같다.
히다랑 준서형이 이런저런 틀린 풀이를 많이 만들어 줬다. 부등호 실수 조금 해도 잘 뚫리더라.. 틀린 풀이 만들기의 중요성을 실감했다. - 수열과 쿼리 HY
1학기 때 루트질 강의 준비하면서 홍준이는 문자열을 좋아해 같은 쿼리 캐싱 문제에 큰 감명을 받았고, 샤워하면서 이런저런 생각 해보다 떠올랐던 것 같다. harmonic lemma를 연습하기 좋은 교육적인 문제라고 생각한다. 내가 이번 HCPC에 출제한 문제 중 가장 마음에 든다.
세팅이 어려울 것 같다는 생각은 했고, 실제로 무지성 루트질이랑 이상한 나이브 커팅을 신경써서 막아야 했었다. 원래는 제한이 10만이었는데, 히다가 들고 온 루트질 코드에 속수무책으로 뚫려서 30만으로 올렸다. 그럼에도 본 대회에서 커팅을 가미한 루트로그 풀이에 뚫려버리고 말았다.. 뚫은 참가자의 후기를 보니 잘 풀었다고 생각하는 것 같아서 대회 끝나고 저격 데이터를 추가했다.
로그제곱 풀이만 생각하고 있었는데, 본 대회 2등 팀은 30만 로그제곱 짜기 무서워서 그냥 로그로 풀었다고 한다. 왤케 잘함? - 돌 게임 nm
쉬우면서 적당히 머리 써야 하는 괜찮은 문제이다. advanced에서는 수퍼노바 급으로 많이 풀렸다. - 덧셈 팰린드롬 수열과 쿼리
처음 버전은 수열 하나가 덧셈 팰린드롬인지 푸는 문제였는데, 너무 쉬운 것 같아 하루 종일 업그레이드를 시도했었다. 구간 쿼리 버전은 그냥 못 풀었고, 일반 트리에서 센트로이드 분할 하는 풀이도 생각해 봤는데 안 되는 것 같았다. 가장 오래 고민했던 버전은 정점이 10만 개 정도인 포화 이진 트리에서 문제를 푸는 버전이었고, 분할 정복을 하면서 $O(N\log^4 N)$ 같은 풀이가 될 것 같아서 한참 생각했는데 결국 실패했다.. 결국 그냥 나이브하게 풀어도 되도록 작은 포화이진트리에서 푸는 문제로 확정했다.
수열 하나 판별은 그다지 어렵지 않고, 하나 판별할 수 있으면 쉽게 풀 수 있으니 많이 풀릴 줄 알았는데 본 대회에서 한 팀만 풀었다. 문제 특성상 지문이 길고, 깔끔하게 생긴 다른 문제가 많아서 상대적으로 미루고 싶어했던 것 같다. - 나연 정렬
예전에 냈던 자료구조는 정말 최고야 문제에 대해 더 생각해보다 올해 초에 나온 문제이다. 애초에 처음 사고가 고정된 상태에서 떠올리다 보니 그리디 풀이만 생각하고 있었는데, 대부분 검수진들이 LIS와 동치임을 관찰하고 풀어서 신기했다. 본 대회에서도 어디서 본 문제라면서 10분만에 LIS 짜고 풀어버린 팀이 있다.. 뭔지는 모르지만 이름이 익숙한 Dirworth Theorem이랑도 관련이 있는 것 같다. 나름 좋은 문제라고 생각하고 있었는데 알고보니 웰노운인 느낌이라 아쉬웠다.
모든 ALOHA 운영진들에게 이름 들어간 백준 문제 하나씩은 만들어주고 싶어서 아직 이름 쓴 적 없는 나연이 이름을 지문에 적었다. - 간선을 하나 그어서 루트까지 거리의 합을 최소로 만들기로 했습니다
개어려운문제.. 대회 시점에 정확한 풀이를 모르는 유일한 문제였다. 지금은 대충 알긴 하는데 짜긴 귀찮다
그냥 김현중은 신인듯
대회 준비하면서 많이 고생하고 싸우기도 하고, 공개적으로 적기 어려운 일들도 많이 있었는데 결국 대회는 무사히 잘 끝나서 다행이라고 생각한다. 고생한 만큼 문제 많이 풀어주시면 좋겠다.
혹시 내년 HCPC 출제진이 이 글을 본다면.. 화이팅입니다.
문제는 미리미리 세팅해두시는게 좋을 것 같고, 끝까지 화목하게 대회 잘 여시길 바랍니다.
'기타' 카테고리의 다른 글
| 제 4회 천하제일 코딩대회 본선 후기 (0) | 2020.12.23 |
|---|
