예전부터 가끔 boj에서 문제를 출제하거나, 검수해보고 싶다는 생각을 하곤 했는데, 마침 dlstj0923님이 중앙대학교 NPC에서 문제를 검수해 줄 사람을 모집하셔서, 외부 검수진으로 참여하게 되었습니다. NPC에 출제된 문제는 총 7문제였고, 모든 검수진이 모든 문제를 각각 풀어보고 검수하는 방식으로 진행되었습니다.
A. 이진 딸기
검수진 예상 티어: 브론즈 I
실제 티어: 실버 V
if문이나 나머지 연산을 통해 상수 시간에 N을 1부터 15 사이의 수로 변환한 후, 출력하는 게 출제자 omjin7n님의 의도였는데.. pjh6792님의 제보로 N이 10억 이내 범위였음에도, 1부터 시작해서 숫자를 N번 바꾸는 naive한 풀이가 통과되는 것이 확인되어, 테스트 케이스를 1000개정도까지 늘리셨습니다.
테스트 개수를 추가한 이후에도 커팅을 하면 여전히 선형시간에 뚫을 수 있지 않을까 하여 몇번 제출해 봤지만 TLE를 받는 것을 확인하는 것을 끝으로 검수를 마쳤고, 다행히도 대회때 선형시간 풀이는 나오지 않은 것으로 보입니다.
B. 주간 달력
검수진 예상 티어: 골드 IV
실제 티어: 골드 IV
주력이 1에서 시작하는 경우부터 50000에서 시작하는 경우까지, 모든 경우에 대해서 테이프가 주력의 면적을 얼마나 차지하는지, 그때 테이프를 몇 번 잘라야 하는지 등을 브루트포스로 계산하는 것이 출제자 tngus5851님의 의도 풀이인 문제였습니다.
이 문제의 경우 검수 과정에서 다른 꼼수 풀이가 나온다거나 한 건 없었지만, S와 E의 범위 제한이 10만 이내였는데, 검수 과정에서 범위 제한을 5만으로 줄이는 게 브루트포스가 의도 풀이라는 것을 더 잘 표현할 수 있다는 검수진분들의 의견으로 인해 범위 제한이 5만 이내로 변경되었습니다. 아무래도 1억(100000M)회 연산에 1초 제한이면 시간이 빡빡하다고 생각하는 분들이 계실 수 있을 것이라고 생각해서 이런 판단을 내리신 것으로 보입니다. (실제로는 단순 반복문이라 시간이 생각보다 널널합니다.)
여담으로 이 문제는 브루트포스 이외에도 검수진에 의해 스위핑, 세그먼트 트리 등 다양한 풀이가 나왔습니다.
C. 교수님 계산기가 고장났어요!
검수진 예상 티어: 실버 III
실제 티어: 실버 II
이번 대회문제중 검수가 가장 활발하게 진행되었던 문제였습니다. 초기에는 -10 초과 10 미만의 소수점 8자리 수 2개를 곱하는 문제였고, 출제자 smmaker118님은 해당 숫자를 string으로 받은 뒤, long long으로 변환해서 곱하는 풀이를 의도하셨습니다.
검수진 사이에서 첫 번째로 논의된 부분은 바로 python의 decimal 라이브러리의 존재였습니다. decimal로 곱한 뒤 “{:.%.16f}“.format으로 출력하면 다른 언어에 비해 쉽게 풀린다는 gojib2002님의 제보가 그 시작이었습니다. 반면 저와 smmaker118님은 format을 안 해주면 일부 테스트 케이스에서 scientific notation(1e-16과 같은 식)으로 출력하게 되는데, 이 부분이 소위 ‘맞왜틀(맞았는데 왜 틀렸죠)’을 유발하기 쉽기 때문에 다른 언어에 비해 딱히 쉽지 않다고 주장하여 이 부분에 대한 논의는 무마되었습니다.
두 번째 문제는, 출제자분이 __float128을 사용한 풀이를 저격하는 테스트 케이스를 넣었음에도, __float128를 이용하는 풀이가 AC를 받는다는 gratus907님의 제보로부터 시작되었습니다. pjh6792님과 shieldnet님 등이 python과 c++의 난이도 격차를 줄이기 위해 decimal과 __float128을 둘다 허용하는게 나을 것 같다고 주장했지만, 출제자님은 소수점 자리수를 9자리로 늘려서 __float128을 막는 쪽을 선택하셨습니다. (지금 보니 대회 종료 이후에는 언어 제한으로 python을 막았네요.) 이 과정에서 의도 풀이가 long long이 아닌, unsinged long long을 사용하는 것으로 변경되었습니다.
마지막 문제는 의도 풀이가 unsinged long long을 사용하는 것임에도, 제 long long 풀이가 통과한다는 점이었습니다. 당시 작성된 제 코드는 다음과 같습니다.
1 | |
신기한 건, 24번째 줄에서 실제로 오버플로우가 발생함에도 출력은 제대로 된다는 사실입니다. 테스트 케이스를 추가한다고 해결될 문제는 아닌 것 같아 수 범위를 줄여 long long으로도 통과될 수 있게 하자고 제안했는데, 출제자분이 이 문제를 발견한 게 검수 마감일인지라 지금와서 데이터를 바꾸긴 어렵다고 판단하여, 이대로 검수를 마감하게 되었습니다. 결과적으로 대회중에 long long으로 풀어서 맞은 분은 없는 것으로 보이긴 하지만, 개인적으로 조금 아쉬운 부분이었습니다..
D. 백발백준하는 명사수
검수진 예상 티어: 브론즈 II
실제 티어: 브론즈 III
단순 사칙연산문제입니다. R1, R2 범위 제한상 double, long double 풀이는 막을 수 없어 보였고, float 풀이를 막을 수 있나 테스트해봤더니 뚫려서 테스트 케이스를 추가했습니다. 이 문제를 double도 아니고 float로 풀 사람은 딱히 없을 것 같아서 크게 의미있는 수정은 아니었던 것 같습니다.
E. 쿠키크루
검수진 예상 티어: 실버 I
실제 티어: 골드 V
단순 브루트포스 문제입니다. 검수진분들은 각자의 방식대로 브루트포스를 구현했고, 저는 그 누구보다도 더럽게(..) 풀었습니다. 이 문제는 일부 지문 수정을 제외하면 별다른 이슈는 없었습니다. 다만 4지선다형 문제다 보니 혹시나 대회때 랜덤 풀이가 나올까 싶긴 했는데 다행히도 없었던 것으로 보입니다.
F. 선형 연립 방정식
검수진 예상 티어: 골드 IV
실제 티어: 골드 I
정직하게 가우스 소거법을 쓰는 문제였습니다. 다만 처음 출제됐을 때에는 해가 100 이하의 자연수라는 조건이 없어 실수 연산을 해야했는데, 신입생이 풀기엔 부적절한 난이도라 판단하여 해당 조건이 추가되었습니다.
여담이지만 이 문제의 상위호환 격인 역행렬을 구하는 문제가 골드 III이라서 한단계 아래인 골드 IV로 투표했는데, 이 문제덕에 가우스 소거법이 재조명되면서 ‘가우스 소거법은 플래티넘 난이도가 적절하다’는 의견이 정론이 되어가고 있네요. 현재 골드 1인데 머지 않아 플래티넘으로 갈 것 같습니다.
G. RPG 마스터 오명진
검수진 예상 티어: 실버 II
실제 티어: 실버 I
출제자이신 dkvltmxhf님이 의도한 풀이는 여러 번의 공격을 사칙연산을 통해 한 번에 처리하여 상수 시간에 푸는 것으로 보입니다. 하지만 반복문을 통해 일일히 시뮬레이션을 돌려보는 코드, 답이 int 범위를 초과할 수 있는데 int를 사용하는 코드 등이 통과하는 이슈가 있어 데이터가 추가되었습니다. 이외에도 지문이 다수 수정되었는데, 대부분은 용사의 공격 한번에 마왕의 체력이 0 이하가 되는 경우의 처리에 관한 것이었습니다.
후기
여태까지 단순히 문제를 푸는 입장에서는 풀이를 찾아서 AC를 받으면 그 문제를 웬만해서는 다시 볼 일이 없었지만, 검수자의 입장이 되니 내 풀이뿐만 아니라 다른 사람들의 풀이(내지는 사풀)를 모두 고려해야 하다 보니, NPC는 상당히 쉬운 문제로 구성되어 있었음에도 검수 과정은 쉽지만은 않았습니다.
그래도 재미있었습니다! 특히 C번에서 나온 다양한 잘못된 풀이들과 python풀이와 c++풀이 간의 난이도 격차 가지고 토론하는게 재미있었네요. 다음번에도 검수진 필요하면 불러주세요 :)