pizzaroot
ICPC Seoul Regional 2023 본선 후기 본문
pizzaroot 의 올해 ICPC는 작년에 같이 나갔던 형 한명 wlsth1004100 과 동아리에서 발굴한 새로운 한명 javago 와 같이 나갔다.
나는 수학, 기하, 애드 혹, DP, 조합론, 정수론 담당이였고
wlsth1004100 는 이제 그래프, 구현, 템플릿 담당
그리고 javago 는 이제 애드 혹, 게임 이론, 그리디, DP 담당이였다.
예비소집날에는 건대 팀 Ilgam Rangers, Saenaegi 와 함께 저녁 식사를 했다.
우리는 Default 라는 팀명으로 세종대에서 나왔다.
팀노트는 그동안 한번도 사용한 적이 없지만 보험용으로 잘 만들어서 갔다.
사실 예선 성적이 기대보다 많이 높게 나와서 본선 기대치가 많이 올라간 상황이였다.
잠을 잘 잔 후에 커피로 도핑을 한 후 대회장에 입장했다.
시험 시작 5분전 긴장이 된 상태!
효과음과 함께 시작된 대회. 바로 문제지를 열동안 템플릿 코드를 작성했다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
return 0;
}풍선 사이즈를 보니 D가 가장 쉬울것 같다는 예상을 했다. 하지만 나는 A번부터 열심히 문제를 읽었다.
A는 뭔가 문제 읽고 싶지 않은 길이였다.
B는 절대로 읽고 싶지 않은 코드였다.
C는 절대로 쉬워보이지 않는 기하였다.
D는 수학같은데 일단 패스했다.
E는 뭔가 읽기 싫어서
F를 봤다.
문제를 이해 한 후, 그리디하게 뽑으면 될까라는 생각을 했지만 뭔가 아닌거 같았다.
G는 별로 읽고 싶지 않은 카드였다.
H는 전혀 쉬워보이지 않았다.
옆에서 javago 가 J가 쉬워보인다고 했다.
여기까지 보고 나는 한동안 F를 고민하기 시작했고, 5분쯤에 스코어보드를 보니 백지가 보였다.
좀 있다가 다시 보니 D랑 I가 한팀씩 푼 것을 보았다!
하지만 아직 믿지 못한 나는 F를 계속 봤다.
하지만 점점 쏟아지는 D AC에 바로 D를 읽으러 갔다.
그냥 살짝 귀찮아 보였기 때문에 파이썬으로 만들다가 그냥 스택으로 열심히 짰다.
내가 구현이 좀 약해서 그런지 좀 시간이 걸렸지만, 28분에 AC를 받았다!
앞으로 빨간색 풍선을 가장 먼저 풀어야 한다는 교훈을 얻을 수 있었다.
그리고 나는 J번을 열심히 봤고 다른 팀원 2명은 I번을 보는 상태였다.
J번에서 관찰은 K가 2, 3, 5, 7 외의 소인수를 가진다면 곱이 0인 경우만 가능하다는 것이였고, 2, 3, 5, 7의 지수들로 DP를 잘 돌리면 될 것 같았다. 처음에 나온 것은 6차원 DP였고 뭔가 계산을 잘못했는지는 모르겠지만 일단 될거 같았다.
dp[10][21][68][43][30][25]이렇게 한 후 대충 짜고 돌렸는데 메모리가 터진듯 했고 스코어보드에는 푼사람이 없기에 바로 접었다.
이후 G번을 해석해서 wlsth1004100 한테 설명했고, 고민하고 있었다.
나는 다음 풀 문제는 사실 잘 몰랐지만 이미 J 고민에 80분정도 썼기 때문에 그나마 많이 풀린 B를 보고있는 javago 의 풀이를 들어보았다. 그의 풀이는 다음과 같다.
"접근을 못하겠다"
문제를 보니 어지러웠다.
어지러운 코드를 열심히 해석했더니 마지막 swap 전 상태는 바로 알 수 있고, 그 다음은 나머지는 요세푸스 문제처럼 세그트리를 돌리면 된다는 사실이다.
따라서 상태 세그트리 배열을 두개 복사해서 이분탐색을 돌려서 풀었다. 그동안 wlsth1004100 는 G AC. 남은 시간 동안 H를 보고있는 나머지 팀원과 B를 디버깅하는 pizzaroot
그리고 212분에 바로 AC.
남은 시간은 88분.
M. S. I. S.
결국 못 풀었다!
기대 했던 것 보다 못해서 기분이 좋지는 않았다.
하지만 생각보다 프리즈 후에 등수가 1등밖에 안떨어져서 등수는 37등으로 마무리.
작년 42등보다 5등 올랐다. 나쁘지 않다.