제 1회 곰곰컵 출제 후기 (부제 : 숨겨진 12번째 문제?)
곰곰이는 귀엽습니다. 너무 귀여운 나머지 곰곰이 이름이 들어간 프로그래밍 대회까지 열려버렸습니다.
https://www.acmicpc.net/contest/view/792
제1회 곰곰컵
www.acmicpc.net
다른 분들의 출제 후기는 개최자이신 pjshwa님 블로그나, 공지글을 올리는 등의 작업을 해주신 Ims0806님 블로그 등을 통해서 확인하실 수 있습니다.
이번 대회 출제진들 중 유일한 codeforces 레드 레이팅 출제진으로써 조금 힘을 내서 문제를 출제해야겠다고 (저 혼자서) 큰 다짐을 했었습니다.
그리고 너무 힘을 냈나봅니다. 출제자 피셜 플레2 난이도의 문제가 마지막 문제로 출제될 예정이였습니다만, 검수진 중 아무도 이 문제를 푼 사람이 없었기 때문에 결국 출제를 하지 못했습니다.
이 문제 또한 아주 엄청난 문제이기 때문에 다음에 다른 대회나 제 2회 곰곰컵 등이 열린다면 그 때 다시 출품하겠습니다.
이번 대회에서 제가 출제(했고 마지막까지 생존)한 문제는 "Yes or yes" 하나입니다.
다른 게시글에서 언급했던, 탈락한 엄청난 문제가 바로 이 문제입니다.
https://www.acmicpc.net/problem/25195
25195번: Yes or yes
첫째 줄에는 정점의 개수 $N$과 간선의 개수 $M$이 주어진다. ($1 \leq N, M \leq 100\,000$) 이후 $M$줄에 걸쳐서 간선의 정보를 나타내는 두 정수 $u$, $v$ 가 주어진다. 이는 정점 $u$ 에서 정점 $v$ 로 가는
www.acmicpc.net
원래는 불협화음과 셋트로 출시하고 싶었던 대중가요 관련 음악문제였고, 아무튼 귀여운 투어리스트 곰곰이로 재탄생했습니다.
출제 의도는 아주 명확합니다. No가 아니라 Yes 또는 yes를 출력하는 문제를 만들고 싶었습니다. 그래서 지문에서도 출력문을 설명할 때, 두 경우 모두 긍정문인 것을 확인할 수 있습니다.
처음에 이 문제를 제작할 때, "뭘 골라도 날 만나게 될거야" 라는 가사를 최대한 살리면서 만들 수 있는 문제를 만드는 것이 목표였습니다.
그래서 "뭘 골라도" --> Decision tree 같은걸 만들자! "날 만나게" --> 해당 트리에서 '날' 에 해당하는 노드를 지나는지 체크하자! 같은 흐름으로 문제 지문을 만들었고.. Decision tree 보다는 DAG 가 알고리즘 친화적이기 때문에 DAG 로 바꾸는 등의 작업을 통해 Yes or yes 문제가 만들어 졌습니다.
여기서 그래프에 사이클이 있게 된다면 좀 많이 골치아파졌습니다. 곰곰이의 '여행 종료 조건'을 정하기가 참 어려워지기 때문이였습니다. 지문이나 사람들이 풀이를 생각하도록 유도하기 편하게 하기 위해 + 데이터를 만들기 편하려고, 그래프를 일부러 DAG 로 골랐습니다. (일반 그래프에서 이 문제를 풀 수 있는지는 고민 안해봤습니다. 하하)
사실 Yes or yes 는 지문이나 데이터같은걸 SUAPC 대회 준비할 때 거의 다 만들어놓은 상태였어서 더 이상 할 것이 없었고... 이번 대회는 날로먹었습니다. 아 달다 달아.
사실 원래 이 후기글에는 [검열됨] 문제에 대한 후기로 가득 채워질 예정이였습니다만...
저의 게으름으로 인해서 결국 대회 출제까지는 못하게 되었습니다 ㅠㅠ
지문 및 데이터, 이미지 등은 전부 준비되어있지만, 이 문제를 담을 수 있는 그릇의 대회가 없군요(...?!) ㅋㅋㅋㅋ
