제 1회 소프트콘 출제 후기

작년 추석 즈음에 BOJ 슬랙에서 jwvg0425님이 같이 대회를 열 분들을 찾고 있다는 말을 들었다. 나도 문제를 출제해보고 싶어서 대회 출제를 하게 되었다! 7문제 중 3문제를 출제했다. 이 글은 그제 대회가 끝나고 후기 겸 작성하는 글이다. (스포일러도 약간 있다!)

대회 URL

풀이

K-균등 문자열

이 문제는 내가 전부터 생각해 놓았던 문제였고, 어렵지 않게 디스크립션, 데이터와 솔루션을 만들 수 있었다. 커팅 풀이가 통과할 일이 거의 없어서, (O(NM) 다음에 빠른 풀이가 O(NM * 2^N)이었다) 랜덤으로 거의 모든 데이터를 만들었다. 유니언 파인드에서 경로압축을 안 한 풀이가 시간초과가 나는 걸 확인하고 데이터는 더 이상 만들지 않았다. 대회에서 그것 때문에 TLE 난 제출도 있었는데, 뭔가 뿌듯했다(?)

프로그래밍 대결

계절학교 가을 통신 교육에서 비슷한 문제를 풀다가, 어, 이거 MCMF로 모델링되네? 하고 풀어보려고 했지만 N이 너무 커서 실패했었던 걸, 그 문제에서 제한과 제약을 수정해서 MCMF 문제로 만든 게 바로 이 문제다. 플로우 문제라는 걸 깨닫고 나면 모델링하는 건 쉬운 편인 것 같다. 이것도 다른 풀이가 지수승 이상이었기 때문에, 데이터 만들기도 쉬웠다. 이외에도 우승자 간선 용량 1 안 더하기, 지금 했을 때 가장 이득인 대결부터 하는 그리디 같은 풀이도 랜덤 데이터로 짜를 수 있었다.

정원사 문제

일단 높이를 h-tk 꼴로 처리한다는 아이디어는 떠올리기 쉬운 편이다. 그 다음은 쿼리 문제를 많이 풀어보신 분들이라면 쉬운 편이었을 것 같다. 다만 메모리 제한이 빡빡하기 때문에 공간복잡도가 O(M log M) 이하여야 하고, 상수도 적어야 한다.  그래도 정해는 공간복잡도가 O(M)이라 int만 쓰면 MLE 날 일은 거의 없었다.  큰 식물부터 자르는 풀이가 통과할 수도 있겠다 싶었는데, 실제로 그런 풀이가 있었다.

이 문제는 커팅이 통과할 여지가 조금 있었기 때문에 내가 커팅 코드를 몇 개 만들어보고 TLE나는 데이터를 만드려고 했다.

다행인지 불행인지는 잘 모르겠지만 대회날 잘하시는 분들이 월파 교육을 하고 계셔서 올솔브가 여러 명 나오지는 않았다. ㅋㅋㅋㅋ 

앞으로도 출제를 자주 해보고 싶다.