Semi Game cup 후기글 (문제별 후기 포함)

그냥 주저리 주저리 쓴 글입니다... 가독성이 안 좋을 수 있지만 나름 재밌을 수도 있습니다.

전체 후기 

한 달 동안 다른거 줄여가면서 정말 열심히 달려왔다. 지금 이 그림을 머릿속에 그려놓긴 했지만, 이 그림이 현실로 다가올지는 상상도 하지 못했다. 오늘이 생일이라서 더 뜻깊은 것도 있는것 같다.
 시작은 그저 아이디어는 조금 있는데 백준 스택 권한이 없어서...도 있었고, 게임문제를 미친듯이 풀어대는 나의 모습을 보고 주위에서 장난식으로 한 번 만들어보라고 했던 이유도 있었다. 무엇보다 사람들의 어그로도 끌고 싶었고, 뜻 깊은 경험이 될 것 같았다.
 사실 의지만 가지고 하기에는 좀 많이 벅찬 여정이었다. 최근 대회퀄이 너무 좋았기 때문에, 계속해서 뇌절 아이디어만던져대고 시간은 다가오고, 급박했었다. 무엇보다 아프게 다가왔던 것은 경험이 없었다는 점이다. 대회 관련해서는 검수조차도 거의 한번도. 이 경험 부족은 굉장히 뼈아프게, 크게 다가왔다. 어쩌면 몇 아이디어만 믿고 너무 까불었는지도 모르겠다.
 하지만 적어도 나에게 능력하나는 있었다. 정말 훌륭한 사람들을 내 곁에 두는 능력. 정말 말도 안되는 라인업의 검수진을 구성하는데 성공했고, 문제 내적으로나 외적으로나 정말 많은 도움을 주셨다. 특히 알지 못하는 사이인데도 흔쾌히 응해주신 jh05013님을 비롯하여 다른 모든 검수진들에게 정말로 감사하다는 말을 하고 싶다. 이 말고 내 능력은 많이 부족했고, 검수진분들 중 한 명이라도 부족했으면, 이 대회는 성립할 수가 없었다고 생각한다. 
 시간이 생각보다 굉장히 빠듯했다. 초반에 불탔지만 일정시간 이후로 너무 나태했던 것도 한 몫을 했고, 이또한 경험부족으로 시간 예상을 제대로 하지 못했다. 특히 마지막날 데이터 하나 다운로드를 해야하는데, 커밋을 하려니 폴리곤이 터져서 다 날라갔고, 다시 다 작업했더니 폴리곤 서버가 너무 느려서 3~4시간이 걸렸다. 12시에 모든문제가 열리지 못할 가능성도 아예 없지는 않았다. 그래서 이 자리를 빌어 백준님께도 사과와 감사의 말을 드리고 싶다.
 하지만 이번 경험을 발판삼아 더 앞으로 나아가려고 한다. 내 글이 점점 보기 이상한 것 같기도, 필력이 그리 좋지도 않으니까 빨리 문제별 후기로 넘어가려고 한다.

A. 왕들의 외나무다리 돌 게임

좋은 문제를 만들어야 한다는 압박감에 시달리던 중, 체스판 한 쪽에 흰 말, 반대편엔 검은 말이 있고 앞 뒤로 움직이는 것을 보게 되었다. 그 순간 바로 문제가 떠올랐다. 그리고 생각을 조금 해보니 풀이도 바로 떠올랐다. 완전 갓문제는 아니지만 입문 A번 문제로 손색이 없을 좋은 문제였다. 관찰이 조금 섞인 + 사전지식 (자료구조) 문제. 내가 정말 원하던 스타일이었다. 준비과정에서 착오도 없었다.
A 퍼솔이 23분???? 굉장히 당황했다. 좀 더 빨리 풀릴 줄 알았는데 D퍼솔에 눈길이 끌려서 느렸던 것 같다. 하지만 시간이 지나니 결국 입문 문제, 제일 많이 풀린 문제였다. 사실 굉장히 많이 풀릴 줄 알았는데 전체적으로 간과한 사실이 있다. 하나는 게임이론이 좀 마이너하다는 것이었고, 두번째는 검수자들은 다 아는 괴물들이었다는 것이다.

B. 돌 술래잡기 게임

내가 결국은 풀었지만 blackking이랑 같이 루비뽀개기를 하다가 잘못봐서 생겨난 문제다. 정말 살짝 다른데 풀이는 완전 크게 달라졌다. 검수과정에서 완벽한 풀이가 계속 안나왔었는데, 서로 다른 두개의 접근으로 짠 코드가 완벽히 같은 답을 낼 때 소름돋았다. 하지만 끝까지 불안에 떨게 한 문제였다. 풀이도 자신감이 있었지만, 뭔가 많이 불안했고, 데이터는 급했기 때문에 데이터도 불안했다.
결국 대회에서 N^2 이 뚫렸다.... 사실 뚫리는게 당연할 정도로 조건문을 조금만 추가하면 저격데이터를 만드는게 거의 불가능해 질 정도이다. 또한 N^2까지 생각하는게 풀이의 거의 전부를 차지하므로 크게 상관이 없었다. 특히 앞부분의 데이터가 많이 약해서 정말 대충짜도 50%를 통과할 수 있는데, 이 때문에 꽤나 어려운데도 불구하고 좀만 더하면 맞을 것 같다는 망상을 가지기 쉬웠다...

