제 2회 소프트콘 개최 후기

* 이 글은 해당 대회 문제의 풀이에 대한 스포일러를 포함하고 있습니다.

1회 후기에 이어서 2회 후기도 써 본다.

1회때 아쉬웠던 점들을 보완하기 위해 몇 가지 변경 사항이 있었다.

1. 전반적으로 문제의 난이도를 낮추고, 맨 앞에 조금 더 쉬운 문제를 하나 추가하고, 맨 마지막에 조금 어려운 문제를 하나 둬서 9문제로 하는 것으로 변경. 1회의 마지막 두 문제는 블루~퍼플을 겨냥한다고 하기엔 난이도가 너무 높았음

2. 처음에는 서브태스크 대회가 아니었는데, 백준님께서 서브태스크 문제 지원을 추가해주셔서 대회 준비 중간부터 서브태스크 문제 대회로 방향을 바꿨다. 서브 태스크 대회가 가지는 장점이 많다고 생각해서 바꾼 것이었는데... 이에 대한 자세한 사항은 후술.

일단 대회 준비 과정에서 djm03178님, yukariko님, jh05013님이 모두 문제 디스크립션을 상당히 깐깐하게 잘 봐주시는 분들이라 전반적인 문제 설명이 어렵지 않게 잘 이루어진 것 같아서 그 점이 1회 때에 비해 많이 개선되었던 것 같다. 또, 일단 검수자 수가 많아지기도 했고 다들 실력이 뛰어난 분들이라서 각 문제의 풀이 검수도 상당히 철저하게 이뤄젔던 것 같다.

 그리고 문제를 A번부터 I번까지 하나의 스토리에 따라 이어지게 만들었는데 이거 하느라 꽤 힘들었다. 근데 아무도 언급을 안 하더라(...) 눈치를 못 챈건지 재미가 없었던 건지... 약간 아쉬웠던 부분. 괜히 신경썼나 싶기도 하고 ㅋㅋ

2회 소프트콘 문제는 아래 링크에서 풀어 볼 수 있다.

- 대회 문제 목록: https://www.acmicpc.net/category/detail/1898

A. 스승님 찾기

 cnhs2205님이 출제하신 문제. 격자점은 많이 다뤄지는 개념이면서 꽤 재밌는 개념인 것 같다. 이 문제는 다른 격자점 문제랑 비슷하면서도 살짝 다른 점이 좋았다. 약간 수학적인 문제에 가깝긴 하지만 그리디한 종류의 사고 방식과 그 증명(이 방법으로 하면 최소야! 증명은 이렇게 하면 돼!)은 컴퓨터 문제에 많이 쓰여서 소프트콘에 적합하지 않은 문제는 아닌 것 같다.

B. 명상 방해꾼

 djm03178님이 출제하신 문제. 코드포스 등에서 흔히 볼 수 있는 유형인데 초보자는 꽤 풀어볼만한 문제인 것 같다. 다른 문제에서는 볼 수 없는 이 문제만의 성질을 써야하는 문제는 아니어서 살짝 아쉽기는 하다. 하지만 난이도가 적당히 쉬우면서 참신한 문제라는게 어려우면서 참신한 문제보다 만들기가 훨씬 힘들어서.. 충분히 만족스러운 문제.

C. 상자 열기

 내가 출제한 문제. 이진법을 이용한 라벨링은 내가 상당히 좋아하는 개념인데, 이 문제는 그 성질을 잘 이용하고 문제의 특성을 잘 이용해야 해서 개인적으로는 굉장히 마음에 드는 문제였다. 대회 끝나고 나서도 많은 분들이 재밌는 문제였다고 칭찬해주셔서 더 기분이 좋았다.

 이 문제는 회사에서 퇴근하기 직전에 문득 생각이 났다가 다음날 아침에 출근한다고 씻으면서 풀이가 문득 생각이 났다. 처음에 어쩌다 생각하게 됐는지는 까먹었다.

 2회 대회에 가장 먼저 추가되었던 문제였는데 문제가 만들어지고 검수되기까지 텀이 꽤 길었고 사람들마다 난이도 평가가 상이해서(아이디어성 문제라 어려운 사람에겐 굉장히 어렵고 아닌 사람에겐 굉장히 쉽게 느껴졌던 것 같다) 적절한 점수가 얼마냐를 따지기가 힘들었다.

