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

월간 향유회는 평소에는 온라인으로 열리는 대회인데, 이번에는 오프라인 대회로 열린다고 해서 참여했습니다.

원래는 하는 줄도 몰랐고 한다고 해도 개강 전날이라 안 갈 것 같았는데 대회 장소가 무려 집에서 걸어서 7분 이길래 이건 가야겠다고 생각했습니다. 인생에서 가장 가까운 약속장소ㅋㅋㅋㅋㅋ

그리고 대회 당일까지도 까먹고 있다가 유틸형이 대회장 간다고 해서 1시간 전에 기억을 되찾았습니다.

대회 1시간 전에 되찾은 기억

그런데 이번주 내내 하고 있던 데이터 크롤링하는 알바가 안 끝나서, 아침부터 계속 돌리다가 1시 40분에(!) 간신히 다 끝내고 대회장으로 향했습니다.

늦을까봐 좀 빠르게 걸었더니 5분 만에 도착했습니다. 아이 신나😀

안면이 있던 kiwiyou, nflight11, utilforever 님의 도움을 받아 빠르게 대회 아이디를 받고, 멀티탭을 받고, 빈 A4 지까지 받고 로그인했더니 59분이 되었습니다.

 

대회 타임라인

대회는 총 10문제가 출제되었고, 따로 설명이 어디 있었는지는 모르겠지만 난이도 순으로 배치된 것 같았습니다.

 

문제 풀이 스포일러가 포함되어 있습니다.

 

0:01 A WA (-1)

0:02 A AC (+1)

심플 브론즈 문제인데, 쿼리마다 한번씩 출력씩인 줄 알고 한번 틀렸습니다. 지문을 잘 읽자

 

0:04 B AC (+)

퍼솔이 나왔길래 믿고 냈습니다. 세 변의 길이가 모두 다르다는 조건이 없으면 아주 어려워진다고 하네요.

cout << set.size() != 3n

 

0:07 C AC (+)

펠린드롬을 구해야 하나 10초 정도 고민했는데, C번이라 그런 거 몰라도 될 것 같았고 잠시 고민하니 될 것 같아서 기다리다가 마찬가지로 퍼솔 찍히는 거 보고 냈습니다.

cout << 26 * (n+1) - n

 

0:16 D AC (+) (First Solve)

똑같은 문제를 풀어본 기억이 분명히 있는데, 무슨 문제인지 백준에서 못 찾았습니다. 

21개만 확인하면 되는데, 대회 중에는 잘 모르겠어서 넉넉하게 30C5개 확인했습니다.

구현이 금방 되는 문제는 아니라서 그런지 풀이를 1초 만에 안 덕분에 퍼솔을 먹었습니다.

여기까지 풀고 오늘 감이 좋은 것 같다고 생각했습니다. 어제 SCPC는 말아먹어놓고ㅋㅋㅋ SCPC때 잘하지

 

0:22 E AC (+)

조금 끄적여버려 보니까 (0,0,4)가 되는 걸 확인했고, 그대로 구현하다가 (0,0,2) 도 되는 걸 확인하고 수정했습니다.

다 구현하기 전에 알아낸 덕분에 구현이 조금 더 깔끔해졌습니다.

A번 페널티 때문에 1등을 못 따고 있었는데, 여기까지 짰을 때 유일한 5 솔이길래 신났습니다.

대회에서 1등을 찍어보다니

0:37 F WA (-1)

0:40 F WA (-2)

F와 G를 둘 다 열어놓고 고민했는데 G는 괴랄한 스도쿠가 박혀있길래 F부터 풀기로 했습니다.

처음에는 만들 수 있는 최대 선분의 길이만 구하면 되는 문제인 줄 알고 냅색 딸깍하는 코드를 짰는데 틀렸습니다.

다시 보니 최솟값도 알아야 하길래 최소 선분의 길이도 구해서 냈는데 한번 더 틀렸습니다.

사풀이 몇 개 더 떠올랐지만 맞는지 모르겠어서 스킵했습니다.

 

