많은 양의 셋 기록

방학이 되었습니다. 사실 방학이 된지 약 20일이 되었습니다. 중간고사 이후로 블로그를 거의 안 올렸는데, 약간 과장하자면 블로그를 쓸 시간에 PS만 했습니다.

글을 쓰는 시점을 기준 내일이 첫 SCPC 1차, 모레가 첫 UCPC 예선, 다음 주는 조합론 알고리즘 여름학교가 있습니다. 중간에 정리를 할 만한 때가 있다면 지금이 최적의 시기인 것 같습니다. 6월 27일부터 7월 10일까지 돌았던 다양한 버추얼 대회들을 짤막하게 리뷰합니다.

6월 27일

2024 ICPC Japan Online First-Round (요코하마 예선) - 5+208/9 = #32

낮에 요코하마 예선을 돌았습니다. 일본 예선은 한국과 다르게 난이도가 정렬되어 있습니다. 문제 스타일도 서울이나 요코하마 본선의 그것과는 조금 다른 느낌이었는데, 약간 ABC를 치는 느낌이 들었던 것 같습니다.

해결한 가장 어려운 문제는 P5, 해결하지 못한 가장 쉬운 문제는 P2입니다. P5에도 꽤나 오랜 시간을 박았고, P2는 풀었어야 하는 문제인데 못 풀어서 아쉽습니다.

난이도 정렬이 되어 있는 팀셋은 색다른 것 같습니다. 구현머신을 앉혀놓고 앞 3문제 정도를 던져준 뒤 남은 2명이 그 뒤의 문제를 발상하는 초반 전략을 사용할 수 있을 것 같습니다.

---

사실 그 뒤에 디미고 대회를 돌려고 했는데, 마침 OMC가 있다는 사실을 듣고 몇 문제 풀다가 넘어갔습니다.

OMC254 - Rated 4위

밤에 OMC254를 레이티드로 돌았습니다. 모든 문제를 풀었습니다. 운이 좋았던 것 같습니다.

올림피아드 수학을 작년 OMC/MathDash 입문 이후로 처음 잡아봤고, 이렇게 좋은 퍼포가 나올 거라 생각하지 못했어서, 매우 만족합니다.

6월 28일

2023 ICPC Northern Eurasia Regional - 7+1099/12 = #32

연세대 25학번의 친구 둘을 납치해서 모르고리즘 동방에서 셋을 돌았습니다. 결과가 썩 나쁘지 않았는데, 나머지 두 팀원들이 생각보다 문제를 매우 잘 풀어줬습니다.

평소에 혼자 셋을 돌면 어려운 문제를 잡을 시간이 없어서 셋을 돌기가 약간 아깝다, 혹은 어려운 문제 푸는 실력이 오르지 않는 것 같다는 생각이 많이 들었습니다. 이번에는 확실히 어려운 문제에 투자할 수 있는 시간이 길었고, 그래서 D5 하나를 풀어 맞추고 하나의 풀이를 냈습니다.

다만 쉬운 문제를 푸는 데 시간이 오래 걸린 것은 여전하긴 했습니다. 정확히는 쉬운 문제들에 패널티를 너무 많이 쌓았습니다. 그래서 7솔이라기에는 크고 아름다운 1099라는 패널티응가로 7솔 최하위권입니다.

풀지 못한 D5는 어렵지 않게 업솔빙했습니다. 앞의 문제들이 한 30분만 빨리 풀렸다면 매우 높은 확률로 풀어냈을 것 같습니다.

CF Round 1012 Div1

친구 추가가 되어 있는 한국인의 91%가 음델타를 받은, 그중 70%가 70 이상의 큰 음델타를 받은 무시무시한 셋입니다.

B와 C가 둘 다 2분할되어 있는 셋이었고, 체감상 난이도는 A<<B1<=C1<<B2였습니다. 운이 좋게 빠르게 B2를 제끼고 C1을 빠르게 본 덕에 나쁘지 않은 퍼포를 받아, 퍼포는 정확히 2400입니다.

---

29일에는 놀았습니다.

6월 30일

CF Round 875 Div1

B에서 4번 틀려서 폭망할 뻔했지만, C번의 해싱 쌀먹을 잘 받아먹어서 퍼포먼스에 거품이 낀 느낌입니다.

B번은 제 풀이를 기준으로 시복과 공복을 모두 크게 쓰는데 (둘다 선형루트) 선형루트가 되는 변수만 32비트로, 나머지 변수는 64비트로 선언해주어야 하는 문제였습니다. 저는 32비트와 64비트를 섞어 쓰는 것에 별로 익숙하지 않기에 약간 애먹었습니다.