D. 국제 소 줄서기 콘테스트

 내가 출제한 문제. 개인적으로 좋아하는 또 다른 개념중에 하나가 부분합이다. C / D 연달아 내가 좋아하는 개념으로 만든 문제였다. 이 문제는 소끼리 자리 바꾸는 것을 제외한 형태와 완전히 같은 문제가 널리 알려져 있다. 아마 문제를 좀 많이 풀어 본 사람들은 한 번씩은 풀어 봤을 것이다. 

 나도 그런 널리 알려진 문제들 중 몇 개를 풀고 나서, 이 걸 좀 변형해서 수열의 원소들 위치가 계속 바뀌면 어떻게 풀 수 있을까? 를 고민하다가 이 문제를 만들었다. 처음에는 임의의 두 원소끼리 교환하는 문제를 생각했었는데 이 문제는 결국 풀이를 못 떠올렸고(혹시 아시는 분 있으면 가르쳐 주세요) 인접한 둘만 스왑한다고 가정할 경우 독특한 성질이 생기는 것을 발견해서 문제를 변경했다.

 적절한 난이도에 적절한 부분합 활용이라고 생각해서 마음에 드는 문제다.

E. 순간이동 발판

 djm03178님이 출제하신 문제. 다들 의도한 방법과 다른 방법으로 풀었고 생각보다 난이도가 훨씬 높은 문제였어서 당황했던 문제다. 나는 이 문제의 풀이가 발전하는 과정을 모두 봤고, 그래서 그런지 문제가 그렇게 어렵지 않다고 생각했었다. 하지만 현실은 전혀 그렇지 않았고...

검수는 해당 문제가 만들어진 과정을 전혀 모르는 사람이 맡아야 한다는 것을 많이 느낀 문제였다. egcd를 써서 푼 사람들이 많았는데 소프트콘은 이런 수학적인 것을 별로 좋아하지 않기 때문에 이 문제의 정해는 그런 수학적인 지식과는 전혀 상관 없는 풀이였다. 

F. 유물 도둑

 어느날 갑자기 smu201111192님(이하 스무님)이 이 문제 어때요? 근데 저도 풀이는 모르겠어요 라며 들고 오신 문제. 나와 스무님, yukariko님 셋이서 꽤 오랫동안 다양한 종류의 해법을 고민했다. 여러가지 접근 방법들이 논의됐었는데, 최종적으로 나온 풀이는 그 중에 가장 깔끔하고 접근 방법이 재밌다고 생각한 풀이로 정해졌다. 채택된 풀이는 yukariko님이 처음 떠올리셨었다. 

 채택된 풀이는 O(Q(V+E))의 시간 복잡도인데... 그 이후에도 이것보다 더 빠른 풀이는 없을지 한참 고민해봤으나(그 와중에 O(V+E)의 통과되면 안되는 야메 풀이가 통과된다는 것을 발견해서 막았다 ㅋㅋ) 결국 어느 것도 떠올리지 못했다. 혹시 더 좋은 아이디어 있으신 분은 저에게 말씀해주시면 정말 감사할 것 같습니다

G. 모든 결말을 보고 싶어

 djm03178님이 만드신 문제. 처음에는 O(NK^2)을 의도하고 만들어진 문제였는데 내가 O(NK) 해법을 찾아서 정해가 바뀌었다. 이 문제도 상당히 우여곡절이 많았는데, 스무님께서 생각도 못했던 커팅 풀이를 정말 많이 생각하셔서 이 커팅 풀이들 막느라 시간을 엄청나게 썼다. 그 과정에서 문제가 처음 문제에 비해 살짝 지저분해진 것 같아 그 점이 아쉽다.

 내가 생각했던 해법은 다른 트리 DP랑 순회하는 방향이 상당히 달라서 그 접근이 재밌다고 생각했는데, 아쉽게도 오일러 투어로 구간을 펴면 훨씬 쉽게 풀 수 있는 방법이 있었다. 당시까지만 해도 트리를 구간으로 펴서 생각하는 방법에 내가 익숙하지 않았었고, 그래서 그런게 가능할 거라곤 생각을 못 했었다. 내가 떠올렸던 정해가 더 재밌는 것 같은데 그게 속도도 더 느리고 제일 좋은 방법은 아니었어서 그 점이 아쉽다.

H. 마법 목걸이

 ainch96 님이 처음 아이디어를 가져오신 문제. 원래 문제는 원형이 아니라 일자로 펴진 구간이었고, 이 구간은 그냥 그리디한 풀이로 풀 수 있는 쉬운 문제다. 근데 너무 쉽고 이 문제를 가져오신 시점이 이미 A,B,C 자리가 차 있던 상황이라 문제를 좀 더 발전시켜보자는 이야기가 나왔다. 그 때 cnhs2205님이 일자가 아니라 원형이면 어떨까요? 라는 아이디어를 내셨고 이건 풀기가 좀 어려워서 고민을 해 보게 됐다.

 그래서 나온 풀이는 꽤 재밌어서 만족을 했었는데, 안타깝게도 절대 막을 수 없는 랜덤 타임 커팅 풀이가 존재했다. 이 풀이도 어느 정도는 고민이 필요하긴 하지만 원래 우리가 생각했던 추가적으로 발견해야 하는 성질 하나를 발견하지 않아도 통과가 가능했고, 문제 특성상 그 커팅을 막을 수 있는 방법이 없었다. 반례를 엄청 고민했었는데 결국 불가능하다는 결론에 도달...

 어쩔 수 없이 문제를 조금 바꿔서 커팅을 쓸 수 없게 했는데 그것 때문에 문제가 살짝 어색해졌다는 점이 아쉽다. 그리고 잘하시는 분들이 대회 중에 우리가 생각한 것보다 훨씬 쉽게 푸는 것을 보니, 상대적으로 널리 알려진 풀이를 쓰는 문제인 것 같아 그 점도 좀 아쉬웠다.

