1월 1일 PS 일기 (ICPC 2025 Manila Regional)

새해 첫 셋으로 ICPC 2025 Manila Regional을 돌았습니다.
https://codeforces.com/gym/106262
#9+1333/13으로 온사이트 기준 11등, 코포 기준 8등을 받았습니다.

ICPC 2025 Manila Regional의 풀이를 다수 포함하고 있으니, 팀 연습을 도실 분들은 여기서 뒤로가기를 눌러주시면 감사하겠습니다.

대회 시작 (00:00~01:00)

지금까지 돌았던 셋들 중 유의미하게 많은 셋이 A번을 가장 쉬운 문제로 두었습니다. A번부터 읽기 시작했습니다.

A번(00:02 AC)

풀이는 굳이 적도록 하지 않겠습니다.

체감 난이도: B3

이어서 D번을 읽었고, Probable한 풀이가 나와서 짜기 시작했습니다. (스포: 틀린 풀이입니다.)
10분정도 박았는데 예제도 제대로 안 나와서 다른 팀들이 푼 문제를 확인했습니다. 가장 많이 풀린 G번으로 틀었습니다.

G번(00:22 WA, 00:24 WA, 00:25 WA, 00:25 AC)

a[i]의 값이 양수인 것은 다 선택하고, 만약 아무것도 선택되지 않았다면 남은 것들 중 최댓값을 선택했을 때 b+a[i]의 값이 0 이상인지 판별합니다.
이상하게 구현해서 3틀을 박았지만 일단 25분에 AC를 띄웠습니다.

체감 난이도: S5~S4

L번(00:43 WA, 00:47 WA, 00:48 WA, 00:52 AC)

a[i][j] != 0이고 b[j][i] != 0인 경우만 tr(AB)가 증가합니다. map을 이용해서 구현해 주면 바로 AC가 나와야 합니다.
굳이 map의 key를 pair<int,int>로 하지 않고 int로 하려다가 3틀을 먹고 풀었습니다.

체감 난이도: S2~S1

여기까지 평소 폼대로라면 아무리 길어도 30분 안으로 컷 냈어야 했는데, 무려 6틀과 함께 52분이나 걸렸습니다.
같은 솔브 수 내에서 페널티 경쟁은 사실상 힘들어졌고, 솔브 수 차이를 하나 이상 내야 다른 팀들을 이길 수 있게 되었습니다.
L번을 풀고 나서 20등 중반~30등 초반이었던 걸로 기억합니다.

중반 (01:00~03:00)

그 다음 풀 문제들의 후보로 E, H, M번이 있었고 D번은 많이 풀리진 않았지만 풀이를 언제든지 고쳐서 맞을 수 있다는 자신감이 있었습니다.
일단 목표를 E, M, H를 다 풀어서 인간컷을 맞추고 D를 풀어내는 것으로 잡았습니다.

E번(01:08 RE, 01:12 WA, 01:15 AC)

(본체의 위치, 클론의 위치)를 기준으로 BFS를 돌려 주면 되는 직관적인 문제이지만 구현이 매우 귀찮고 까다로웠습니다.
대회 치는 도중에는 구현이 너무 길었고 체감상 1시간은 박은 것 같은데, 끝나고 나서 타임스탬프를 보니까 25분 컷 냈었네요.

체감 난이도: G3~G1
발상하는 난이도는 쉽지만 정올 기출문제 "토마토"의 티어와 비교해서 G3~G1을 줬습니다. 구현에 약하다면 체감 플래까지도 갈 수 있겠습니다.

A, G, L, E까지는 풀이가 매우 직관적이라 설명할 것이 많지 않았습니다.

그 다음으로 M번의 풀이를 발상해냈고, 짰지만 TLE를 받았습니다.
풀이가 잘못됐다고 생각하여 D번으로 틀었지만, 또 예제가 나오지 않았습니다.
어떤 식을 적분하여 자연로그를 사용해야 정답을 구할 수 있다는 점만 짚고 H번으로 넘어갔습니다.

H번(01:58 WA, 02:00 WA, 02:04 AC)