C는 누적 XOR 해싱으로 딸깍이 가능한 문제였습니다. 저는 해싱에도 익숙하지 않은데, 며칠 전에 해싱을 쓴 기록이 있어 어쩌다 보니 약간의 운빨으로 풀었습니다.

결론적으로 퍼포는 2465 정도를 띄웠습니다. 사실상 고점입니다.

2024 ICPC BAPC

12문제 언저리가 나오는 ICPC 형식의 세트 중에서 난이도가 낮은 것으로 유명한 세트입니다. 혼자 돌기에도 꽤 좋은 세트인 듯합니다.

이 세트에서 가져갈 만한 takeaway로, 읽고 처음으로 풀만하다고 느끼는 문제가 사실 가장 쉬운 문제가 아닐 수도 있다는 점이 있습니다. 저는 A번을 읽고 짤 수 있을 것 같아서 바로 짰는데, 사실 가장 쉬운 문제는 J였기에 패널티를 조금 먹었습니다. (대신 A번 본대회 기준 퍼솔을 가져갔습니다.) J를 풀고 B부터 읽는데 B도 보였고, 근데 B는 짜는 데 40분 정도 걸렸습니다. B를 풀고 나니까 B는 안 풀려 있고 G가 쭈루룩 풀려 있었습니다. 바로 G를 짰고 15분 밖에 안 걸렸습니다. 이런 느낌의 패널티가 많이 박혔습니다. 물론 세 명이서 돌면 이런 식으로 패널티를 쌓을 일은 많이 없기 때문에 괜찮은가 싶긴 합니다.

그리고, 그냥 전체적으로 이상한 패널티를 많이 쌓았습니다. 그냥 깔끔하게 구현하는 것을 전체적으로 못 하는 것 같습니다.

해결한 가장 어려운 것은 P2, 해결 못 한 가장 쉬운 것은 P3입니다. 어렵지 않은 문제의 물량이 많은 세트였기에 능지가 부족하지는 않다고 생각했습니다.

UCPC 2023 예선

40기의 두 친구를 데리고 돌았습니다. G와 J를 제외한 문제를 풀었고, 결과는 9+794/11 = #16 입니다. 저는 B, E, F, K를 풀었습니다. K는 그냥 쉬운 문제였고, B, E, F는 다 생각해 볼만한 문제였습니다.

• F는 ICQT 2023 D번과 문제 생김새가 비슷했습니다. 그래서 발상을 그리디하게 (ICQT23D와 비슷한 방향으로) 했고 얼마 안 걸렸습니다.
• B는 재미있는 작큰 문제였습니다.
• E는 어려운 수학 문제였습니다. 1시간 동안 이것만 잡고 있었고, 대회가 끝나기 10분 정도 전에 풀었던 것 같습니다. 기분이 매우 좋았습니다. 패널티를 그렇게 많이 쌓은 것 같지 않았는데 9솔브 중 꼴등입니다. 확실히 패널티 덜 쌓는 연습이 많이 필요하다는 것을 느낍니다.

7월 1일

JOI 2024

를 돌았는데, 백준의 서버 상태가 영 좋지 못해서 채점을 받지 못하는 이슈로 인해 좀 거시기했습니다. 대충 쉬운 골플급의 문제임이 자명한 1번과 2번을 풀고 나서 P1의 3번 대신 D2의 4번에 가서 50점 언저리를 긁었습니다.

4번의 구현에서 많이 절(었고 백준 서버와 열심히 싸웠)어서 3번에는 1시간 정도를 투자할 수 있는 상황이었습니다만, 그냥 힘들어서 접었습니다.

CF Round 1034 Div3

그냥 그런 대회가 있길래 돌았습니다. 한 번도 안 틀리고 올솔을 했습니다. 아마 딥3 라이브 올솔은 처음 한 것 같습니다.

tralalero_tralala_ 한테 졌습니다.

7월 2일

2024 ICPC Latin American Championship (LAC)

꽤나 어려웠고 꽤나 퀄리티가 좋았습니다. 그래도 이름이 라틴아메리카 슈퍼리저널의 ^챔피언십^이라고, 맛이 썩 좋습니다.

