제3회 SCSC Computer Programming Contest

2주 전 카이스트에 이어, 2025년 5월 19일에 서울대 SCSC Computer Programming Contest에 다녀왔습니다. Division 1의 44명 중 27위를 했습니다.

대회 이전

• 뭐두스에서 12명이 참가 신청을 해버리는 바람에, 점심을 먹으러 만나려고 했습니다.
• 근데 당일 오전에 같은 건물에서 KMO가 있었습니다. 보러 간 경곽 고삐리들이 많아서 점심팟이 없어질 위기에 처했습니다.
• 솔브드 커뮤대회챈에서 버거운 버거 점심팟이 생겼다길래 KMO 안 보는 뭐두스들을 다 여기로 부르고 저도 갔습니다.
• 디코를 하고 계신 세 분이 서 계셨고, 그중 한 분이 toycartoon님이셨고, 다가가서 세그먼트 트리라고 소심하게 외치니까 친?구가 될 수 있었습니다.
• 빠르게 많은 사람들이 모였습니다. 12명?인가가 같이 대회장으로 이동했습니다.
• 도착하니까 iccodly가 보여서 같이 들어갔습니다.
• 명찰을 주시더라고요. 제 팀명은 슼보 핸들 did_you_check_n_is_1 추천합니다 였습니다. 이전에 솔브드 잡담에 팀명 추천을 받으니까 하이퍼볼릭님이 저렇게 보내주셔서 갖다 썼습니다.
  • 제 팀명 덕에 검수 솔루션 하나를 터뜨렸다고 합니다. 감사하십시오.
  • 정작 저는 도움을 못 받았습니다. :blobsad:
• 회장에서는 더 많은 분들을 뵈었습니다.
  • ‘해병대 팟’을 가장 먼저 만났습니다. 제16대 트릭컬 마이너 갤러리 갤주 셰럼, Bumbardiro Gibumino, hán guó xiǎo nán niáng, 범 범 범 범 범 범 범 범 범 쌀후르, 추노한엄종노, 다른 이름, 10년동안 묵혀있던 전설의 검 등등과 야부리를 털었습니다.
    • 회장에서 10년동안 묵혀있던 전설의 검이랑 제16대 트릭컬 마이너 갤러리 갤주 셰럼이 리듬게임을 하는 것을 구경했습니다.
  • 생각보다 40기 경곽이들이 많았습니다. _’, iccodly, 백준스터디, 백두산을 만났습니다.
  • KMO 끝나고 완전체가 된 ‘뭐두스 팟’에서는 노르웨이산염간고등어를지켜주세요지키지않으면입에서빔을쏴서인류가멸망해요, 아따 시밤 파이아, 응가쟁이, 변재우는왜넘버링을못풀었는가, 눠쉔슇끠봎즹쎼묝읅쏛괋혱꾄뷸숏뿹쮜눨륯읭솄궤뇾 등을 만났습니다.
  • 외에도 Serendipity__님, 슼보그만보고문제풀어요님, octane님, .님, 25학번 2회차 새내기님, LUN4Я!$//T3RR∆님, 노노님, toycartoon: 저, 디비전은 3로 해달라고 말했잖아요!님 등등과 인사를 하거나 야부리를 털거나 ‘저분이 왔다는 사실을 인지’했습니다.
• 딥1 회장은 지금까지 다녀왔던 그 어떤 오프대회보다도 무서웠습니다. 그냥 절반 정도 인원이 적어도 2400인 것으로 보였습니다. 실제로 1등부터 10등까지의 탑레가 모두 2600 이상이었습니다.
• 대회가 20분 연기되었습니다.

몇 문제 못 풀어서 대회 내용이 뭐가 없습니다.

A번 (0:19 AC, 19분)

