2020 ACM-ICPC Seoul Regional 예선 후기

14등!!!

 

ACM-ICPC 서울 온라인 예선 스코어보드가 나왔다.

 

저번 UCPC에 비해 개인 역량도 좋아지고 팀으로써의 합도 잘 맞았다. 그 덕분에 정말 좋은 성적을 받을 수 있었다.

 

이 기세를 잘 이어가 본선에서도 좋은 결과가 있었으면 좋겠다.

 

 

+ 참고로 팀명 INPISA는 인하대학교 유일 피아노 동아리 "인하인의 피아노 사랑"이다.

예로부터 인하대학교 PS는 컴퓨터 동아리보다 인피사가 더 뛰어남이 잘 알려져 있다(?).

 

 

팀원

 

ANZ1217, ik_e, Envil_Saintan

---

타임라인

 

시작 전에 Zoom문제로 대회가 10분 연기되었다.

어디에서 많이 본 상황이라 종이에 "Is It Rated?" 이라고 크게 써서 앞에 있는 카메라에 보여줄까 조금 고민했는데 꾹 참았다.

 

시작하고 등록문제가 있을까 싶어 문제를 쭉 훑었는데, 그런 건 없었다.

바로 문제 셋을 빈 USB에 담았고 ik_e가 프린트하러 나갔다.

 

 

우선 늘 있었던 "짧고 한국어 지문이 있는 쉬운 문제"를 찾았고, I번이 그런것 같아 보였다.

 

단순히 정렬하고 양 끝을 짝지어주면 되는 문제임을 알아냈고 바로 제출했더니 맞았다.

 

0:05 I 정답

 

 

 

잠시 후 문제를 프린트해온 ik_e한테 좋은 소식을 알려주었다.

 

다음으로 한국어 지문이 있는 문제들을 훑어보았고, E번을 잘 읽어보니 단순 Union-Find로 풀리는 문제였다.

바로 구현을 했고, 팀원들은 나머지 한국어 지문이 있는 F, K, L을 봤다.

 

0:14 E 정답

 

 

 

E번을 풀고 나니 Envil_Saintan이 K번이 단순 다익스트라 문제인것 같다고 했다.

내 생각에도 그랬고, 바로 구현에 들어갔다.

중간에 간선의 가중치를 어떻게 설정해야 되는지에 대해 생각이 꼬여 조금 뇌절을 할 뻔 했지만, 다행히 큰 문제없이 맞았다.

 

0:28 K 정답

 

 

 

이제 나머지 F와 L중 뭘 풀지 결정해야 했다.

F를 적당히 훑어봤는데 풀이가 빠르게 나올 것 같지는 않은 문제였다..

 

L을 보던 ik_e가 Ad-hoc 풀이를 나한테 알려주었고, 나한테 풀이를 설명했는데 내가 잘 이해를 못해서 시간이 조금 소요되었다.

결국 이해하고 코드를 작성하던 중에, 이렇게 풀 바에는 그냥 DP로 푸는게 더 쉽고 구현량도 적을것 같아 DP를 이용해 다시 풀었다.

 

1:08 L 정답

 

 

 

기본적으로 풀어야 할 문제들은 다 풀었다고 생각했다.

 

스코어보드를 보니 F가 생각보다 많이 풀려 있었고, "뭔가 있다"고 생각했다.

다같이 이 문제를 보고 있는데, ik_e가 이 문제에서 도둑은 한 방향으로 계속 도망가는게 무조건 이득이라고 했다. (바둑에서 비슷한 상황이 있다고 한다)

 

대충 생각해보니 맞는것 같아 도둑이 각 4방향으로 일직선으로 움직일 때 경찰이 그 전에 도둑의 위치를 막을 수 있는지 여부만 판단하는 풀이를 짰고, 제출했더니 맞았다.

 

1:21 F 정답

 

 

 

나머지 문제들 중 그나마 사람들이 푼 문제들을 훑어보았다.

 

H를 봤는데 간선의 가중치가 -1인 것이 홀수개인 사이클을 찾는 문제였고, DFS 트리를 이용하면 되겠다 싶어서 내가 구현을 시작했다.

 

DFS트리를 만들면서 현재 노드까지의 음수의 개수가 몇개인지 저장해서, back edge가 생기면 사이클이 생긴것이므로 이 사이클에 음수가 몇개인지 확인하는 식으로 구현했다.

 

여기에 더해 한 정점에 2개 이상의 back edge가 존재하면 그 중 2개의 back edge를 사용해 생긴 사이클에서도 음수가 홀수개인 경우가 있을 수 있으므로, 이 경우까지 확인해주었다.

단순히 홀짝만 판별하면 되는 문제니 구현이 크게 복잡하지는 않았다.

 

이 2가지 경우 말고도 뭔가 다른 경우가 있지 않을까 싶어 틀릴것 같다고 팀원들에게 말하고 제출했는데, 다행히 맞았다!

 

1:58 H 정답

 

 

 

나중에 집에 와서 잘 생각해보니 반례가 될 수 있을 것이라고 생각했던 것이 나올 수 없는 경우였다. 아마 틀렸는데 데이터가 약한건 아니었다고 생각한다. (확실하지는 않다)

 

이 때쯤 스코어보드가 프리징되었고, 프리징 직전 순위가 11등이었다.

남은 시간동안 한두문제만 더 풀자고 파이팅을 외쳤다!

 

 

어떤 문제를 풀지 정해야 했는데, D를 보고 있던 ik_e가 이 문제를 O(6 * N^2) DP로 푸는 방법은 알겠는데, 더 줄일 방법을 모르겠다고 했다.

들어보니 좋은 풀이였는데, 이걸 어떻게 줄일까 생각하다가 세그트리를 이용해 구간 최대값을 log시간에 구하면 N 하나를 logN으로 바꿀 수 있다는 사실을 깨달았다.

 

그렇게 내가 구현을 시작했고, ik_e는 다른 문제를 보면서 내 구현이 맞는지 같이 봐주었고, Envil_Saintan은 그나마 많이 풀린 문제들을 봤다.

 

구현이 생각보다 복잡해서 처음에는 제출했지만 틀렸는데, 오타 1번과 잘못된 코드 1번을 고치고 나니 맞았다!

 

2:44 D 정답

 

 

 

이제 시간이 얼마 안 남아 어떻게 해야할지 잘 결정해야 했다.

ik_e가 B를 단순히 이분탐색을 잘 하면 풀 수 있다고 해서 문제를 봤는데, 문제 설명을 다 듣고 풀이를 적당히 생각해보니 시간이 10분 이내로 남았다.

 

결국 내가 이 구현량을 10분만에 완성하기에는 힘들다고 판단했고, 여기에서 마무리하기로 결정했다.

 

 

우리 팀원 모두 정말 최선을 다했고, 후회 없는 결과가 나왔다!