초반 난이도커브가 급격하게 올라갔고, 그래서 혼자 하는 것치고 플중~플상다하를 많이 건드릴 수 있다는 점이 좋았습니다. 다만 문제가 있다면, 제 퍼포가 심각하게 낮았습니다! 이상한 구현 미스에 걸려서 1시간 정도를 박았고, 백준에서 돌아가지만 코포에서는 돌지 않는 요상한 상수 커팅을 해결하겠다고 또 1시간 정도를 박았습니다. (빠른 입출력을 긁어오니 5배 빨라져서 맞았습니다.) 결론적으로 5시간 대회를 한 3시간 친 느낌입니다.

C가 난이도가 높은 것치고 많이 풀렸는데, 알고 보니 이분매칭 문제였습니다. OI에는 플로우가 안 나오다보니 (욪즘엔 대놓고 최대 유량을 내도 된다고 하던데 진짜 나올 지는 잘 모르겠고요) 유량과 관련된 모든 토픽에 익숙하지 않은데, 유량을 좀 공부해 둬야겠습니다.

2023 ICPC Jakarta Regional

UCPC 2023 예선을 돌았던 친구들을 불러 또 돌았습니다. 전체적으로 잘 했습니다.

한 명이 D를 푼 기록이 있는데 마침 셋이 13제라서 12문제를 푼다고 생각하고 돌았습니다. 어차피 대회 시간 중에 D를 풀지는 않았을 것 같습니다.

처음에 FGHI를 읽었는데 풀만해보이는 것이 없었습니다. M이 쉬울 것 같은데 안 풀린다는 말을 듣고 건너가서 쌀먹하고, C로 넘어가서 1시간 정도 보다가 하늘에서 뚝떨어진 관찰을 주워다 먹어서 1트했고, 이것저것 보다가 B가 보여서 1트했습니다. 그러고 나니 J가 남았는데, 세 명이서 거의 1시간 내내 J만 봤지만 보이지 않았습니다. 그러다가 20분 남은 시점에서 누가 풀이를 냈다면서 막 구현하길래, 기다려봤더니 3분 남기고 TLE를 띄웠습니다. 그런데 사실 백준에 내면 맞는 솔루션이었습니다.

코드포스 서버는 확실히 무언가 갑자기 느려지는 트리거가 있나 봅니다. J를 못 푼 기준으로는 8솔브 11등, 풀었으면 9솔브 6등입니다.

그건 그렇고, 3명이 솔루션을 계속 비슷한 시간대에 내서 컴퓨터 분배가 비효율적이었습니다. 그래서 패널티가 많이 쌓인 것이 아쉽습니다. 패널티가 많이 쌓이는 건 저(와 팀셋을 도는 팀)의 숙명인가 봅니다.

7월 3일

낮에는 전날 돈 두 셋을 업솔빙했습니다.

2024 ICPC Swiss Subregional

누가 개쩌는 셋을 찾아왔다길래 개인전으로 몇 분과 함께 돌았습니다. BAPC보다도 더 쉬운 난이도의 셋이었고, 손을 빨리 움직이는 걸 연습하는 무언가를 한 것 같습니다.

돈 사람이 많이 없어서 버춸을 도는 내내 순위가 잘 나왔습니다. 중간중간에 열심히 캡쳐를 했는데, 2솔까지 1등, 4솔까지 4등, 5솔까지 2등(이때가 약 1시간째였습니다), 7솔까지 7등(2시간 반째), 9솔까지 6등(4시간째)이었고, 그 상태로 대회가 종료되었을 때 13등이었습니다.

저답지 않게 패널티 관리가 매우 잘 되었고 - 많이 쉬운 문제를 빠르게 푸는 실력과 약간의 운빨이 도와준 것 같습니다 - 그래서 9솔브 중 1등을 했습니다. 사실 마지막 1시간 동안 한 문제도 못 풀어서 그런 것도 있긴 한데, 한 문제를 더 풀기는 힘들었을 것 같습니다.

당시 했던 말을 인용하면, 체감상 실버/골하에 5..15분을, 골상/플레에 25..50분을 쓰는 것을 잘 지켜서, 매우 이상적으로 돌았던 것 같습니다.

7월 4일

CF Polynomial Round 2022 (Div1+2)

E번까지 크게 어렵지 않게 풀 수 있는 셋이었고, E까지 1시간 정도에 주파했기에 만족스러웠습니다. 사실 그러고 나서 F를 풀지 못했다는 점이 아쉬운데, 풀이를 보니 대략 나이브와 믿음을 섞어 잘 버무리면 proof by ac가 되는 그런 문제였습니다. 절대 못 풀었을 것 같습니다.

퍼포는 E까지 잘 풀었기에 2300 정도 나왔습니다.