H~J까지 남은 문제를 전부 열어봤는데, H는 재밌어 보이는 컨스트럭티브 / I는 씹덕 조합론 / J는 게임이론 문제로 보였습니다.

"마지막 문제가 게임이론이라고?" 를 외치면서 J로 바로 스킵했습니다. (퍼솔을 하나 더 먹고 싶었어요)

 

1:19 J WA (-1)

1:27 J WA (-2)

1:29 J AC (+2) (First Solve)

게임이론 문제는 작은 케이스에서 먼저 손으로 해보고, 하나씩 늘려가 보면서 규칙을 찾아보는 게 유효한 전략인 경우가 매우 많습니다. 이 문제에서는 토끼굴이 1개인 경우 -> 2개인데 하나가 0 -> 2개인데 하나가 1 -> 2개인 경우 일반화 -> 3개인 경우고 두 개가 0 -> 3개이고 하나가 0 -> 3개이고 1이 2개인 경우까지 손으로 해보니까 규칙이 나왔습니다.

 

첫 번째 중요한 관찰은 남은 굴이 0과 1만 있을 때, 0이 짝수개 있으면 현재 턴인 사람이 이기고 홀수개 있으면 진다는 것입니다. 

이때 1이 몇 개 있는지는 상관없어 보였습니다.

 

이 관찰을 바탕으로, 입력에 0은 없기 때문에 1이 아닌 것들을 전부 0이나 1로 잘 바꿔주면 될 것 같다는 결론이 나왔습니다.

스프라그-그런디 정리를 알고 있다면, 모든 숫자의 xor값이 0이 아닐 때 한 숫자를 줄여서 항상 0으로 바꿀 수 있다는 것을 직관적으로 알 수 있습니다. (다시 말해, xor만 있는 게임의 그런디 넘버는 모든 숫자의 xor값입니다.)

이 정리를 모르더라도 가장 큰 수에서 적당한 값을 빼서 전체 숫자의 xor을 0으로 바꿀 수 있다는 것을 (아마도?) 증명할 수 있는 것 같습니다.

 

여기까지 생각한 다음에 1 이상인 수가 짝수개일 때와 홀수개일 때를 분리해서, 한 경우는 xor이 0이면 승리하고 다른 경우는 xor이 0이 아니면 승리한다까지 찾아냈습니다.

여기까지 생각하고 구현했는데 WA를 받았습니다.

다시 생각해 보니 xor이 0이면 승리하는 경우에, 0이 아니더라도 내가 0으로 만들지만 않으면 승리할 수 있다는 것을 발견했습니다. 이걸 어떻게 할 수 있을까 고민했는데 왠지 xor이 1만 아니라면 항상 이길 수 있을 것 같았고 구현했더니 맞았습니다.

 

이번 대회의 프리즈 기준이 "6솔하면 개인 프리즈" 였는데, F를 못 풀고 J를 풀어서 프리즈를 박는 이상한 사람이 되었습니다. ㅋㅋ

 

1:52 G WA (-1)

1:58 G WA (-2)

1:59 G AC (+2)

 

H를 먼저 잡았는데, H는 "높이가 5의 배수인 노드를 루트와 전부 연결하면 된다" 까지는 떠올렸는데 그게 n/5개보다 많을 수 있어서, 어떻게 이걸 해결할지 몇 가지 아이디어를 고민하다가 유기했습니다.

G를 다시 읽어보니 마지막 두 줄만 보면 될 것 같다는 핵심 관찰이 나왔고, 여기서 사이클만 잘 찾아주면 된다는 결론이 나왔습니다. 사이클을 제대로 못 찾아서 1번, N^2 <= 1600인데 max = 1000으로 잡았다가 한번 더 틀리고 "문제를 잘 읽자2" 하고 맞았습니다.

 

 

2:24 I WA (-1)

2:27 I WA (-2)

2:29 I WA (-3)

2:34 I TLE (-4)

2:35 I CE

2:35 I TLE (-5)

2:37 I AC (+5)

 