C. 경비병 세우기 게임

IMO 국대! 수학의 신!이 추천해준 문제이다. 말도 안되게 좋은 풀이에 꽤나 어려운 문제. 난 이 문제가 정말정말 좋은 문제라고 생각한다. 내가 추구한 이 대회의 문제스타일과도 꽤나 맞아떨어졌다. 제한은 좀 낚아볼고 했다... 뇌절인것 같아 죄송하다.
생각보다 훨~~씬 적게 풀렸다. 나는 문제의 난이도에 비해 proof by ac로 정말 많이 풀릴 줄 알았다. 특히 대충 대칭 전략 생각하면 맞을 수도 있다. 사실 코포였으면 다들 proof by ac로 그냥 도전해볼 가능성이 꽤 크다고 생각한다. 

D. 숫자카드 제거 게임

TST에 있던 문제를 좀 변형시켜서 만든 문제이다. 맨처음에는 N^2 그런디로 풀려고 하다가 나도 처음에는 %4가 규칙인줄 알았다. 집 앞 산책을 하면서 전자노트에 끄적여보니까 아니었다... 바로 코딩으로 찍어봤고, 나는 바로 규칙이 보였다. 검수자들 별로 편차가 정말 심하게 갈린 문제이다. 다들 규칙찾기라는 것은 발견했지만 사람별로 규칙을 정말 못찾기도 바로 찾기도 했다. 대회에서는 어떨지 궁금했다.
생각보다 꽤 많이 풀리고 퍼솔도 나왔다. %4 뇌절을 보는 것은 언제나 즐거웠으며 %12,<14 등등 별의별 가능성을 다 시도해보는 수많은 코드들이 있었다. %4를 딱 보는 순간 역시 사람 생각은 다 똑같다는 것을 느꼈다. 

E. 평면그래프 게임

maruii와 TAMREF가 문제 아이디어를 생각하고 stonejjun03이 디스크립션을 만들었으며 TAMREF가 데이터를 만들고  ahgus와 gs18115가 검수를 한 문제... 사실 난 디스크립션 말고 손을 안댔다. 잘모른다. ㅋㅋ! 
생각보다 말도 안되게 많이 풀린 문제. 홀리... 맙소사... ------- 기법을 쓰는 문제가 4번째로 많이 풀린 대회가 있다??? 진짜 말도 안되는 스코어 보드입니다...

F. 고인물의 리듬게임

stonejjun03은 DP 원툴입니다. 다른 글들과 DP 기초글들을 보면 알 수 있다. 따라서 DP opt 한 문제는 내야겠다고 생각했다. 사실 처음에는 Ci 대신에 그냥 C였다. 이로써 cht를 유도 했었는데 문제 대장장이가 오셔서 Ci와 단조감소를 넣고 풀이를 다양화 시켜주셨다. 
아니;;;; 왜 안풀렸지;;; 검수진들 모두의 예상은 4번째로 쉬운문제였다. 그냥 웰노운. 쉽게 보이고 추측가능한 DP opt 문제. 사실 어쩌면 다른 문제에 충격을 받아서 "이게 단순할리 없어!" 라고 생각들을 하셨나보다. 그거말고는 설명이 안된다.

G. 지역꾸미기 게임

문제 출제의 장인이자 이 대회의 품격을 높이게 해주는 blackking을 알아보고 미친듯이 내가 갈궈서 출제하게 만든 문제. 사실 나랑은 별 관련이 없어서 할 말이 없다.
올솔을 막아준 고마운 문제!! 좌셋을 막아버린 슬픈문제..

H. Non-decreasing subarray Game

할 말이 많다. 이번 usaco 플레 문제에서 subsequence인데 잘못보고 subarray 판을 금광세그를 써서 풀었다. 거기에 min-max distance game의 아이디어를 환상적으로 얹어서 탄생한 좋은 문제라고 생각한다. 그런데 또 그분께서 로그제곱에서 로그로 줄이고 선형으로 줄여버리셨다.... 근데 로그 풀이가 좋아서 그걸로 바꾸었다. 검수과정에서 이미 금광세그로 푼 많은 분들이 새 풀이를 찾는데 정말정말 많은 시간이 걸렸다. 꽤나 좋은 낚시가 될 것 같았다.
역시나 금광세그는 굉장히 매력적이다. 몇몇분들이 깔끔하게 낚이셨고 열심히 커팅을 시도했지만 당연히 실패했다. 그 모습을 보며 죄송하지만 행복했다. 사실 좀 많이 행복했다. 사실 예상보다 많이 느리게 풀렸다. 퍼솔이 한시간 

I. 조작된 ㄱ 폭탄 게임

3주간의 역작!!! 내 모든 힘을 다한 문제... 사실 나는 사전지식이 거의 없는 상태로 이 문제를 설계했다. 사실 잘못된 뇌피셜 사전지식이 추가된 상태였다. 1주반동안 고민했는데 나오지 않았고, 1개 조건을 넣는 순간 풀이가 생각나서 너무 짜릿했다!!! 물론 그 풀이가 망했다. 정말 당황했고, 또 하루를 꼬라박아서 새로운 풀이를 만들어 냈다. 정말 다행이었다... 
사전지식을 완벽히 이해하면 생각보다 꽤 빠르게 풀릴 것이라고 예상했고, 역시 사전지식을 아는 분들이 잘 풀어주셨다.