여기에서 이야기했듯이, 반년대회로 돌아왔습니다. 이제 대회에 나가서 상을 탈 실력이 안 된다고 판단해서, 문제를 많이 내 보려고 합니다.
팰린팰린드롬 이라는 문제를 출제했습니다.
는 지문과 동일하게, 꼬들꼬들한꼬들꼬들은 팰린팰린드롬이라는 발상에서 시작했습니다.
지문에 쓴 것과 다르게 원본에는 공백이 없더라고요
정해는 신문 문제 때처럼 정말 빨리 나왔습니다. 양쪽에서 그리디하게 제거해주면 되는구나 → 롤링 해시를 쓰면 O(N)이구나 라는 발상이 한 3분 만에 나왔던 것 같아요.
바로 삼중 해싱을 쓰는 정해를 짜서 콜포태에 제출했고, 최종 선정되어서 감사하게도 반년대회의 출제진이 될 수 있었습니다.
그런데, 풀이 내기를 제외한 모든 면에서 문제를 세팅하기가 참 힘들었습니다. 그럼에도, dkim님이 저를 정말 많이 도와주셔서 꽤 순조롭게 세팅을 할 수 있었던 것 같습니다. 정말 감사합니다.
제일 먼저, 팰린팰린드롬을 엄밀하게 정의하고 잘 정의하는 게 참 힘들었어요. 제가 지문을 잘 쓰는 편은 아니기 때문에 팰린팰린드롬을 잘 설명하려고 정말 많은 고민을 거쳐서 지문을 썼는데, 대회 중에 질문이 없었던 것으로 보아 꽤 성공적으로 지문을 작성한 것 같습니다.
가장 어려웠던 건 데이터 만들기였습니다. 문제의 정해가 해싱이었기 때문에 잘못된 해싱(특히 모듈러가 $2^{64}$인 라빈 카프)을 저격했어야 했고, 사풀이들을 통과시키지 않기 위해 최대한 다양한 특성을 가진 문자열들을 생성해야 했습니다. 그래서 제너레이터를 13개를 짜서 데이터를 열심히 만들었습니다.
혹시 이 글을 읽는 분들 중 문자열 해싱을 사용하는 문제를 만들고 싶은 분이 있다면, https://codeforces.com/blog/entry/60442 이 글을 읽어보시는 것을 추천합니다. $2^{64}$로 나누는 잘못된 해싱을 저격하는 방법이나 생일 역설을 사용해 작은 모듈러에 대한 반례를 만드는 것 등 많은 내용이 담겨 있습니다.
저와 dkim 선배가 작성한 제너레이터들
그럼에도 불구하고, 본대회에서 $O(N^3)$ 코드가 50점을 받고, $O(N^2)$ 코드가 만점을 받는 참사가 일어났습니다.. 그래서 본대회가 끝난 다음 날 모든 20점 이상의 점수를 받은 코드를 읽어보면서 통과되면 안 되는 풀이를 저격했고, 약 3시간 반 정도를 써서 사풀이 네다섯 개를 저격하는 데에 성공했습니다.
세팅을 열심히 했음에도 문제가 뚫려서 정말 슬펐습니다. 사풀이를 더 열심히 생각해내서 미리 막았어야 하는데, 안일하게 생각해서 그러지 않았던 것이 원인인 것 같습니다. 언제쯤이면 문제 오류가 없는 문제를 만들 수 있을까요..
여담으로, dkim 선배가 해싱을 안 쓰는 풀이를 내 주셔서 정해에서 해시 충돌이 나면 어떡하나 하는 걱정을 덜 수 있었습니다. $O(N)$ sa + $O(N)$ rmq를 사용하면 가능하다고 합니다. 자세히는 모르겠고, 그냥 이런 풀이를 10분만에 만드실 수 있다는 사실이 경이롭네요
재밌었습니다. 진짜 재밌었습니다.
일단 제가 처음으로 운영해 본 풍선을 달아주는 대회였는데, 풍선 달아주는 게 꽤 재밌었습니다. 백준 님이 기능을 잘 만들어놓으셔서, 누구에게 풍선을 전해줘야 하는지가 관리가 잘 되더라고요. 닉네임을 보고 그 자리를 찾아가서 달아주는 식으로 했는데, 정말 비슷한 두 닉네임 ⬆️❤️⬇️과 ⬇️❤️⬆️이 있어서 참 헷갈렸습니다.