안녕하세요!
이전에 ACPC 예선을 치뤘다는 글을 올렸었는데, 오늘은 ACPC 본선에 가게되어 대회를 치루고온 후기를 적어보려합니다!
AWS본사로 가봅시다.
이번 ACPC 본선은 서울에 있는 AWS 본사에서 열려요. 약간 애매한 시간에 입장이 마감되기에 광주에 있는 저는 전날 올라가서 있는 편이 여러모로 좋지만, 이번에는 그냥 일찍 올라가기로 하였어요.
아침 5시 30분에 일어나 버스를 타고 역삼역에 있는 센터필드로 갔습니다.
AWS 본사는 센터필드 18층에 있었는데 막 뭔가 구경할 시간은 없었고(구경 할 수도 없었고? 어쨌든 회사니까) 바로 준비해주신 티셔츠로 갈아입고 명찰을 착용한 뒤 대회장으로 이동하였어요.
보니까 대략 90명정도가 참여한 것 같던데, 일단 전남대는 저 혼자 뿐인 것 같았어요. 제가 아는 제 다음 순위 분도 예선을 잘보셨는데 선정 방식이 좀 특이했는지 떨어지고, 어쩌다보니 학교 대표가 되었습니다.
본선
본선은 오후 1시부터 5시까지 총 4시간 동안 치뤄졌어요.
다른 대회와 달리 스코어보드가 존재하지 않아 사실상 4시간 동안 스스로와의 승부를 하는 느낌이였답니다.
A - 18분 solve
A는 간단한 N^2 브루트포스 문제였어요. 특정 값을 미리 구해둬야하긴했지만, 그렇게 까다롭지는 않았습니다.
분명 간단한 문제는 맞는데, 본선에 대한 긴장 그리고 아침일찍 와서 잠이 부족했던 점, 온도가 조금 추웠던 점 등이 겹쳐 컨디션이 급속도로 안좋아진 탓에 생각보다 너무 오래 걸렸어요.
정황상 A가 가장 쉬운 문제였는데, 이 즈음부터 잘못하면 1솔로 끝날수도 있겠다. 큰일이다는 생각이 들었어요.
B - 1시간 10분 솔브
리스트에서 신기한 형태의 정렬(스왑)을 해야하는 문제였어요.
스왑 대상을 최초에 우선순위큐를 통해 우선순위가 높은 것을 꺼내 스왑을 하고, 그 연산으로 스왑대상이 추가로 생기는 것을 다시 우선순위큐에 넣는 걸 반복하여 풀었어요.
A번에서 컨디션 애매했던 것 치고는 풀이를 꽤 빨리 찾고 잘 푼 것 같아요.
다행히 1솔로 끝나진 않아서 안도하는 한편, 대회 난이도가 생각보다 높은 것 같다 생각하였어요.
당연히 예선에서 잘 푼 사람이 본선에 온것이니 높은게 맞지만 그럼에도 좀 어려운 것 같아요.
C - 2시간 10분 솔브 / 2WA
파라메트릭 서치(이분 탐색)과 냅색이 혼합된 형태의 문제였어요. 냅색을 문제의 구조에 맞게 변형해야 했기에 많이 햇갈렸지만, 종이에다 식을 적어가며 최적화하고 구조를 바꿔서 풀었습니다.
알고리즘은 바르게 짰지만 초기값을 잘못설정하여 두번 틀렸어요.
이때부턴 몸이 적응한 건지 컨디션이 좋아졌어요. 남은 시간이 1시간 50분가량이기에 한문제만 더 풀면 4솔브로 만족스럽게 대회를 끝낼 수 있을 것 같아 서둘러 다음문제를 확인했습니다.
D - 패스
문자열문제이고 읽어보았을때 아마 트라이 혹은 KMP의 실패함수 아님 아예 아호코라식으로 갈 만한 문제라 생각했어요.
뒤에 두개는 노트가 없으면 구현하지 못하기에 일단 트라이라도 구현해봤지만, 그 뒤로 뭔가 아이디어가 떠오르지 않아 패스했어요.
E - 시간초과
트리 형태의 구조에서 서브트리 내부의 연산을 진행하는 문제였어요.
일단 저는 처음보고 빌라봉 과 같은 느낌의 트리 DP일 것 같다 생각하여, 열심히 구현하였는데 아무리 생각해도 N^2의 연산을 최적화할 방법이 떠오르지 않았어요. 상수 커팅을 통해 넘기려는 시도도 해보았지만 계속 51%에서 시간초과가 발생했어요.
대회 끝까지 연산 최적화 방법을 고민하다가 끝났는데, 나중에 들어보니 이 문제가 트라이문제였다네요?! 상상도 못했어요.
결과
앞서 이야기했듯 스코어보드가 공개되지 않아 자세한 등수는 모르지만 3솔브로 나름 만족스러운 결과를 얻었어요.
이후 디스코드에서 알려주신 내용에 의하면 3솔브는 46등~58등 이라하여서 딱 평균정도로 푼 것 같아요.
알고리즘 잘푸는 사람들 사이에서 평균이면 성공적이죠!
못풀만 했네
대회가 종료된 이후에는 보통 솔브드 디스코드에서 문제에 대한 이야기가 이루어집니다. 이번 대회같이 백준에 올라오지 않는 문제도 예상티어가 어디일지 논의되곤하는데, ACPC또한 어떤분 예상티어를 적어주셨습니다.
물론 이 분이 이야기하신게 100% 정답은 아니지만, A번부터 골드3, B번 골드1, C번 플레3라네요.
대회 도중 어렵다 생각은 했는데 이정도일줄은 몰랐어요.
플레3을 풀었다는 것과 플레1 에 시도라도 했다는 사실만으로도 이번 대회는 만족스러운 것 같습니다!
실버?
보면 난이도가 올라가다가 갑자기 G번에서 실버4가 나오는데, 이부분도 이야기할거리가 좀 있어요.
대회 시작한 후 얼마지나지 않았을때, 갑자기 대회문제가 7개가 아니라 8개라고 이야기해주시면서 문제가 하나 추가되었어요.
가장 뒤에 H번으로 추가되었는데, 대회 도중 갑자기 추가되고, G번과 H번의 문제 이름이 같은 것, 그리고 G는 매우쉽고 H는 매우 어려운 것으로 보아 문제가 잘못 배치(또는 누락)되거나, 이름이 같아 다른 문제를 가져온게 아닌가 다들 이야기하더라구요.
이런 경우 스코어보드가 있다면 G가 많이 풀리면서 바로 G를 풀러갈 수 있는데, 이번 대회같은 경우는 스코어보드가 없어, 아마 저처럼 A번 부터 본사람은 G번이 쉽다는 것도 몰랐을 거에요.
4솔브가 많은 이유도 3 + G번을 발견해서 푼 사람이지 않나 싶습니다.
물론 문제를 다 안본건 제가 한 선택이니 아쉬운건 없어요.
마무리하며
일단 저는 이번 대회에 아주 만족해요! 제가 풀 수 있을 만한 문제는(G번삐고) 다 풀었고, 평소에 풀기 어려운 문제도 풀었어요.
사실 저는 대회를 주로 수상보다는 동기부여 목적으로 가곤합니다. 수상하는 사람들을 보면서 '저렇게까진 어렵더라도 나도 더 노력해야지' 하는 느낌과 '내가 이런 문제를 풀었어! 나 좀 성장했네?'이런 느낌? 그리고 이렇게 본선 진출하면 성취감도 얻구요!
오늘도 수상만큼 화려하진 않더라도 aws의 작은 기운을 받아갑니다.