• 앞 두 문제가 가장 쉽다고 그러더라고요. 일단 A랑 B를 번갈아가면서 읽었던 것 같습니다.
• 실제로 격자를 걸어가는 그래프를 그려보면, 1번의 swap으로 그래프 하나의 면적을 1 넓히거나 줄일 수 있습니다.
• 여기서 볼 수 있는 게, 두 경로가 겹쳐 있다면, 두 경로 중 하나가 다른 하나보다 위에 있게 하기 위해서는 그 경로의 길이만큼 위로 보내주면 됩니다.
• 두 경로 중 각각이 다른 경로에 겹치거나 그보다 위에 있도록 하러면 몇 번이나 면적을 넓혀주어야 하는지를 계산해주면 문제를 풀 수 있습니다.
• 다행히도 빠르게 푼 편에 속했던 것 같습니다.

B번 (0:44 WA, 1:03 WA, 1:14 WA, 1:18 AC, 59분)

• A가 그나마 빠르게 풀려서 약간 안정된 마음으로 B를 봤습니다.
• 신기한 형식의 문제라고 생각했습니다.
• 조금 생각해보니까, 맨 뒤에서부터 적용하고 정렬되지 않은 것들만 업데이트하다가 언젠가 unstable 하나가 들어오면 그때 남은 정렬되지 않은 것들을 섞는 개수를 세어주면 되는 문제였습니다.
• 여러 번의 구현 이슈를 겪었습니다만 결국 풀어냈습니다.

J번 (1:42 TLE, 1:48 TLE, 2:05 AC)

• 무슨 제일 마지막 문제가 엄청 풀리더라고요. 바로 봤습니다.
• 그냥 해싱을 잘 스까서 매내처를 다 돌리면 풀 수 있는 문제였습니다.
• 혹시 해싱이 뚫리지 않을까 싶어 map을 써봤는데 바로 컷당했습니다.
• 근데 그냥 제대로 된 해싱도 TLE를 받더라고요?
• 알고 보니 가져온 매내처가 너무 느렸습니다. 빨라지도록 코드를 엎었더니 맞았습니다.

D번 (3:55 WA)

• 다음으로는 D 아니면 E를 풀어야 했습니다. D가 조금 더 풀리고 있길래 먼저 봤습니다.
• 가장 가중치가 작은 간선부터 그래프에 이어 봅시다. 그리고 추가한 간선의 두 정점은 서로 다른 팀에 속하도록 할 수 있는지 생각해 봅시다.
• 추가한 간선이 같은 팀 쪽에 있다면 간선 양쪽의 두 정점 중 하나가 다른 팀으로 가야 합니다. 그렇지 않다면 두 정점 모두 그대로 있거나 다른 팀으로 가야 합니다.
• 이는 이분 그래프 느낌으로 모델링할 수 있습니다. 즉 간선을 추가하면서 이분 그래프인지 확인해주면 되고, 여기까지는 작큰 같은 걸로 간단하게 만들 수 있습니다.
• 문제는, ‘한 그룹에서 한 명까지’ 조건을 이 방법으로 깔끔하게 처리할 수가 없습니다. 그룹별로 색상을 관리하는 추가 정점을 만든다거나, 그룹별로 이분그래프 양쪽 정점의 개수를 세그로 관리하면서 체크하거나 하는 다양한 방법을 시도했지만 성공하지 못했습니다.

E번 (제출 없음)

• 격자 위를 신기하게 움직이는 문제입니다.
• 각 점에 대해, 그 점을 사용하는 경로의 수를 세고자 했습니다. 결국 카탈란 수열의 결합으로 나타낼 수 있었습니다. 보다 정확히,
  • 길이 L만큼 이동하는 경우의 수는, 이동하면서 $y=x$ 위에 도달하는 횟수에 따라 나누어서 생각하면 되는데요,
  • 안 올라가는 경우의 수는 $C_L$
  • 한 번 올라가는 경우의 수는 $C_0C_{L-K}+C_1C_{L-K-1}+\cdots=C_{L-K+1}$
  • 두 번 올라가는 경우의 수는 $C_0C_0C_{L-2K}+C_0C_1C_{L-2K-1}+\cdots+C_{L-2K}{C_0}{C_0}=C_{L-2K+2}-C_{L-2K+1}$
  • 세 번 올라가는 경우의 수는 $C_{L-3K+3}-2C_{L-3K+2}$
  • 네 번 경우의 수는 $C_{L-4x+4}-3C_{L-4x+3}+C_{L-4x+2}$
  • …
