10주년 대회 출제 후기

28 Aug 2022

개강 전 마지막 행사..

다음주가 개강? 이건 말도 안된다. 슬슬 종강할 때가 된거 같은데 뭔가 버그가 발생한 듯 ㅇㅇ. 하여튼 어제 있었던 알로하 10주년 기념 대회 출제 후기 쓰러왔음. 이게 알고리즘 놓은 지 꽤 오래된 선배님들도 참여하는 대회라서 난이도 커브 잡기가 너무 어려웠다. 알고리즘을 알아야 풀리는 문제들은 최대한 지양하고, 많이 어려워서도 안되니까 출제가 그리 쉽진 않았음. 또한, 지금 동아리원들 중 잘하는 사람들이 너무 일찍 스코어보드를 얼리는 일이 없도록 해야했기 때문에 그래도 어느정도 난이도는 있어야 했었음. 결과만 보자면, 음.. 적당히 망한(?) 느낌으로 출제가 됐다. 생각보다 난이도를 저평가해서 그런지 알고리즘들을 잘 써야 풀리는 문제는 없었지만, 1시간 30분동안 노솔브가 꽤 있었다. 오프라인 참여해서 풍선 못받으면 좀 슬픈데 ㅠㅠ 미안해요.

문제가 없어요

문제(issue)가 없는 문제(problem)를 출제했다. 그 문제 지문에 적혀있던 내용은 사실을 바탕으로 쓰여졌는데, 사실 우리 대회 11일전에는 문제가 단 하나도 없었다. 그래서 회장님이 ‘문제가 없으면 안돼’ 이러길래 그럼 ‘문제가 있는거네’ 이러면서 말 장난하다가 그걸 그대로 출제를 했다. 단순한 구현 문제고, 지문을 잘 읽으면 한 번에 풀리는 문제다. (지문 읽기 난이도가 젤 어려운듯 ㅋㅋ) 대회 문제 셋에서 가장 쉬운 문제였고, 실제로도 젤 많이 풀렸다. 나름 뿌듯함. 딴 문제들에서 맞왜틀하다가 이 문제 풀어서 1솔권에 들어온 사람들이 꽤 있어서 좋았다.

N명 K분대 남았습니다.

에이펙스 레전드를 하다가 우측상단에 뜨는 인디케이터를 보고 떠올린 문제다. 아마 배틀로얄 중에 몇분대 몇명이 뜨는 게임이면, 음~ 대충 이런 구성으로 팀이 되어있겠네 하는 생각을 해봤을거다. 특히, 에이펙스 레전드에서는 이게 더 중요해서 자연스럽게 생각하다보니 이거 출제해도 괜찮겠네라는 생각이 들어 그대로 출제했다.

원래 처음에는 \(\scriptsize O(NMK)\)가 정해였다. 가만보니, 점화식 계산에 드는 시간을 \(\scriptsize O(NK)\) 또는 \(\scriptsize O(NKlogM)\) 로 줄일 수 있을 것 같았다. 조금 고민을 하다가 안바꿀까? 싶었는데.. 학술부장이 \(\scriptsize O(NMK)\)풀이를 금방 가져오길래 어림없지 ㅋㅋ하고 바로 정해를 \(\scriptsize O(NK)\)로 수정했다. 뭐 그러던 중에 hibye1217님이 dp[i] = 0 (mod M)이면 정해가 틀릴 수 있는 것 때문에 출력 바꾸자고 해서, 원래 불가능한 경우에 -1을 출력하도록 했었는데 그냥 0으로 바꿨다.

나는 DP를 의도하고 출제한 것이긴 했으나, 참여자 중 한 명은 이걸 조합론적 풀이로 풀어서 제출했었다. 중복조합과 조합을 적절히 쓰는 풀이였는데, 아무래도 조합론 문제다 보니까 이게 가능했나보다.

나름 기초적인 DP지만, 그래도 이번 문제 셋에서는 어려운 포지션을 담당했다. 대충 생각한만큼 풀린 것 같고 난이도 포지셔닝이 적절했던 듯.

크게 만들기

갑자기 헉! 하고 떠오른 문제다. 하나 뽑고 나머지 전부 1 감소시키면, 어떻게 뽑아야 뽑은 수의 곱이 최대가 될까? 라는 생각이 그냥 갑자기 떠올랐다. 조금 끄적이다가 왠지 그냥 오름차순으로 곱하면 되는 것 같았는데 난 증명을 못했다. 그래서, 이런 문제 어떠냐고 디코에 올렸는데 hibye1217님이 그냥 바로 뚝딱 하더니 슥하고 삭해서 증명을 가져와줬다. 증명은 조금 배경지식이 없으면 어렵다. 최적의 해를 가정하고 그 순서를 바꿨을 때 바꾼것보다 최적해가 더 커야한다 라는 부등식을 통해 시작한다. 고걸 정리하다 보면, 좀 익숙한 형태가 보이는데 그 부등식을 항상 만족하려면 큰거에 큰걸 곱하면 된다는 사실을 알 수 있다. 정확하게는 재배열 부등식에 의해서 그렇게 되는데, 사실 그 정도의 증명을 대회 시간 내에 하진 않을거라 생각했고 이 문제처럼 직관과 약간의 proof by ac를 통해 해결할 거라 생각했다.

문제에서 시키는것도 그렇고 발상도 약간 codeforce 느낌이라 지문도 그냥 codeforce 감성으로 썼다. 근데, 진짜 어딘가 있을법한 문제이긴 한데 뭐 그냥저냥 무난한 그리디? 수학? 문제였다. 생각보다 proof by ac를 잘 시도안했는지 그냥 바로 보고 넘긴건지는 모르겠지만 예상치보다는 적게 풀린 느낌이다.

그런데 왜 망함?

사실 각자 출제는 잘 했는데 (문제 하나하나 각각 보면 다 괜찮음), 모으고 나서 보니 완전 쉬운 문제.. 흔히 등록 문제라고 하는 문제가 없었다. 제일 쉬운 문제가 내 구현 문제였는데 원랜 그것보다도 더 쉬운게 있어야함. 여튼 그래서 0솔브가 되게 많았다. 상위권을 위한 문제들의 난이도 커브도 살짝 아쉽지만 그래도 이거는 제대로 잡힌 것 같아서 다행이었다. 0솔브가 너무 많았던 점 죄송합니다.. ㅠㅠ