히농의 잡합다식
이 멋진 대회에 출제를! (부제 : SUAPC 2022 Winter 출제 후기) 본문
작년 여름에 4연속 대회 검수를 했다가 너무 바빠서 고통스러웠던 기억만 남았고
'아...회사 일과 검수를 병행할 수 없으니 이제 검수진은 하지 말아야지' 라고 생각한게 얼마 안된거 같은데..
이렇게 같은 실수를 반복해버렸습니다.
유달리 이번 달에 갑자기 회사 일이 많아지면서, 이번달 필수 근무시간이 +20 시간을 초과한 상황입니다..
그럼에도 불구하고 SUAPC 2022 Winter contest 대회의 출제진이 되었고.. 문제를 무려 4개나 출제를 했습니다.
문제를 4개를 출제하게 된 배경은 별건 아니였는데.. call of task 지원 당시에 문제를 네 가지 난이도별로 받고 있었고, 제가 가지고 있던 문제들도 딱 저 난이도 분포대로 있길래 그대로 문제 4개를 던졌고... 그 중 3개가 실제 대회 때 채택이 되었습니다. (비슷한 난이도의 문제가 많다는 이유로 탈락했는데, 탈락한 문제 1개도 아주 엄청난 문제이므로, 언젠간 기회가 되면 출제를 해보고싶네요.)
그렇게 3개의 문제를 출제하는 상황에서, 브론즈급 후원사 문제를 하나 구하게 되었고.. 투표를 통해 제가 작성한 문제가 당첨이 되었습니다.
이렇게 문제 4개를 출제하게 된 출제진 pichulia 는... 일이 너무 많았답니다. 하하..
애석하게도 이번 대회의 문제를 출제하면서 프로그램으로 그림을 그린게 "불협화음" 한 가지 밖에 없었고, 그림을 그리기에는 4문제 출제하는 제 코가 석자였기 때문에, 그림 그리는 것은 다른 전문적인 사람들에게 맡겼습니다. 그래서 게시글 분류도 프로그래밍이 아닙니다.ㅋㅋㅋ)
작년 여름처럼 검수하는 대회가 동시에 4개였던 시절을 제외하고는 왠만해서는 모든 문제를 검수하려고 노력합니다. 덕분에 평생 짜볼 생각을 안했던 선인장 BCC 코드도 구현..하진 않고 검색해서 복붙해볼 생각도 해보고, 실제로 정답도 받아서 색다른 경험이였습니다.
이 글에는 풀이에 대한 언급은 일절 하지 않을 예정이고,
그냥 제가 출제하면서 느꼈던 이모저모를 자연스럽게 적어놓고자 합니다.
풀이는 뭐, 다른 사람들이 잘 정리해서 올려주겠죠.
키랏-☆
대회 문제 출제 이야기로 돌아옵시다.
제가 이번에 출제한 문제는 C번 카카오뷰 큐레이팅 효용성 분석 , I번 이 멋진 수열에 쿼리를, J번 일이 너무 많아..., M번 불협화음 이렇게 총 4개의 문제를 출제했습니다.
예상 티어를 각각 브론즈5 / 플레1 / 골드3 / 다이아2 로 잡고 시작했는데.. 실제 결과는 어떻게 나올지..두둥...
1. 카카오뷰 큐레이팅 효용성 분석
문제에 적힌 조건대로 잘 구현하면 되는, 언어 조금 할 줄 아는 사람이라면 누구나 풀 수 있는 문제로 설계해서 만든 문제입니다. 정말 최소한의 조건으로, '흥미도' 값인 Ai 를 배열에 저장할 수 있는 사람만이 풀 수 있도록 하기 위해서
일부러 Ai 정보를 N번 주고, 그 다음줄에 Bi 를 주도록 했습니다.
사실 이 문제는 문제 풀이를 먼저 정해놓고, 그에 맞춰서 컨셉을 어거지로 끼워넣은 문제에 해당합니다.
그리고 애초에 카카오뷰 후원사 문제로 탄생하지도 않았습니다.
원래는 현대오토에버 후원문제로 기획해서 그렇게 지문을 쭉 적었고, 그에 맞춰서 풀이 및 데이터도 다 만들어놓은 상태였습니다. 그러다가 오토에버측에서 문제 출제 가이드라인으로 온게 있었고... 정말 아쉽게도 출제 가이드라인에 맞춰가면서 이 문제를 그대로 쓰는게 너무 힘들었습니다.
그래서 원래는 카카오뷰 후원 문제를 만들 예정이였던 G번 도로 정보 랑 후원사를 바꾸기로 해서 만들어진 문제입니다.
후원사를 바꾸기 전에 'G번 문제에서는 ~~~ 를 홍보하고, 이 문제에서는 ~~~ 를 홍보하면 되겠다.` 라고 계획해서 이래저래 협의를 거친 후 후원사를 바꾸는데 성공했습니다. 그래서 두 문제 다 데이터 하나도 안고지고 지문만 바꿔서 해결! 거기까진 좋은데... 디테일한 요소를 적어넣다보니 의외로 설명할게 많아지고, 말이 좀 주저리주저리가 되어버렸습니다. 문제 지문을 읽는 사람들은 조금 고통스러워하지 않았을까 싶기도 했던 문제입니다.
2. 일이 너무 많아...
실제로 일이 너무 많아서 만든 문제입니다.
회사 메신저에서 파트 사람들에게 일어 너무 많다고 혼자서 중얼거리면서, 제가 무의식적으로 죽죽 내뱉은 말이 그대로 문제가 되었습니다.
대략 이런 흐름이였습니다.
"아.. 일이 너무 많다... 일이 하나만 있는 것도 힘든데 일이 여러개가 있네요...
이 때 여러개의 일로 이루어진 수의 개수를 구해보자!...으아아.... (일하러 감)"
이런 헛소리에서 이제 좀 더 문제스럽게 다듬어서, 평범한 포함배제 문제가 되었습니다.
이 문제는 원래 카카오 후원사 문제가 될 계획은 없었습니다. 자세한 사항은 불협화음 문제 설명 때 서술하겠습니다만...
여튼 후원사 관련해서 문제가 생겼을 때 남겨둔, 제 나름의 Plan B 로써 이 문제를 남겨놨었고... 실제로 Plan B 가 발동해 후원사 문제가 되어버렸습니다.ㅋㅋㅋㅋ
사실 반 장난삼아 "일이 너무 많은 블랙기업 이미지가 남게 되니, 후원사에서 싫어하지 않을까?" 라고 생각했는데...
"7년 경력을 가진 신입 개발자로 입사한 pichulia" 라는 헛소리도 받아준 카카오의 너그러운 아량으로 인해서 그냥 무사히 넘어가게 되었습니다. (사실 무사하지 않을 수도... 이제 카카오로 이직 못할듯 절대로ㅋㅋㅋ)
참고로 올해가 삼성전자에서 경력 7년차. 진짜로 7년차 개발자가 되어버렸습니다.. 으어어어....
사실 이 친구도 call of task 당시에 비슷한 난이도의 문제가 많다고 빠꾸먹었던 친구중 하나였습니다. 그러다가 출제진중 한명이 각.개.전.투 를 가게 되었고... 그 빈자리를 채우기 위해 이 문제가 다시 올라왔습니다. 그랬던 친구가 후원사 문제로까지 진화를 해버리네요 ㄷㄷ
사실 너무 갓 문제라서 100% 채택될줄 알고 데이터 셋팅까지 다 끝내놓은 상태였는데... 빠꾸 먹었을 땐 조금 슬펐었습니다. 뭐, 이 때 데이터를 만들어놓았다는 이유로 빈자리를 빠르게 채울 수 있었고, 결국 출제를 했으니 메데타시 메데타시.
3. 이 멋진 수열에 쿼리를!
한별이를 그리고 싶어서 만든 문제입니다. 하하.
모티브가 된 소설/애니 를 전혀 보진 않았지만, 몇 가지 간단한 설정은 알고있었습니다.
그 중에서 "마을 밖에 있는 고성에 하루에 한번씩 폭렬마법을 날려서 성에 살고있던 주인이 화가 났다" 라는 설정이랑,
"주인공이 경찰?에게 조사를 받을 때 무슨 거짓말을 말하면 울리는 종 때문에 기분이 나빴다" 라는 두 가지 설정을 차용해서 문제상황을 구성하였습니다.
문제 컨셉과 메인 이미지, 그리고 풀이는 1년정도 전에 다 만들어놓았었습니다.
위 이미지는 제가 한별이 창조주님께 보낸 콘티입니다. 종이와 연필을 이용해 흑백으로 끼적끼적 할줄만 알지, 이를 디지털화 시키는 능력은 한참 부족해서 어쩔 수 없이 한별이 창조주인 havana723님께 제작을 요청했습니다.
콘티로 맨 처음 만들어진 결과에서 수열(水列) 이 아니라 흙길이 나와서 이에 대한 간단한 피드백을 주었고... 이후 이래저래 주고받으면서 최종 귀여운 한별이 이미지가 탄생했습니다.
solved.ac 배경으로 쓰이지 않을까? 싶어서 일부러 한별이를 우측에 배치해놓고 그랬는데... 대회가 운영되는동안 사이트 주인장님께서 각.개.전.투 를 하러 가셔서, 배경 이미지화 여부는 불투명합니다.ㅠㅠ
이 친구도 너무 멋진 문제라서 100% 채택될거라 생각해서 데이터를 미리 만들었던 문제입니다.
검수 도중에 다이아4급 아이디어를 이용한 풀이가 새로 튀어나왔는데..
제가 출제할 때 생각했던 풀이랑은 방향이 완전 달라서 저도 이해하는데 고생좀 했습니다. 어쨌든 출제 기간 내에 해당 풀이를 이해하는데 성공했고, 풀이 pdf 에 적어놓는 것에 성공했습니다만.. 사람들이 이걸 보고 이해할 수 있을지는 모르겠네요.
여담으로, 사람들 사이에서 소위 "금광세그" 라고 불리는 세그트리 테크닉이 하나 있는데.. 그런 것처럼 세그먼트 트리에 행렬을 붙여넣는 아이디어로 푸는 테크닉을 이 문제 이름에 맞춰서 "코노쿼리" 라고 사람들에게 불리우기를 바라는 자그마한 욕심이 있습니다. 하핫..
위에 문단에 살짝 힌트가 적혀있긴 하지만.. 이 문제 정말 재밌습니다. 한번씩 다들 고민해주시길.
4. 불협화음
행복한 기하문제 입니다. 행복하셨나요? >ㅅ<
저에게 한국음반저작권협회라던가 가사 저작권을 구입하는 방법에 대해 연구하게 만든 불운의 문제입니다.
초반에는 지문에 가사 일부가 포함되어 있었는데, 원저작자로부터 별다른 응답이 없어서 그냥 빼버렸습니다.
여담으로 제가 찾아본 저작권 관련 협회들은 죄다 진짜 음악 그 자체에 대한 저작권을 다루고있었고... 가사같은 경우는 총 몇 부를 인쇄할거냐고 물어보고 있길래, 인터넷 공개 배포되는 이런 문제같은 경우에는 어떻게 처리될지 모르겠어서 그냥 가사 삽입을 포기하였습니다. ㅠㅠ
이 문제는 원래 카카오 후원사 문제였습니다. 사실 그냥 저희 멋대로 "멜론도 카카오 밑에 있으니까 그냥 카카오 후원 문제로 만들면 되겠찌?" 하면서, pichulia 가 카카오 서비스를 통해 막 음악 주고받고 머시기 저시기 하는 문제였습니다.
근데 멜론이 엄밀히 말하면 카카오에서 서비스하는게 아니여서 후원 목적에 맞지 않으니, 컨셉을 카카오지갑으로 바꿔달라는 피드백을 대회 개최 이틀전에 알게 되었고... 저의 Plan B 가 발동되어서 일이 너무 많아가 카카오지갑 문제가 되었습니다.
아 너무 슬픈 전설이다...
슬픈 이야기들은 뒤로 하고 이제 기하 얘기로 넘어가보겠습니다.
이 문제 컨셉 자체는 과거에 검수했던 문제 중 하나인 BOJ 19586번 울타리 를 검수하다가 나왔습니다.
해당 문제에서 핵심이 되는 Lemma가 "사각형 4 개의 변 중 하나가 convex hull 의 변과 일치하는 직사각형 중 정답이 되는 케이스가 존재한다." 가 있었습니다. 이 Lemma 를 증명하는 과정에서 함수 꼴이 Z * sin(theta + alpha) 꼴이 된다는 것을 알아냈고... 문제를 푸는 사람들이 이 식을 유도해내기를 원하는 마음으로 문제를 출제하였습니다.
사실 "최소 삼각형" 의 경우에는 위 함수꼴을 증명하지 않더라도, 세 변중 하나가 convex hull 의 변과 일치하면 된다고 "찍어서" 맞출 수 있기 때문에, 트로피보다 철학이 중요한 저의 출제 의도와는 어긋났고 식을 유도하도록 하고싶었던 저의 마음을 가득 담아서 "최대 삼각형" 까지 구하도록 했습니다.
사실 함수꼴이 볼록함수라고도 "찍어서" 맞출 수도 있었는데.. 뭐 이정도는 너그러이 넘어가도록 했었습니다.
찍어서 맞추는 얘기가 잠깐 나왔는데.. 사실 이 문제는 랜덤으로 풀 수 있습니다. 랜덤한 삼각형을 여러개 정해서 그대로 테스트를 해보는 풀이를 물리적으로 막을 수 없었습니다. (사실 막을 순 있지만 대회 시간 내에 아무도 못풀거 같아서 그냥 안막았습니다. 랜덤으로 풀 수 없는 버전은 언제 기회가 되면 누군가가 출제해주시길...)
원래는 오차범위를 1E-9 로 설정해서 10^7 번의 랜덤한 삼각형을 시도하는 풀이를 막았었는데, 검수 과정에서 너무 tight 하다는 피드백을 받아서 10^6 번의 랜덤한 삼각형 정도는 막아주는 1E-7 로 합의를 보았습니다.
그리고 이건 이미지 제작용 프로그램입니다. 문제에 쓸 적절한 이미지도 만들고 싶었고...
뭐 이런식으로 삼각형이 싫어할법한 정점 10만개짜리 convex hull 잘 만들어졌는지도 확인하고 싶습니다.
기타 여담
제 문제 중 일이 너무 많아 랑 불협화음 두 문제가 특별상이 있는 문제였습니다.
불협화음 문제같은 경우에는 정답자가 아무도 없을거라고 가정했고.. 그냥 "정답 여부와 상관없이 불협화음 문제에 뭐라도 제출한 사람" 을 특별상 수상 기준으로 정했습니다. 이렇게 정한 이유는.. 분명 100% 모든 문제에 이상한 코드를 제출하는 팀이 한두팀정도 있을 것이라고 예상했고, 그 팀에게 기하를 사랑하는 마음으로 버니어 캘리퍼스를 선물로 주고싶었습니다. 그리고 그 예상은 적중되었습니다.
만약 근시일 내에 버니어 캘리퍼스가 당근마켓에 올라온다면 다 저의 계획대로입니다. :)
일이 너무 많아 문제는, 스코어보드상에 1 이 너무 많은 팀에게 주고싶었습니다. 원래는 문제별 패너티도 표시되는 백준표 하얀 스코어보드를 상상했었는데.. 문제별 패널티는 표시해주지 않아서 아쉽게도 해당 숫자에 대한 랜덤성이 떨어져버렸습니다. 그래서 그냥 진짜 화면에 표시된 숫자 1이 많은 팀에게 주기로 했고...
그 결과, 아까 그 모든 문제에 한번씩 제출을 한 팀이 이 특별상을 받아버렸습니다. 틀려서 뜨는 숫자 1 때문에 특별상 조건을 만족해버렸고.... 여러 가지 고려한 결과 (버니어 캘리퍼스는 상이라기 보다는 벌칙에 가깝다는 생각에 의해) 그냥 특별상 중복수상이 되었습니다. 일이 너무 많아 특별상은 평범하게 일기장입니다.
문제 난이도 분포에 대한 의견은 내부적으로 조금 있었습니다만.. 저희들은 참가자들을 믿었습니다.
문제의 난이도를 고르게 출제한다는 것은 정말 어려운 일인거 같습니다. 출제진의 예상 난이도와 실제 난이도 사이의 간극도 무시할 수 있는 수준이 아니며, 출제 및 검수를 하는 사람들은 기본적으로 다 짬밥(?)들이 있기 때문에.. "아 이거 이렇게 풀면 되겠따!" 가 금방금방 보이시겠지만 문제를 푸는 사람 입장에서는 그게 아니기 때문이죠.
플레티넘급 문제를 설계한다는 것은 생각해보면 참 어려운 일입니다. "금방 풀 수 없을 정도로 어렵지만, 고민을 하다보면 사람들이 풀 수 있을정도로 쉬운 난이도" 라니.. 생각해보면 참 엄청난 구간의 난이도라 할 수 있겠습니다.
일단 저는 제 위치에서 최선을 다해 저의 역할을 수행했습니다. 문제들의 컨셉, 지문, 데이터, 풀이. 모든 것이 저의 마음에 들게 나왔습니다. 여러분들도 즐겁고 재밌게 푸셨기를 바라면서... 전 다시 회사일을 하러 가겠습니다.
(일이 너무 많아~~)
'잡담' 카테고리의 다른 글
| 미로 만드는 모듈을 C++로 만들어보았다. (0) | 2015.11.28 |
|---|---|
| 지뢰찾기 고해상도 버젼(커플스위퍼)를 만들어보았다. (0) | 2015.11.18 |
| C언어 뿌요뿌요 (9/15) (2) | 2012.09.15 |
| 테스트글 입니다. (0) | 2012.08.03 |