2024 ICPC Nanjing Regional

중국의 Sheyang County Rice Association에서 개발한 난징 5718 품종 쌀이 제16회 일본 쌀 품질 및 맛 연구 협회 세미나 및 프리미엄 자포니카 쌀 시식 행사에서 특별 우수상을 받은 기념으로 난징 쌀을 시식하기로 했습니다.

세 명이서 돌았습니다. 체감상 최근 돌았던 셋 중에는 난이도가 가장 어려운 정도였습니다. 그것도 있고, 그냥 제가 버스를 탔습니다.

가장 쉬운 문제 하나를 잡고, 그 다음으로 쉬운 문제가 센트로이드였고, 제가 구현을 박아서 팀원이 문제를 가져가서 대리로 풀었습니다. 그 후로도 개인적으로 많이 말렸는데, 아무튼 버스를 타서 좋았습니다.

생각보다 중국 쌀이 괜찮습니다. 시간 나면 한번 - 꼭 팀을 짜서 - 돌아보세요. 아, 중국 리저널은 언오피셜을 켜도 오피셜이 압도적으로 더 잘하기 때문에 (일반적으로 중국 리저널의 1등은 그 해 중국 IOI 국대로 이루어진 비공식 팀이 가져갑니다) 편하게 슥보를 볼 수 있습니다.

2024 ICPC Greece Regional

을 돌려고 했는데 사실 브론즈 실버만 9문제 나오는 셋이었고 그래서 접었습니다.

7월 5일과 6일에는 거의 놀았습니다. 7월 5일 밤에 CF Round 1035 Div2에 언레로 참가해서 박았습니다. 다음날 밤에 CF Round 1036 Div1+2에 레이티드로 참가했으며, 5문제를 풀어 레이팅이 2 올랐습니다. 개인적으로 박았다고 생각합니다.

7월 7일

2022 ICPC East Central North America Regional (ECNA)

어떻게 대회 이름이 동부중부북아메리카 리저널

학교에서 오프라인으로 돌았습니다. 처음에 ABCD를 잡아서 ABCD를 풀고 (P3 G2 P5 S2, 풀이를 내는 데는 2시간에서 2시간 반이 걸렸고 AC를 받기까지는 3시간 반이 걸렸습니다) 두 D3인 E와 H를 잡다가 대회가 끝났습니다.

E는 기하 문제였는데, 1시간 남은 상태에서 아마도 맞는 솔루션이 나왔지만 풀지는 못했습니다. H는 애드혹 구현 문제였는데, 10분 남은 상태에서 아마도 맞는 솔루션이 나왔고 이걸 집에서 구현하는데 두 시간 걸렸습니다. 결론적으로 무슨 일이 있어도 제가 풀이를 낸 걸로 E랑 H를 대회 시간 중에 풀지는 못했을 것 같습니다.

근데 어쨌든 두 다이아 모두 풀이를 내는 데까지는 성공해서 좋았습니다. 별개로 제가 읽었다면 L이 유량이라는 사실을 모르고 끝났을 것 같은데, ICPC를 하시는 분들은 유량 문제를 보면 바로 보이시나 봅니다. 확실히 제가 아직 많이 부족합니다.

7월 8일

2024 ICPC Latin America Regional

을 도는데 너무 아무 문제도 안 보여서 그냥 브실골골만 풀고 접었습니다. 까고 보니까 그 다음 난이도가 P2 P2 P1 P1 이더라고요. 가장 쉬운 못 푸는 문제의 저점은 아직 플레 중상위에 머무르는 것 같습니다.

KOI 2025 1차대회 1교시

못 참죠?

비코에 올라왔길래 80분 재고 풀어봤습니다. 어째 작년보다도 문제가 안 풀리는 느낌이었습니다. 결론적으로 116점이 나왔습니다. 사실 시험이 엄청 어려운 거였고 저는 꽤 잘 본 축에 속한 것 같습니다.

CF Round 810 Div1

A번을 풀고 나서 아무것도 보이지 않아 1시간 만에 마음이 꺾인 채로 자러 갔습니다. 다음날 아침에 보니까 사실 B부터 많이 어려운 셋이 맞았기에 크게 아쉽지는 않았습니다. 여담으로 1E번이 사실 중국에서 나온 적이 있는 문제라서 셋이 언레였다고 합니다.

7월 9일

KOI 2025 1차대회 2교시

못참죠22?

나름 한국정올이니까 리뷰를 하자면,