관찰 1) k >= 5인 경우에는 prime spaced인 set의 가짓수가 0이다.
k가 충분히 커지면 set에 있는 원소들을 정렬했을 때 차이가 큰 짝수인 것이 생기기 마련입니다.
k가 4인 경우까지는 정렬했을 때 인접한 원소의 차이를 2 / 소수 / 2로 두어서 두 원소의 차이로 가능한 것이 2, p, p+2, p+4이게 할 수 있지만, k가 5 이상이라면 두 원소의 차이가 4이거나 소수 + 소수인 경우가 존재해야만 합니다.
관찰 2) k = 1인 경우에 답은 "n 이하 소수의 개수"이다.
관찰 3) k = 2인 경우에 답은 "n 이하 소수 p에 대해서 (n-p)의 합"이다.
set의 두 원소의 차이는 무조건 소수 p여야 하고, n 이하의 두 정수의 차이가 p인 경우의 수는 n-p입니다.
관찰 4) k = 3인 경우에 답은 "n 이하 쌍둥이 소수 p-2, p에 대해서 (n-p)*2의 합"이다.
기본적으로 관찰 3과 똑같지만, 하나의 p에 대해서 {a,a+p-2, a+p}, {a, a+2, a+p}라는 두 가지 경우가 가능해집니다.
관찰 5) k = 4인 경우에 답은 "n 이하 세쌍둥이 소수 p-4, p-2, p에 대해서 (n-p)의 합"이다.
n, k의 범위가 10^7까지이므로 에라토스테네스의 체를 사용해서 잘 구현해 주면 답이 나옵니다.

체감 난이도: G3~G1

관찰 5를 빼먹고 코드를 짜서 2틀을 받았고 마지막 관찰을 해낸 뒤 코드를 고쳐서 AC를 받았습니다.

M번(01:47 TLE, 02:06 WA, 02:13 WA, 02:19 WA, 02:25 AC)

관찰 1) chemical의 수를 n, shop의 수를 m이라 했을 때 n <= 15 or m <= 15가 성립한다.
n에 대해서 지수 시간에 풀리고 m에 대해서 지수 시간에 풀리면 문제가 풀릴 것 같습니다.

m에 대해서 지수 시간에 푸는 것)
shop을 고르는 2^m가지 경우에 대해서 (고른 shop들 중에서 각 chemical의 가격의 최솟값 + 고른 shop들의 배송비의 합)의 최솟값을 구해주면 됩니다.

n에 대해서 지수 시간에 푸는 것)
i번째 shop까지 봤을 때 어떤 chemical들을 샀는지의 경우의 수는 2^n입니다. 외판원 순회를 돌리듯이 비트 dp를 돌려주면 됩니다.
저는 i번째 shop에서 chemical을 샀는지 / 안 샀는지 여부까지 고려하면서 dp를 돌렸습니다.

시간복잡도가 O(nm * min(2^n,2^m))이고 하나의 TC에 대해서 총 10개의 테스트가 주어집니다. 일단 뚫는다는 마인드로 pragma를 박았다가 TLE가 났습니다.
어떤 코드의 경우에는 pragma를 안 쓰는 게 더 빠른 경우도 있어서 안 써 봤더니 TLE 대신 WA가 나왔습니다.
변수명 조금 고쳐보고 INF 값 조금 고쳐보고 코드 다시 짜보고 하다 보니까 갑자기 AC가 나왔습니다.
2:19때 받은 WA 코드랑 2:25때 받은 AC 코드랑 구조는 완전히 똑같은데 결과가 왜 다를까요?? 아마 샤머니즘의 영역이 아닐까 싶습니다.

체감 난이도: P4~P3

D번(02:38 AC)

부피가 v인 술을 제조했을 때 알코올 양의 최소/최댓값은 각 v에 대한 함수로 나타낼 수 있습니다.
(농도순, 농도 역순으로 정렬했을 때 최소/최댓값을 얻을 수 있습니다.)
이 두 함수를 0부터 V까지 적분한 값의 차를 구해주면 답이 나옵니다.

풀이는 간단하지만 약간의 식 정리가 필요했습니다. A번 이후로 처음으로 한번에 AC가 나왔습니다.
사실 예제가 맞게 나온 순간 WA를 받는다면 "실수오차망겜!"을 외치고 유기할 생각이었습니다.
한번에 AC가 나와서 다행입니다.

체감 난이도: idk
태그에 "미적분학"이 들어간 문제들 난이도는 잘 모르겠습니다. 그래도 골드는 될거고 그래도 플3은 안 넘겠죠..?

여기까지 해서 7솔이었고, 스코어보드에서 다음 두 가지를 관찰했습니다.
1) 9솔 이상의 팀이 거의 없다.
2) 8솔을 한 팀은 대부분 D를 못 풀고 I와 J를 풀었다.
즉 제가 I와 J를 푼다면 느린 9솔로 꽤 잘했다고 평가받을 만한 퍼포먼스가 나올 것입니다.

B, C, F, K에서 제가 풀 만한 문제가 있을지도 모른다는 생각을 했지만, 다음 사유로 기각했습니다.
- B는 수쿼 비스무레한 문제인데 아마 다이아일 것 같았습니다.
- C는 그림부터 어지러웠고, 아무도 푼 사람이 없다는 점에서 기각했습니다. 깡구현 문제라면 한 팀정도는 풀지 않았을까요??
- F와 K도 딱 봤을 때 풀이 안 나옴 + 푼 사람 적음을 이유로 기각했습니다.
2시간 반이 남았고, I와 J만 풀면 만족할 만한 성과를 낼 수 있습니다.

