Post

CERC 2019, PPC 2025, Seoul Regional 2024

Posted
By
26 min read
CERC 2019, PPC 2025, Seoul Regional 2024

버추얼을 많이 도는 것이 좋습니다.

2025년 5월 21일에 ICPC CERC 2019를, 26일에 PPC 2025를, 28일에 2024 서울 본선을 돌았습니다. 제목과 같이 이번에도 혼자 돌았습니다. 결과는 다음과 같습니다.

  • CERC19: 8+1065, 본대회 25등
  • PPC 2025: 10+963, 본대회 1등 (jununu+equinox 팀을 이겼으므로)
  • Seoul24: 6+660, 본대회 23등

CERC 2019

개인적으로 힘들었습니다. D, E, L에서 너무 많은 자원을 소모했습니다. G, I를 빠르게 푼 것은 좋았다고 생각합니다.

0:00~0:15 (A +)

  • 별 생각 없이 A부터 봤습니다.
  • 매내처를 짜면 바로 풀 수 있는 문제였습니다. 팀노트를 열심히 베꼈습니다.
  • 15분 걸렸는데, 평타는 친 것 같습니다.

0:15~0:29 (C +1)

  • C를 봤습니다. 트리를 path로 만드는 문제였습니다.
  • 리프 개수를 세서 -2해주면 됨이 보입니다. 짜서 냈고 바로 틀렸습니다.
  • SCSC 팀명을 무시한 제 잘못입니다. N=1인 경우의 예외를 처리했고 바로 맞았습니다.
    • 예외를 생각해내는 데 8분이나 걸린 건 잘못했다고 생각합니다.

0:29~0:37 (G +)

  • 자연스럽게 슥보의 다음으로 많이 풀린 문제로 넘어갔습니다.
  • bitwise and가 최대가 되는 크기 K의 부분집합의 bitwise and를 구하면 됩니다.
  • 상위 비트부터 하나씩 보면서 K개가 있으면 그 비트가 1인 것만 남기고 싹 지우는 것을 그리디하게 반복하면 됩니다.
  • 빠르게 푼 것 같아 기분이 좋습니다.

0:37~0:58 (F +)

  • 입력으로 주어지는 두 수에 대해 그 사이의 모든 정수의 약수의 개수의 합을 구하면 됩니다.
  • 1 이상 N 이하의 모든 수의 약수의 개수는 $[\frac{N}{1}]+[\frac{N}{2}]+[\frac{N}{3}]+\cdots$입니다. 이는 $O(\sqrt{N})$에 구할 수 있습니다.
  • 그러면 풀립니다. 위 사실을 생각해내는 데 시간이 조금 걸렸지만 아무튼 풀었습니다.

0:58~1:46 (D +)

  • Chomp랑 비슷한 스그 게임입니다.
  • 모든 tainted square를 포함하는 최소 직사각형까지 가는 님 게임이며, 따라서 그냥 묶음이 4개인 님 게임에서 승리하면 됩니다. (여기까지 오는 데 적어도 30분은 걸린 것 같습니다.)
  • 그러면 네 개의 묶음의 xor값을 0으로 유지해주면 됩니다. 네 묶음을 각각 $a, b, c, d$, $x=a\oplus b\oplus c\oplus d$라 하면 $a\oplus x$, $b\oplus x$, $c\oplus x$, $d\oplus x$ 중 원래 수보다 작아지는 게 하나는 있으므로, 구현하면 됩니다.
  • 시간을 너무 오래 써서 아쉬우나, 결론적으로 패널티를 쌓지는 않았으므로 다행입니다.

1:46~1:57 (I +)

  • 염기서열이 주어지면 min swap sort의 swap 횟수를 구하면 됩니다.
  • a를 b로 바꾸고, b를 c로 바꾸고… x를 a로 바꾸는 사이클이 있다면, 그 사이클의 크기 -1만큼이 swap 횟수에 추가됩니다.
  • 그러므로 사이클 크기 2, 3, 4 순서대로 그리디하게 최대한 사이클을 풀어주면 됩니다.
  • next_permutation을 써주면 매우 쉽게 딸깍 구현할 수 있습니다. 11분 만에 1트에 맞은 것은 아주 잘한 것이라 생각합니다.