남은 문제들 중에 I번이 제가 팀연습 때마다 잡는 대충 조합론 섞은 dp 문제였기 때문에, 어차피 이벤트 대회니까 I번을 고민해 보기로 했습니다.

cologue님이 설명해 주신 풀이는 사실 잘 이해하지 못해서 같은 풀이인지 아닌지 모르겠습니다.

제 풀이는 다음과 같습니다.

1. 가장 큰 숫자를 전부 배치합니다.  
2. 두 번째로 큰 숫자를 전부 배치합니다. 이때 가능한 상태는 두 가지 중 하나인데, "앞서 배치한 숫자들의 가장 앞에 하나라도 놓을 것인지 놓지 않을 것인지" 입니다.
   만약 가장 앞에 하나라도 놓게 된다면 문제에서 정의한 "가증스러움" 이 1 증가하게 되고, 하나도 놓지 않는다면 증가하지 않습니다.
   가장 큰 숫자의 개수가 a개, 두 번째로 큰 숫자의 개수가 b개라고 했을 때 두 번째 숫자를 배치하는 경우의 수는 (a+1) H b 입니다. 그리고 이 중에서 가장 앞에 하나도 놓지 않는 경우의 수는 a H b 이므로, 가장 앞에 하나라도 놓는 경우의 수는 (a+1) H b - a H b 입니다.
3. 이 과정을 반복하여, x번째로 큰 수까지 배치했을 때 x+1번째로 큰 수를 배치하면서 가증스러움을 1 증가시키거나 증가시키지 않는 각 경우의 수를 구할 수 있습니다.
4. 따라서 dp[n][k] = n번째로 큰 수까지 배치했고, 가증스러움이 k인 경우의 수 로 정의하면 dp table을 O(nk) 로 업데이트 할 수 있습니다.
5. 문제에서 구해야 하는 답은 dp[n][0] + dp[n][1] + ... + dp[n][k] 입니다.

mod 연산을 몇 군데 빼먹어서 세 번 틀리고 (중간에 음수가 되는 부분이 있었는데 제대로 처리를 안했습니다.), 고쳤더니 TLE가 나서 nHr 구하는 코드를 고쳤습니다.

처음에는 divmod ((n+r-1)!, (n-1)! * r!) 으로 짰는데 이러면 시간복잡도에 logn이 붙습니다. 문제의 조건을 잘 생각해 보면 nHr은 최대 n+r <= 5000까지만 들어오기 때문에, 5000^2의 테이블을 미리 만들어주면 전처리 5000^2 + O(1) 시간에 nHr을 구할 수 있습니다.  

 

~3:00

아까 잠깐 고민했던 100억 번의 연산을 잘 커팅하는 F번 코드를 짰는데, 3시간 00분 05초에 완성해서 제출은 못했습니다. 그런데 어차피 TLE였을 거라 아쉽지는 않습니다.

 

대회 결과

대회 결과

 

중간에 잠깐 1등까지 찍었지만 후반에 페널티를 많이 먹었고, 10솔은 몰라도 9문제에 제출하신 분이 꽤 많아서 1등은 못할 것이라고 생각했고 4등으로 마무리했습니다.

 

10등까지 중에 저만 F를 틀렸네요 저거 왜 나만 못풀어~~~~

 

단체사진 (출처 : https://owsjdhdusiwi.tistory.com/22)

 

사실 대회가 있다는 걸 까먹고 뒤에 저녁 약속을 잡아둬서 슼보 공개 전에 갈까 고민했는데, 예상보다 많은 문제를 풀어서 기분이 좋아져 그냥 행사 끝까지 남아있었습니다.

단체사진을 찍는데 A4지에 1등~3등까지 적어서 들고 박제하는 걸 보면서 '4등이라 다행이다' 라고 생각했습니다. 휴 나는 박제 안 당했다~

 

월향이 따로 후원받는 곳도 없다고 알고 있는데 오프라인 행사 기획해 주신 분들 감사드립니다 :)

 

티셔츠 디자인하신 분 누가 하셨는지는 모르지만 평소에 입고 다닐 수 있는 디자인으로 만들어주셔서 한번 더 감사드립니다.