• 딱히 규칙이 안 보이더라고요. 열심히 생각해보다가 안 될 것 같아서 접었습니다.

종료 이후

• iccodly에게 D, _‘에게 E의 풀이를 들었습니다. D는 2-SAT 딸깍이 가능했고, E는 ^online fft^ 하면 되는 문제였습니다.
• 2SAT도 FFT도 익숙하지 않기 때문에 B와 J에서 풀이를 낸 채로 전 것을 빼고 딱히 아깝지는 않았습니다만, 이런 것도 잘 풀어야 될텐데 하는 생각은 들었습니다. 더러운 걸 잘 푸는 연습도 확실히 필요한데 말입니다.
• 슥보를 까러 이동하면서 해병대팟, 경곽40기팟, Serendipity__님과 잠깐씩 야부리를 털었습니다.
• 슥보 공개는 다른 강의실에서 진행하더라고요. 운영진 분들이 열심히 팀명을 읽으시는 것들을 들었습니다.
• 저는 딥1 27등이더라고요. 제 이름을 까시면서 ‘이분 팀명을 보고 N=1을 추가해 봤는데 검수 솔루션 하나가 터졌다’고 하시더라고요. 팀명을 지어주신 하이퍼볼릭님께 감사하십시오. :blobhyperthink:
• 서울대까지 와서 동아리 활동점수를 채우시는 런 분들을 위해 활동사진을 찍어드렸습니다. 런 소속이 아니신 범 범 범 범 범 범 범 범 범 쌀후르같은 분들이 사진에 섞여 들어가긴 했지만, 뭐 알빤가요?

뒷풀이

• 에 또 갔습니다. 가게 이름이 치르치르였는데, 차르차르가 입에 더 잘 붙는 것 같습니다. 폭탄 맛도 나고, 테트리스 생각도 나고 좋지 않나요…
• 뭐두스팟이 어쩌다 보니 13명짜리 팟이 되어서, 같이 한 테이블에 앉았습니다. 치킨을 기다리면서 N명의 참가자와 M개의 테이블으로 이루어진 뒷풀이에 K초마다 치킨을 공급하는 문제를 생각했습니다.
• 종이님, toycartoon: 저, 디비전은 3로 해달라고 말했잖아요!님, 25학번 2회차 새내기님 등과도 야부리를 털었습니다.
• 확실히 런 뒷풀이는 (몇 개의 아는 사람들끼리의 디스코드 서버에서 매번 보던 사람)들과의 뒷풀이인 반면 스시스시 뒷풀이는 (솔브드 디코에서 지나가다 몇 번 혹은 그 이상 정도 봤던 사람)들과의 뒷풀이라서 느낌이 많이 달랐습니다. 뭐 둘 다 재밌긴 했습니다.
• 그러다가 이러다간 SCSC 동방에서 재워달라고 해야 될 것 같아서 빨리 집에 왔습니다.

그랬습니다. 다음 주 ACPC까지 다녀오면 한동안 오프 대회는 없겠네요. 아쉽습니다. 오프라인 대회 운영이 얼마나 귀찮고 노력 많이 들어가고 물질적 리턴 없고 힘든 일인지 대충 알기에, (심지어 이런 대회들은 아무나 참가할 수 있으니까 더 힘들겠지요,) 오프 대회를 열어주시는 분들께는 항상 감사하고 있습니다. 혹시 읽고 계시는 운영진 분이 계신다면 팬이에요 :blobaww:

대회 후기 글을 두 개 싸지른 관계로 Proposition은 늦어지거나 한 주 없을 예정입니다.

뭐 암튼 그러합니다. 감사합니다.