1:57~2:40 (E +5)

  • 대충 계산기하 문제인데, 그냥 수능 기하 문제입니다.
  • 점에서 원을 긋고 직선과의 교점을 구해 두 교점 사이의 구간을 가지고 최대 클리크를 구하면 됩니다.
  • 피타고라스 정리를 쓰면서 절댓값에 마이너스를 안 붙여서 틀리고, 원이 직선에 접하는 경우를 따로 고려해주지 않아서 틀리고, 두 원의 접점이 직선 위에 있는 경우를 고려해 주지 않아서 틀리고, 아무튼 다양한 방법으로 틀렸습니다.
  • 18분과 패널티 100점을 버렸습니다.

2:40~4:23 (L +8)

  • 수열에서 아무 세 원소나 잡아서 서로 다른 세 원소의 크기 순서를 모두 찾는 문제였습니다. 크기 관계는 총 13가지 있으므로, 셋질과 세그 약간을 섞은 케웍 노가다 문제입니다.
  • 역대급으로 많이 틀렸습니다. 이번 대회에서 퍼포가 안 나온 가장 주요한 원인이 된 문제입니다.
  • 언오셋을 써야 되는데 셋을 썼다던가, 사실 세그를 써야 되는데 언오셋으로 비볐다던가, 케웍을 하면서 변수를 잘못 썼다던가 (실수를 서너 번 했는데, 각각 따로따로 틀렸습니다) 해서 많이 절었습니다.
  • 아래에서 언급하겠지만, icpc를 돌 때 가장 큰 문제 중 하나가 적나라하게 드러났습니다. 아무튼 결론적으로 풀긴 했으나, 매우 힘들었습니다.

4:23~5:00 (J -9)

  • 뭔가 루트질을 하면 될 것 같은데 계속 TLE가 나왔습니다. 시간이 없어서 못 풀었습니다.

PPC 2025

꽤나 좋았습니다. 어떻게든 3인팀인 채로 진행했으면 적어도 본대회는 [[압도적 살해]]가 가능했을 것 같습니다.

0:00~0:28 (A +, M +, B +1, G +)

  • A와 M이 브론즈였습니다. 빠르게 풀고 넘어갔습니다. 합 6분 걸렸습니다.
  • M을 보기 전에 B를 봤는데, 어렵지 않을 것 같아서 M을 풀고 나서 잡았습니다.
  • 그림을 떠올리고 격자 위 경로를 한 칸씩 구부리며 미는 것을 생각하면, A와 B의 개수는 하나의 구간으로 나타낼 수 있음이 보입니다.
  • 매우 어이없는 자명한 실수를 하나 했습니다. 어쨌든 바로 맞았습니다.
  • 그러고 나서 G가 눈에 들어와서 빠르게 짰습니다.
  • 풀이는 대충 누적합 딸깍하면 됩니다.

0:28~1:04 (K +1, C -2, D +)

  • K를 봤습니다. 구성적 문제였습니다.
  • 2일 때는 안 된다고 했고, 3일 때는 되고, N일 때 N+3이 되는 것이 빠르게 보였습니다.
  • 4, 5일 때의 경우를 찾고자 했고, 4는 바로 보였고 5는 안 보였습니다.
  • 3k+0or1 꼴만 구현해서 제출해봤고 틀렸습니다.
  • 3k+2꼴을 열심히 찾다 보니 사실 있었습니다. 구현해서 바로 맞았습니다.
  • C를 봤습니다. 뭔가 그냥 하면 될 것 같습니다.
  • 안 되더라고요. 일단 포기했습니다.
  • D를 봤습니다. 사실 이전에 잠깐 잡았다가 모르겠어서 뱉었습니다. (아마 M을 풀고 나서였던 것 같습니다)
  • 뭔가 기울기가 가파르다는 것이 컨벡스헐이랑 연관되는 것 같길래 열심히 그려봤습니다.
  • 거기서 조금 더 가니까, 그냥 이웃한 것끼리 나오는 기울기 중에 최대가 있더라고요?
  • 최소는 90도 돌려서 구해주면 됩니다. 빠르게 짜서 맞았습니다.

