1. 14

• 
• 삼성 대회 후기...
• 4시간 대회에 4문제. 하지만 각 문제가 꽤 난이도가 있었고 레퍼런스가 없었기 때문에 구현에도 시간을 들여야 했다. 그래서 올솔브가 안나왔고, 타임 페널티가 없고 제출 페널티가 있는 대회였기 때문에 빠른 제출보다도 제출 휫수를 줄이자는 마음가짐으로 편하게 대회시간동안 임할 수 있었다.
• A는 알고리즘 자체는 직관적으로 나오는데, 두 segment의 위치관계를 고려해야 하는 약간은 까다로운 구현이 필요했음. O2 옵션이 적용된다는 걸 대회직전에야 공개한-_-걸 들은 나는 그럼 당연히 C++을 써야지!하고 VS로 구현을 했는데, VS 디버깅 환경이 너무너무나도 익숙하지 않아서 도저히 대회시간안에 적응이 되질 않더라. 우선 실행창에 test case 복붙을 못한다는 것부터... 그래서 파일입출력을 쓰려 했는데 freopen이 알 수 없는 이유로 작동을 안하면서 멘붕에 빠지기 시작했다.. 그래서 VS로 삽질하다가 이대로 안되겠다 싶어 Java로 갈아타고 재코딩, 만점을 받은 게 한시간이 지나고 나서야였다. 어휴..
• B를 읽고나서 바로 매칭이네.. 하고 구현해서 137점은 받아냈는데, 만점을 받기 위해선 flow modeling이 필요했고, 근데 시간복잡도 각은 나오지 않아서 헤메기 시작했다. 시간제한이 무려 0.1초(자바기준 0.5초)라서 10^7대 계산량을 요구하는 거 같았는데 포드풀커슨만 해도 O(Ef)에 E가 5000*100이고 f가 5000까지 나올 수 있었으니.. 도저히 각이 안나와서, 다른 방법을 써야 할 것만 같았다. 그걸 고민하다가 C로 넘어간 게 1시간 30분이 남았을 때 정도.
• C가 94점이 좀 긁힌 상황이라 94점짜리 조건을 생각해 봤는데, 생각보단 알고리즘이 쉽게 떠오르더라. cycle component로 분리를 하면 각각이 곱의 법칙이 적용되니까 각각 MST/최소병목트리의 개수를 쉽게 구해낼 수 있었다. 이걸 구현해서 AC를 받고나니 대회시간이 약 30분정도 남아있었음.
• D는 문제나 읽어보자..하고 들어갔는데 문제가 매우매우 더럽더라 그래서 뛰쳐나오고 B를 다시 잡다가.. 아 이건 도저히 안돼ㅠㅠ하고 GG...
• A만점, B 137점, C 94점. A와 B를 만점받은 사람이 29명이므로 수상권 밖이었다ㅠ_ㅠ.. 나중에 B를 들어보니까 포드풀커슨이든 디닉이든 flow modeling을 해서 어떻게 탐색순서를 바꿔가며 돌리면 만점이 나온다더라. C는 본격 Kirchhoff's theorem문제.. Kirchhoff를 겉핥기로 알고 있었던 나는 이걸 풀 각을 마련하지 못했다고 한다ㅠ_ㅠ...
• 수상권은 페널티가 적은 AB만점이 5등상, AB만점+C긁기가 4등상, ABC만점이 3등상, ABC만점+D긁기가 1,2등상을 가져갔던 것 같다. C긁기에 성공했으니 B를 맞기만 했어도 4,5등상은 노려볼 만 했는데... 하는 대회 끝나고서의 아쉬움이 남음 -ㅅ-
• 생각보다 알고리즘하는 사람들이 많다고 느꼈고, 잘하는 사람들도 많다는 걸 느꼈다. 겉핥기로 알고있는 주제들을 구체적으로 습득하는 것도 중요하다고 느꼈다. 하지만 삼성이 O2를 대회시작직전(!)에야 말해준 건 매우 악독하다고 생각한다-_- 내겐 매우 critical한 조건이었고(STL을 쓰느냐 못쓰느냐=C++을 쓰느냐 못쓰느냐) 대회에 큰 영향을 끼친 조건이었는데...ㅠㅠ 게다가 심지어 채점환경은 g++인데 코딩환경은 VS만 된다는 게 말이나 되냐고!ㅠㅠㅠ
• 또 시간복잡도 각이 flow에선 매우 유연하게 적용된다는 걸 느낀 셋이였다. B만점이 29명이나 됐는데, 나도 어떻게 비벼볼 수 있지 않았을까...ㅠㅠ