후반 (03:00~05:00)

I번(03:32 AC)

관찰 1) 충분한 전처리를 하면 구간 [s,e]가 주어졌을 때 H(int(S[s,e]))의 값을 O(1)에 구할 수 있다.
각 숫자가 몇개씩 등장하는지 알 수 있으면, 10의 몇승째 자리부터 몇승째 자리까지 특정 숫자가 들어가는지 알 수 있고,
10^i의 값을 누적 합을 포함해서 전처리 해뒀다면 O(1)에 가능합니다.
이 관찰이 직접적인 solution으로 이어지지는 않지만, s, e, i라는 변수 중 i를 고정하고 돌린다는 발상으로 이어졌습니다. (관찰 1은 s,e를 고정하고 i를 바꿔가면서 답을 구했습니다.)

관찰 2) H(int(S[1,s]))부터 H(int(S[s,s]))까지의 합에서 특정 숫자 i가 얼마나 기여하는지 구하면, s가 1씩 증가함에 따라 O(1)만큼의 시간에 앞서 언급한 "기여도"를 갱신할 수 있다.
s가 1 증가할 때, S[s+1]이 i보다 크면 기여도에 10을 곱하고 1을 더합니다. 아니라면 기여도에 1을 더합니다.
비슷한 방식으로 s 이후의 합들에 대해서도 기여도를 구할 수 있고, 두 기여도를 곱하면 각 s[i]가 최종 정답에 얼마만큼씩 기여하는지 O(1)에 구할 수 있습니다.

체감 난이도: P3~P2

J번(04:20 AC)

30분동안 문제를 잘못 이해했었습니다. "5턴만 진행하고 종료한다"는 조건을 빼먹었습니다. 위 조건을 발견하고 20분만에 AC가 나온 것 같습니다.
관찰 1) 차수가 4 이상인 정점에서 시작하면 필승이다.
오목에서 33이 있다면 틱택토(삼목)에는 11이 있지 않을까요?

관찰 2) 차수가 1인 정점은 필패이다.

차수가 2, 3인 정점 v에 대해서는 v와 인접한 정점들이 서로 연결되어 있는지 여부로 경우를 나눠서 케웍을 돌렸습니다.

체감 난이도: G2~P5

이후 남은 문제들이 B, C, F, K인지라 앞서 설명한 사유로 인해 먼저 GG치고 셋을 마무리했습니다.

셋 이후

혼자서 9솔을 하고 전체 11등을 했지만, 아쉬운 점이 여럿 남았습니다.
- 초반 푸쉬가 너무 느렸습니다. 실버~골드 라인에서 먹으면 안 되는 페널티를 너무 많이 먹었고 결국 9솔 꼴등으로 마무리했습니다.
- 결국 마지막에 남은 시간이 애매해서 J를 풀고 남은 4개의 문제들을 건드려보지도 못했습니다. 30분정도 더 있었다면 B 잡다가 폭사하기 딱 좋은 시간입니다.
- 그랬다면 아마 지금 B 업솔빙을 하고 있었겠죠..?
- 문제를 너무 대충 읽었습니다. '지문에서 앞에 절반은 쓸데없는 소리니까 넘어가야지'라고 생각했다가 J번에서 한번 당했습니다. 제가 영어 독해가 느린 편도 아닌지라 모든 내용을 이해하고 문제를 풀어도 늦지 않을 것 같습니다.

5시간 셋이니만큼 타임어택에 너무 신경쓰지 말고 페널티를 최소한으로 쌓는다는 마인드로 임해야 더 좋은 퍼포먼스를 얻을 수 있겠습니다.
추가로 다음 사실들을 관찰했습니다.
- 문제에서 나오는 mod 값들이 하나같이 특이했습니다. 998244353이나 1e9+7같은 국룰 mod는 한 번도 나오지 않았습니다. 1,000,696,967이라는 mod는 태어나서 처음 봤습니다.
- 문제 지문에서 문제에서 요구하는 내용을 이해하는 데 필수적이지 않은 부분이 너무 많았습니다.

전반적으로 셋의 난이도 커브나 문제 자체의 퀄리티는 만족스러웠습니다. 하지만 지문 늘려놓기나 구현량이 지나치게 많은 쉬운 문제 등 약간 불쾌할 수도 있는 부분이 존재했습니다.
실전이었다면 상당히 아쉬운 셋이었을 수도 있지만, 팀"연습"의 취지에는 적당하다고 생각합니다.
내일은 하루 쉬었다가 주말에 다시 코포/앳코더 돌아보겠습니다.

감사합니다.