1:04~2:02 (H +6)

  • 그러고 나서 뭘 봐야 될지 모르겠어서 쭉 돌았습니다.
  • H가 어렵지 않아 보이길래 잡았습니다.
  • 그냥 루트부터 정점별로 최단거리 잡아서 그 범위 안쪽의 정점들 사이에 간선을 추가해주는 경우를 열심히 더하면 되는 문제로 보였습니다.
  • 이미 있는 간선에 대한 경우를 빼주는 걸 n번 잘못 생각해서 n번 틀렸습니다. 안타깝습니다.

2:02~2:07 (I +)

  • 구데기 구현 문제일 것 같아서 미루고 미루었는데, 생각해 보니까 쉬운 구현이었습니다.
  • 몰라뵈어 죄송합니다. 바로 풀었습니다.

2:07 ~ 2:24 (J +)

  • H를 풀기 전에 읽으면서 ‘DP 아닐까’ 라는 생각까지 하고 지나갔습니다.
  • $dp_{i,j}$가 i부터 j까지 구간의 최댓값을 나타낸다고 하고 바텀업하면 되게 생겼습니다. 사과를 새로 따는 상태 전이를 잘 만드는 것이 관건입니다.
  • 결국 사과를 딸 때 한 구간을 골라서 따니까, 사과를 따는 것은 어떤 구간을 골라 그 구간의 최대 점수만큼을 뺐을 때 딱 10이 남아서 상태를 업데이트해주는 것과 같습니다.
  • 슥슥 짜면 됩니다. 상태는 두 구간의 합이 새로운 구간을 포현하도록 하면 되니까 세제곱입니다.

2:24~3:26 (C +2, L)

  • 네 문제가 남았는데,
    • C는 개쩌는 관찰이 필요해 보이고,
    • E는 딱 봐도 구현하기 싫게 생겼고,
    • F는 딱 봐도 보스 문제같아 보였고,
    • L은 기하였습니다.
  • 놀랍게도 저는 여기서 기하를 보는 선택을 합니다.
  • 통나무가 컨벡스 헐을 완전히 자르면 불가능하고, 그렇지 않으면 가능해 보입니다.
  • 통나무와 같은 직선상에 있는 점들을 잘 처리해준 다음,
  • 통나무의 양쪽에서 점을 하나씩 잡고 성게를 만들어준 다음,
  • 컨벡스헐 위에 있는 선을 가지고 통나무 양쪽의 성게를 이어주면 풀 수 있을 것 같습니다.
  • 까지 생각했을 때 1시간 정도가 남아있었습니다. 짜기가 싫었고, 기하의 신 Equinox에게 풀이를 뱉은 뒤 튀었습니다.
  • 그나마 아까 잡았던 C를 잡는 것이 현명해 보였습니다.
  • 아까 잠깐 했던 생각인데, P를 +1, C를 -2로 두고 누적 합한 다음 좌표평면에 플로팅해봅시다.
  • PCP는 처리할 수 없는 것이 자명합니다.
  • 만약 플로팅한 것 전체가 y=0을 기준으로 한 쪽에만 있다면, 봉우리를 없애는 느낌으로다가 지우다 보면 됩니다.
  • ‘봉우리를 없애는 느낌’이 안 먹히는 경우를 생각해 봅시다. 일단 y=0에 점이 찍히는 것들을 기준으로 나누어서 생각하는 것이 편합니다.
  • 한 쪽에만 있지 않더라도, 그 구간은 y=0 위에 점을 안 찍으므로 대충 풀 수 있을 것 같습니다.
  • 여기서부터 증명하지 않고 구현해봤고, 개쩔게도 바로 맞았습니다. 이로서 본대회 기준 1등을 가져왔습니다.