1번 문제는 DP임을 어렵지 않게 확인할 수 있었습니다. 상태정의를 잡는 것까지는 쉽고, 전이를 어떻게 해주어야 할지 잘 생각해서 풀면 됩니다. 저는 N일째에 한국이가 x일, 정올이가 y일치 티켓을 구매해 가지고 있는 상황을 정의했고 7가지 티켓에 대해 $2^7$가지 티켓 구매 방법을 모두 확인하는 DP를 짰습니다. 난이도는 골드 중위 정도를 예상합니다.

2번 문제는 한국이가 눈을 감고 있는 동안 정올이가 어디까지 이동할 수 있는지 구하는 것을 N번 반복해주면 되는 문제였습니다. 즉, 다익스트라를 N번 돌려서 풀 수 있었습니다. 구현에서 실수하지 않으려면 꽤나 조심해야 할 것 같은데, 저는 운 좋게 바로 맞았습니다.

앞의 두 문제에서 38분을 쓰고, 남은 1시간 동안 3번을 보기로 합니다. 이에 대해 저는 8분 동안 다음과 같은 풀이를 내는데,

1번부터 N번까지 경로를 수직선 위에 늘어놓고
bfs 돌려서 모든 정점에 대한 '그 정점으로부터 경로까지의 거리와 가장 가까운 경로 위의 점'을 저장해 두고
그럼 로봇 추가 제거를 경로 위의 구간 추가 제거로 볼 수 있고
그 구간은 대충 lower_bound 딸깍하면 알 수 있고
그럼 구간의 합집합이 전체 집합인지를 빠르게 알아야 하는데
세그로 각 지점이 속해 있는 구간의 개수를 관리하는 min 느갱

사실 저것만 해도 문제의 90%는 해결한 것이나 마찬가지입니다. 제가 한 실수를 바로잡자면 사실 짐을 간선 중간에도 둘 수 있습니다. 그렇기 때문에 어떻게 보면 더 쉬운 문제가 되는데, 어쨌든 결국 Q개의 구간 추가/삭제 질의에 대해 그 구간의 합집합이 전체집합인지 확인하는 문제입니다.

구간 확인에 등장하는 서로 다른 값이 $O(Q)$개이기 때문에 좌표압축을 가해줄 수 있고, 그러면 느리게 갱신되는 세그트리를 이용하면 쉽게 문제를 해결할 수 있습니다.

저는 대회 시간동안 구현을 마치지 못해서 34점만 받았고, 후에 30분에서 1시간 정도 구현을 더 해서 만점을 받았습니다.

34점을 받은 상태로는 총 400점으로 금상을 받지 못하고, 만점을 받았어야 금상이 나옵니다. 아직 갈 길이 먼가 봅니다. 일단 구현 능력을 키워야겠습니다.

2024 ICPC Taiwan Online Programming Contest (대만 예선)

대만 예선은 12문제를 3시간동안 푸는 타이트한 대회입니다.

쉬운 문제들에서 많이 틀려서 고생했지만, 한편으로는 그만큼 문제를 빨리 풀어서 패널티에서 크게 손해를 보지는 않았습니다. 오히려 문제수로 밀렸는데, P5까지를 1시간 50분에 밀고 나서 남은 1시간 10분동안 P1과 P2를 번갈아 잡다가 둘 다 풀지 못해서 끝난 케이스입니다.

조금 덜 틀렸으면 시간이 남아서 뭐라도 풀 수 있었으려나요? 못 푼 두 문제 중 하나는 세그 그리디, 하나는 정수론 그 자체였습니다.

---

네.

확실히 뭔가 많이 하긴 했습니다. 그래서 실력이 많이 올럈냐 물으신다면 글쎄요.

이상은 PS 블로그이고, 비-PS 블로그 - 그러니까 프로포지션 - 도 조만간 올리려고 노력은 해보겠습니다. 제 블로그를 자주 보시면서 디코로 연이 안 닿아 계신 분이 있는지는 모르겠지만, 저 잘 살고 있습니다.

요즘 셋을 돌 때는 대부분 solved.ac 디스코드의 문제-함께-풀기 채널의 ("Road to %d",max_rating+100) 쓰레드에 내용을 올리고 있습니다. 이미 솔브드 디코에 가입되어 계신다면 이쪽의 링크로 확인하실 수 있을 겁니다. 또, 요즘은 셋을 돌고 나서 일정을 시트에 기록해두고 있습니다. 이쪽에서 구경하실 수 있습니다.

감사합니다. SCPC 1차가 이제 내일이 아니고 오늘이니, 자러 가야겠습니다.