I. 팀 빌딩

 내가 출제한 문제. 유니온 파인드 역시 내가 굉장히 좋아하는 개념인데, 여기에 이미 합쳐진 집합을 분리하는 연산을 추가할 수 있을까?를 고민하는 과정에서 만들어진 문제였다. 구현이 상당히 까다로워서 잘 생각하지 않으면 풀기가 어려운 문제다. 문제에 필요한 아이디어 접근은 생각보다 어렵지 않은데 그걸 제대로 깔끔하게 구현하는 게 어려운 문제. 나도 문제를 생각하고 구현하는 과정에서 한참을 헤맸던 것 같다.

 안타까웠던 점은 tncks0121님이 대회중에 데이터를 뚫은 것... 뚫고 나서 대회 질문으로 손수 TLE가 나는 데이터까지 말씀해 주셨다. 그 때의 왠지 모를 굴욕감이란.. 데이터를 잘 만들었다고 생각했는데 많이 부족했다. 이 정도면 되겠지 하고 좀 안일하게 생각했던 게 문제였던 것 같다. union-find 연산과 관련한 카운터 케이스를 내가 잘 몰랐던 점도 컸던 듯.

 어쨌든 결과적으로는 1회때 보다 좀 더 완성도가 높고 내가 원했던 방향성에 가까운 대회가 되지 않았나 싶다. 여전히 아쉬운 점들과 부족했던 점들이 좀 있지만...

 한 가지 특히 아쉬웠던 것은 중간부터 서브태스크 대회로 바꿔서 고민하게 되면서 약간 생각하지 못한 완성도가 낮은 부분들이 생기게 되었다는 점이다. 특히 F번은 섭태 1을 통과하면 안되는 코드가 반례가 섭태2에만 들어가있는 바람에 섭태 1은 통과하게 되어버리는 문제가 있었고, A번도 대회 초반에 비슷한 문제가 있었다. H번은 서브태스크 인풋 범위 설정하는 과정에서 인풋 범위를 잘못 적는 바람에 문제가 생기기도 했고...

좀 더 일정을 여유롭게 잡고 준비해야 했었는데 욕심 때문에 급하게 서브태스크를 추가하면서 정말 많은 문제점이 생겼던 것 같다. 의도는 문제들을 최대한 서브태스크로 나눠서 조금 실력이 부족하더라도 대회 시간동안 쭉 문제들을 풀어볼 수 있게 하는게 목적이었는데 막상 사람들은 서브태스크 단위로 문제를 푸는 건 잘 시도하지도 않았고... 

BOJ에서 서브태스크 문제를 걸면 점수를 높게 받아야하는 큰 이유가 없는 경우 서브태스크만 맞추면 내 프로필에서 틀린 문제로 남는게 보기 싫기 때문에 서브태스크를 시도하지 않는 사람이 많다는 것을 너무 간과했었다. 그 외에도 일단 서브태스크를 푸는 것에 사람들이 별로 관심이 없는 것 같기도 하고...

모든 서브태스크에 대해 가능한 풀이를 준비하고 각각 제한 설정, 점수 정하기 하느라 정말 신경을 많이 썼는데 그게 별 의미가 없었던 것 같아서 많이 아쉬웠다. 

그래서 2회가 끝나고 시간도 꽤 많이 흘렀는데... 3회는 어떻게 할지 아직도 고민 중이다. 일단은 BOJ가 아니라 직접 만든 온라인 저지 사이트에서 대회를 개최하고 싶은데 문제는 사이트를 만들 시간이 없고(...) 그래서 3회 준비도 계속 요원한 상황. 3회 대회는 올림피아드 류처럼 긴 시간동안 적은 개수의 질좋은 문제를 푸는 대회로 하고 싶다는 생각도 좀 있는데(3시간 4문제 정도의) 이런 방향성에 대한 고민도 많이 되고...

언젠가는 열리긴 하겠지만 3회는 아마 열리려면 시간이 좀 더 많이 필요할 것 같다. 어쨌건 1,2회를 하면서 배운 걸 바탕으로 3회는 더 발전된 대회가 되기를!!!