3:26~4:00

  • jununu와 equinox에게 자랑질을 하며 불닭을 하나 먹고 코포를 치러 갔습니다. 감사합니다.

Seoul 2024

혼자 돌아본 ICPC 셋 중 가장 고생한 것 같습니다. 사실 셋을 돌기 이전에도 많은 정보를 들었기에(다른 건 딱히 기억이 안 나지만, C의 악명 정도는 알고 있습니다), 큰 의미를 두지는 않았습니다. 그냥 ‘어짜피 언젠가 돌 거면 지금 돌자’란 마인드로 돌았습니다.

0:00~0:10 (A +)

  • A번부터 읽기로 했고, 마침 A가 바로 보였습니다. 그냥 나이브하게 짜면 됩니다.

0:10~0:29 (B +)

  • 순서대로 B를 읽었고, 쉽지 않아 보여서 C, D까지 읽다가, B를 풀 수 있을 것 같아서 B로 돌아왔습니다(???).
  • 색깔을 정점으로, 카드를 간선으로 보면, 간선 하나에 정점 하나를 대응하는 문제가 됩니다.
  • 이는 연결요소로 묶어서 트리인지 아닌지 간선 개수만 확인해주면 바로 해결할 수 있음이 웰논입니다.

0:29~0:45 (L +)

  • C, D 둘 다 에바인 것 같아서, 뒤로 가서 L부터 봤습니다.
  • 좋은 선택이었습니다. 두 점을 고정하면 남은 한 점이 극단적일 때가 최대나 최소나 이득이라는 것을 알 수 있습니다.
  • 8가지 삼각형의 넓이를 비교해주면 됩니다.

0:45~1:23 (J +1)

  • 뒤부터 보고 있었으니 다음은 K입니다. 근데 이건 모르겠어서 J를 봤습니다.
  • 어차피 왼쪽 끝 로봇과 오른쪽 끝 로봇이 만나야 되니까, 제일 왼쪽에서 오른쪽으로 정보를 이동시킬 수 있는지 체크하면 됩니다.
  • 그러면 연료량을 대충 이분탐색하면 바로 구할 수 있습니다.
  • 안 됩니다. 중간에 점을 하나 잡아서, 그 왼쪽에서는 오른쪽으로, 오른쪽에서는 왼쪽으로 오도록 하면 연료를 조금 더 아낄 수 있을 수도 있습니다.
  • 맞았습니다.

1:23~2:21 (K +1)

  • 다시 K를 읽어봤습니다.
  • 결국 늘릴 수 없는 substring을 만드는 것이 중요한 것 같습니다. 이는 그리디하게 $O(26N)$에 할 수 있음이 웰논입니다.
  • 그러한 substring 중 가장 긴 것을 찾습니다. 그 단어보다 짧은 범위에서는 그 단어 때문에 계속 Q가 바뀌는데, 그것보다 길어지면 그 단어는 안 늘어납니다.
  • 그래서 이케이케 잘 짜면 됩니다.
  • 까지 생각하는 데 매우 오래 걸렸고 힘들었습니다. 풀고 나니 대회 절반이 날아가서 꽤 절망적이었습니다.

2:21~4:32 (F +3)

  • 이게 본대회에서는 그렇게 많이 풀렸다는데, 저는 하나도 모르겠습니다.
  • 어쩌다 보니 복잡한 솔루션이 나와서, 그냥 빨리 내자는 마인드로 대충 냈습니다.
  • 그러고는 상수를 열심히 잘라주니까 몇 번 안 가서 맞긴 했습니다만…
  • 로컬에서 모든 케이스를 충분히 돌릴 수 있는데도 무지성 제출한 건 너무 생각이 없었던 것 같긴 합니다.
  • 많이 힘들었습니다.

