월간 향유회 8월 오프 대회 후기

대회 끝나고 찍은 사진이다.

내가 누군지 굳이 말하지 않아도, 혼자 어색하게 사진을 찍은 사람 한 명을 고르면 바로 찾을 수 있다.

PS를 제대로 시작한 건 올해 2024년인 거 같고, 나에게 있어 첫 오프라인 대회였기에 의의가 컸던 거 같다.

알고리즘 그 자체를 정말 좋아하는 나지만, Competitive Programming에 쥐약인 스타일이라 그동안 대회에서 골드 이상 문제를 푼 적이 없었는데, (기존에 푼 가장 어려운 문제는 미적확통컵에서 푼 실버2 문제였다.)
난이도가 매겨지고 보니 골드5를 2문제나 풀었어서 놀랐던 기억이 있다.

현장에서 꼴지(19위)를 하기도 했고, 내가 푼 3문제 (A, C, E) 모두 코드가 굉장히 짧은 편이었기에 그냥 거저 주는 문제만 풀었다 생각했고, 0솔이 아니라는 것에 의의를 두고 있었다. (18등을 하신 wapas님이 루비니까 나는 루비랑 비벼볼 만한 실력이다. 라는 어이없는 자기위로를 하기도 했다.)

A는 정말 거저 주는 문제가 맞았지만, C랑 E는 그렇지 않았던 것 같다.

문제별 후기

A: 다음 달에 만나요

정말 거저 주는 문제. 브론즈3 난이도라는데 솔직히 브론즈3은 너무 고평가라고 본다....

B: 네모의 꿈

기하 문제이고, 출제진들 중 한 분이 두 삼각형을 붙였는데 삼각형이 되는 반례를 발견했다고 하셔서 놀랐던 기억이 있다.

티어는 실버4가 나왔다.

반례를 직접 찾지는 못했지만, 나는 해당 반례가 존재할 것을 현장에서 예측했고, 예외 처리를 어떻게 해줘야 할 지 떠올리지 못해 그냥 넘겼다. SciOI2023 때 실버5에서 막혔던 거에 비하면 실버4에서 막힌 건 봐줄 만 한 것 같다...

C: 아보와 킨텍스

포켓몬스터 아보를 떠올릴 수 있지만, 그 아보 아니다... 아이보리님이다 (여담이지만, 내 동생이 가장 좋아하는 포켓몬이 아보다.)

O(1) 풀이가 존재한다. 테스트 케이스 2개를 보고 O(1) 풀이를 떠올리긴 했는데, 반례가 있을 거 같아 보류했다.
단어를 첫 글자부터 마지막 글자까지 탐색하면서 두 글자가 다르다면 26을, 아니라면 25를 더해나가는 풀이를 떠올렸으나, '틀렸습니다' 를 받았다.

'aaaaaa' 같은 경우에서 177이 나오기 때문인데, 맨 앞자리에 a를 붙이든 마지막 자리에 a를 붙이든 똑같다는 것을 깨달았다. 답은 176이다.

그래서 이 문제에 대해 경우의 수를 엄밀하게 증명해야 정해를 찾을 수 있을 것이라 판단, 풀이를 포기하고 에디토리얼을 보기로 했다.

그러나 176. 이게 내가 아까 테케 보고 유추한 O(1) 풀이로도 나오는 값이었다... 그냥 넘어가기엔 뭔가 걸리는 점이 있었다.

문자열의 조성과 상관없이 길이만으로 답이 정해진다는 건 절대 말이 안 된다 생각했음에도, 뭔가 수상했다.

고민하다가 예능 찍는 셈 치고 그냥 O(1) 풀이를 내봤는데 '맞았습니다!!' 가 나와서 황당했다....

아주 좋은 문제라 생각했으며, 엄밀한 증명을 해보고 싶고, 나중에 올릴 것 같다.

D: 꿀잼 루비 문제

사실 제목만 봤을 때 '아니 D번에서 루비를 낸다고??' 싶었는데 막상 문제를 보니 루비 난이도로 낸 문제는 아닌 거 같았다.

K<=5 라는 알고리즘 문제에서 정말 보기 힘든
(시간 복잡도가 매우 큰 외판원 순회 문제조차도, N<=16이다.) 제한 조건을 보고 빡구현+완탐으로 뚫을 수 있겠다 생각은 했는데, 그러기 싫었다.

구현이 귀찮았던 것도 부정할 수는 없지만, 더 깔끔한 풀이가 분명 존재할 것이라 생각했고, 이 문제 자체가 너무 잘 만든 문제라 느꼈기 때문이다.

상하좌우 이웃한 칸과 연관되어 있다는 점에서
커넥션 프로파일 DP? 를 잠깐 떠올렸으나 나는 저 알고리즘을 모르기 때문에 넘어갔다.

다이아3인 싼 비용 문제가 커넥션 프로파일 DP 기본 문제인데, D번에 다이아 문제를 넣었을 거 같지도 않았다.

근데 문제가 너무 DP같이 생겨서... DP 접근법을 포기하긴 싫었다. 백트래킹으로도 분명 될 거 같았는데
나는 티어가 골드1임에도 실버 백트래킹 문제를 힘겨워하는 사람이라 백트래킹은 선택지에 없었다.

