2020 ICPC 인터넷 예선 후기

올해는 병특으로 근무중이여서 재학생이 아니기 때문에 어처피 본선은 못 나가고, 작년 Little Piplup 팀에서 나랑 같은 휴학생 처지가 된 Coffeetea, Diordhd와 한 팀을 꾸려서 나가게 되었다. 결과는 생각보다 괜찮았던 7솔브! 비록 A랑 J가 풀만했지만 풀지 못했던 게 조금 아쉽긴 해도, 대회 중에 문제 솔루션이 끊임없이 나왔고, 구현도 큰 코딩 실수 없이 생각했던 걸 (J 빼고) 모두 빠르게 구현해내서 좋은 결과를 얻을 수 있었던 것 같다.

대회 중 역할분담은 주로 Coffeetea와 Diordhd가 솔루션을 생각해서 전달해주고, 그걸 내가 받아서 구현하는 방식이였다. 우리가 푼 문제 한정으로 솔루션은 koosaga.com/262 와 대략적으로 일치해서, 여기서는 솔루션을 자세하기 설명하지 않겠다.

Timeline

0:07 - I AC.

Coffeetea가 프린트하러 간 사이에 나랑 Diordhd랑 민 문제. 스코어보드에 0분째부터 푼 팀이 있고 그 뒤로도 제출한 팀 중에 틀렸던 팀이 없었던 것 같은데, 이게 정말 큰 힌트였다. 이걸 보고 바로 정해를 떠올렸고, 증명을 요구하는 Diordhd를 무시하고(???) 그냥 코딩해서 AC. 사실 증명은 잘 모르겠다. ㅋㅋ!!! 너무 PS절임뇌답다..

0:13 -  E AC.

Coffeetea가 프린트하러 간 사이에 나랑 Diordhd랑 민 문제(2). Do you know DSU? 배열 최대 크기 잘못 입력해서 한번 틀렸다ㅠㅠ

0:50 - K AC.

. 다익스트라를 사용했다. 정확히 MN개의 노드만 있으면 되고, 간선은 a -> b로 갈때 b위에 써져 있는 숫자를 간선의 weight로 사용하면 된다. 

1:03 - F AC. 

내가 K를 구현하는 동안 Coffeetea랑 Diordhd랑 같이 솔루션을 생각했고, 내가 K를 풀자마자 바로 컴퓨터 교체해서 Coffeetea가 구현해서 맞았다. 옆에서 들은 걸로 보았을때는 직관적인 솔루션을 증명하는 것이 매우 힘들었던 것 같다ㅋㅋㅋ 나는 대회중에 문제를 읽지 않았다.

1:12 - L AC. 

E랑 K사이에 한번 오답을 제출했었는데, 이때는 O(n)그리디가 된다고 잘못 생각했었다. ("3 OOX OXO 1 2"가 반례) 이 뒤에 Diordhd랑 토의해서 반례가 있다는 걸 깨닫고, 첫 번째 특수문자? 를 n+1개의 위치에 삽입해 보고 두 번째 특수문자를 그리디하게 넣는 방식으로 AC.

1:50 - H AC. 

Coffeetea가 노드에 컬러링을 하는 방식으로 Cycle detection을 할 수 있다는 걸 깨달아 넘겨주었고, 내가 DFS를  통해서 그 cycle을 construction할 수 있다는 사실이 어렴풋이 생각나서 내가 구현을 잡았고, 생각보다 오래 걸렸으나 다행히 1트에 AC.

2:20 - D AC. 

Diordhd가 세그트리 6개를 사용해서 풀 수 있다는 사실을 깨달아 넘겨주었고 내가 구현을 잡았다. 도중에 DP정의가 좀 헷갈려서 오래 걸렸다. 이것도 1트 AC를 했다는 사실이 너무 놀라웠다.

2:52: J WA.. koosaga 블로그의 첫번째 풀이를 Diordhd가 찾아서 전달해주었으나, 내가 구현을 잡아서 이걸 Fenwick도 아닌 Order Statistics Tree로 풀었고, 거기에다가 대회 중에는 구현 실수로 WA를 받았다. 대회 종료 10분 후에 구현 실수를 찾았으나, 백준에 제출해보니 TLE.. 첫번째 솔루션을 Fenwick으로 최적화할 생각을 했었거나, 더 빠른 알고리즘을 썼었어야 맞는 것 같다..SCPC에서도 OST를 향한 맹신 때문에 한방 얻어먹었었는데, 이제는 정말 좀 조심해야겠다.. :blobsad:

 

끝! 오랜만에 PS를 정말 몰입해서 재미있게 할 수 있는 기회였어서 너무 재미있었다. 병특 끝나고 학교로 돌아올때쯤엔 정말 본선 진출 한번은 해볼 수 있겠지..?