그 이후

  • 어차피 문제를 더 풀 순 없을 것 같아서, 이 블로그를 완성했습니다.

저는 아직 송도에서 같이 ICPC 팀셋을 돌 사람을 찾거나 만들지(?) 못했습니다. 매번 시간이 나는 것은 수요일 저녁 시간대이고 그 시간대에 다른 학교의 친구들을 부르는 것은 더 힘들기에, 일단은 계속 같은 시간대에 혼자 셋을 돌고 있습니다.

사실 혼자 ICPC 셋을 도는 것에 대한 장점도 존재합니다.

  • 제가 요즘 블로그 등에서 밀고 있는 생각입니다. 제가 교내에서 팀을 결성할 경우 당분간은 팀 내에서 유의미하게 가장 잘하는 사람이 될 확률이 높아 보입니다. 성적을 잘 내려면 플래티넘 이하 정도의 문제는 빠르고 확실하게 넘겨서 어려운(다중하위 혹은 그 이상) 문제들에 쏟을 시간을 확보하는 것이 중요하므로, 이를 연습하기에 매우 확실하고 좋습니다.
  • 저는 OI나 코드포스는 많이 했지만 ICPC 형식은 아직 부족합니다. OI와 ICPC는 꽤나 스타일이 다른데, 이를테면 WA에 대한 패널티가 없고 가장 마지막으로 점수가 바뀐 시간을 기준으로 등수를 나뉩니다. ICPC에서는 그만큼 제출이라는 행위가 자유롭지 못한데, 저는 짜고 나면 일단 제출하고 보는 것에 너무 익숙해서 ‘제출 전에 코드에 실수가 없는지 확인하는 과정’이 많이 부족합니다. CERC E와 L, PPC H에서 절었던 것이 그 예시이겠지요. 혼자 ICPC를 하다 보면 이런 문제가 매우 적나라하게 드러나며 그에 대한 punishment도 크기 때문에 꽤 좋습니다.
  • 플레 정도 난이도 문제를 푸는 속도를 향상하는 데 좋습니다.

그러나 단점도 명확합니다. 원래 3명이서 돌아야 될 셋을 혼자 돌기에 생기는 당연한 문제들이 많습니다.

  • ICPC의 몇몇 특성적인 역량을 연습하기 어렵습니다.
    • 쉬운 문제 발굴해 풀기: 1인 체제는 3인 체제에 비해 초반에 느릴 수밖에 없습니다. 그러다 보니 제 속도보다 스코어보드 속도가 많이 빨라서, 거의 대회 시간 전체를 슥보에 풀린 다음 문제를 따라가는 형식으로 진행하게 됩니다. 즉, 1인 ICPC는 사실상 정렬된 ICPC 세트를 혼자 푸는 것에 가깝습니다.
    • 어려운 문제 함께 풀기: 작년 RUN ICPC Mock에서 느낀 것인데, 어려운 문제 함께 풀기는 꽤나 문제를 풀기에 좋습니다. 그걸 연습할 길이 없습니다.
    • 컴퓨터 스케줄링 연습하기 + 컴퓨터 없이 디버깅 연습하기: 네. (전자는 연습이 필요한 무언가인지 잘 모르겠지만, 후자는 매우 중요한 역량인 것 같습니다.)
    • 실제 대회에서는 팀원들이 꽤 많은 문제를 풀어줄 것인데, 그런 상황을 시뮬레이션할 수가 없습니다.
  • 다이아 이상 난이도 문제를 푸는 연습을 하기에 좋지 않습니다.
  • 뭐 하나도 떠넘길 수가 없습니다. 특히 맞왜틀을 같이 해줄 사람이 없습니다.
  • 존나 힘듭니다.
CP, ICPC
cp icpc ps
This post is licensed under CC BY 4.0 by the author.