배열의 행, 열 인덱스 합을 이용하거나, 택시 거리로 DP식을 정의하는 등 다양한 시도를 해보았으나 아무 성과 없이 2시간이 지났다.

E: Knight crusing

애드혹 문제. 옛날에 솔브닥 상태메시지에 애드혹원툴이라 써놨을 정도로, 애드혹은 그나마 내가 잘 하는 파트다. 나이트의 이동 횟수에 제한이 없다는 점을 인식했고, 2번의 이동만으로 x,y,z 좌표 중 원하는 하나를 2만큼 증가시킬 수 있다는 사실을 알아냈다.

여러 이동을 조합해봤지만 좌표를 홀수만큼 증가시키는 건 불가능했다.

그래서 가장 작은 짝수인 2가 최소 단위라고 판단, 코드를 제출했고 '맞았습니다!!' 를 받았다. C번은 나름 고민을 했더라도, 이건 너무 스무스하게 풀린 문제라 솔직히 브론즈1~실버4 정도로 티어가 나올 줄 알았는데 골드5여서 놀랐다. (다만, 내가 애드혹을 지나치게 잘 해서 그런지 애드혹 문제들의 티어를 저평가하는 경향이 있는 거 같다는 생각을 예전에도 하긴 했다.)

물론 내가 자력으로 푼 애드혹 최고 티어는 골드2이다.

다이아 애드혹 문제(특히 '청소기 마술' 문제는 내가 가장 맘에 들어하는 문제들 중 하나이다. 언젠간 꼭 풀어보고 싶다.) 를 풀어보고 싶지만, 아직 그 정도 실력은 아닌 거 같다... 당장 골드1인 '흰색으로 만들기' 문제도 풀이가 안 떠오르는 걸 보면 말이다.

근데 원래 애드혹이란 게 배워서 실력이 느는 알고리즘은 아닌 거 같아서 그냥 고민을 계속 해볼 것 같다.

F: 선분의 합집합

이 문제를 볼 때 이미 대회 시간이 30분도 안 남은 상태였다, 뒷 문제들을 봤지만 내가 건드릴 문제들은 아니어 보였고, 이 문제를 그나마 고민했다.

1차원에서 선분의 합집합을 구하는 문제이다. 1차원이라는 걸 봤다면 스위핑을 떠올렸겠지만, (내가 스위핑을 잘 못 하는 것과는 별개로) 1차원을 3차원으로 보는 어이 없는 실수를 했다.

'3차원 막대기 연결하기' 라는 기하+그리디 문제를 스스로 푼 적이 있는데, 그걸 응용하면 될 거 같았다.

그런데 데이터가 꽤 큰 거 같았다. 게다가 막대기의 길이만 고려하는 게 아니고 가격도 고려해야 했다.

순간 배낭 문제가 떠올랐지만 데이터 범위를 보니 그건 아니었다.

해시맵을 쓸까라는 생각도 해봤으나, 가격의 합이 정확히 어떤 수가 되는 막대기들을 어떻게 고를 지 떠오르지 않았다. 패스했다.

G: 아이보리와 함께 푸는 스도쿠

문제를 다 읽기도 전에 넘어갔다.
나는 스도쿠 문제가 싫다... 백트래킹을 지나치게 못해서 그런가 보다.

H: 코코아와 마법사의 돌

F 버리고 마지막으로 고민이라도 해 본 문제.
트리+애드혹 일 거라 생각했다.

트리의 지름을 일단 구해야 간선들을 추가하면서 지름을
1/2로 줄여나가는 그리디를 시도해 볼 거 같았는데,
트리의 지름 문제를 풀었지만 구현 방법을 까먹었다!

그래서 포기하고 넘어갔다. 근데 이 문제, 애드혹이 아니었다... 비둘기집 원리를 써야 하는 문제였다.
풀이를 들으면서 감탄했다. 나중에 풀어볼 것 같다.

I: 순열 제작의 달인

'배열 제작의 달인' 문제가 티어가 상당히 높은 편이기도 했고, 문제 비주얼도 까다로워 보여서 루비 난이도일 거라 생각하고 그냥 넘어갔다.

J: 래빗 홀

게임 이론 문젠데, 시간이 없어서 이 문제는 대회 중에 읽어보지도 못했다...

생각보다 문제 퀄리티가 많이 좋았다. 7월 대회에 나온 삼색정리도 역대급이었는데 (물론 난 아직도 못 풀었다.) 이번에도 그에 뒤지지 않는다. 아보와 킨텍스, 코코아와 마법사의 돌 문제는 클래스에 넣어도 될 거 같다.

아직 8월 월향 뱃지를 못 받았지만 곧 들어오겠지 싶다.

전공이 바쁘고, 독서모임과 블록체인 학회 등 여러 이유로 인해 2학기 동안은 알고리즘을 거의 못 할 거 같아 아쉽다.

그래도 9월~12월 월간 향유회 모두 참석할 예정이다!

끝

aliens트릭을 이해하는 그날까지.