7개의 댓글이 있습니다.
-
-
Apple_Cplus -
용기내서 알거스팟에들어는데.. 이런 후기가있었네요
수고하셨습니가다 ㅠㅠ
ICPC 는 가슴속에 묻어둘게요 ㅠㅠ
10년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
SINCE 2007
VOCList
xhae입니다.
연세대학교 팀으로 올 해 대전 및 Danang Regional Contest에 참가했는데요. 지난 금요일(2013.11.29)에 있었던 Danang 대회를 마지막으로 올 해 제 ACM-ICPC 일정은 모두 마무리됐네요.
결과는 올해도 아쉽습니다. 물론 결과는 언제나 아쉽습니다(...).
위로가 되는 건, 돌아보면 아쉬운 만큼이나 즐거운 순간도 배운 것들도 많았단 생각이 드네요.
아직 생생할 때 경험담 형태로 남겨봅니다. 여러분도 일기는 자게에...
###Danang?
위아래로 2천키로쯤 뻗어있는 베트남 한 가운데 있는 도시로 베트남에서 비교적 근대화가 많이 진행된 장소입니다. 북쪽에 Hanoi, 가운데 Danang, 남족에 Ho-Chi-Minh-City 해서 베트남 도시 삼대장같은 느낌이네요.
본래는 관광과 경치로 유명한 장소라고 들었는데, 제가 갔을 때는 한 달 전에 지나간 큰 태풍탓에 사진에서 본 에메랄드빛 바다랑 강물은 하늘나라로... 여름에 참 이쁘답디다. 겨울(대회 시기)엔 어... 비가 좀 오네요. 이게 시도때도 없이 옵니다. 막 옵니다. 펑펑 쏟아지다 30분이면 그치다 두시간뒤에 또 오다 또 그치다 또... 계속... 어... 옵니다. 좀 삼한사온같이 오는건지 마지막 2일은 비구경 별로 못하긴 했는데 그래도 양일 다 오전에 한번 쏟아붇긴 했네요. 관광이 마지막 이틀동안이어서 다행이었습니다. ㅠㅠ
최저/최고온도가 18/24쯤 되는 시기라 춥거나 하진 전혀 않고요. 반팔에 얇은 재킷하나 걸치고 체류 내내 잘 지내다 왔네요. 제비들이 괜히 남쪽나라 가는게 아니고...
물가는 항목별로 한국 1/3 ~ 1/2쯤 돼요. 대회 전 후로 가볍게 여행다녀오긴 좋은 물가인듯.
###대회 환경
해외팀에 신경을 많이 써주는 편입니다. 팀마다 현지 자원봉사 가이드가 한명씩 붙어서 공항 마중부터 대회 종료까진 물론이거니와 심지어 이후에 팀에서 자체적으로 가는 투어까지 오셔서 여행지 추천이나 번역을 도와주시네요. 물론 이게 사실 베트남이 가이드 없인 호텔에서 한발짝 나가기도 참 힘들어서 그런거같기도 한데... 전국민 1인 1오토바이 국가라 그런지 택시 말곤 대중교통을 본 기억이 없는데 택시들이 영어를 저언혀 못해요.
가이드 외에도, 공식 일정에 대회 후 자체 진행하는 지역 투어도 해외팀만 참가하고 디너도 예비소집/당일 두 번 있었네요. 팀 소개도 해외팀은 팀별 / 자국팀은 학교별. 이쯤되면 거의 역차별...
챙겨주는 거랑은 별도로 실제로 우리나라 팀 입장에서 그렇게까지 많이 편하냐 하면 그건 아닌 것 같습니다. 일단 식사가 입에 안맞는 분들이 꽤 있네요. 전 가리는 음식이 없는 편이라 배부르게 잘 먹고 다녔는데 그래도 돌아갈 즈음엔 뭔가 밥같이 안정감있는(?) 식사가 좀 생각나긴 하네요. 음식이 입에 안맞는 분들은 저보다 더 고생하셨고...
말이 통하지 않는 부분도 생각보다 많이 답답했습니다. 제가 태어나서 말이 통하질 않는 나랄 처음 가봐서... 그래도 영어랑 손발이면 얼추 되겠거니 하고 간건데 음 택시에서 공항가자고 "다낭 에어포트"만 몇번을 이야기한건지 ㅜㅜ. 평소엔 그냥 팔다리 잘라놓구 가이드님따라 데굴데굴 굴러다니는 기분.
회장은 King's palace 란 곳을 대여해 진행했습니다. 인테리어가 딱 결혼식올리는 홀이라 물어보니 아니라다를까 결혼식도 한다고. 문제는 여기가 생각보다 정말 많이 좁아서... 111팀이 참가했으니 제가 알기론 이쪽 아시아 리저널중 최대규모인데, 그거 치곤 회장이 꽤 작았습니다. 정말 사람들 냅색해서 회장에 집어넣듯 빽빽하게... 아래 사진.
저 사이로 오며가며 풍선달아주고 화장실가고 프린트전달하고 난리죠 난리.
대회장에 들어가기 전 대기실이 따로 없는 것도 꽤 불편했는데, 여긴 입장을 한 팀씩 호명되면 들어가거든요. 무려 111팀이 입장해야 하는데 입장 전에는 밖에서 군데군데 알아서 모여있다가 한 팀씩... 작년 Hanoi에서는 따로 대기실도 있었다고 하는데 올 해 대회장 시설부분에서는 이래저래 아쉬운 점이 좀 보입니다.
대회 자체는 큰 탈 없이 부드럽게 진행됐습니다. 모 팀이 알고리즘 잘못구현해서 대충짰는데 맞았더라는 카더라도 있기는 한데 적어도 맞은 솔루션 틀렸다고 한 건 아니니 뭐...
###대회
예비소집 때 재밌는 일이 있었는데, A번은 A+B 문제였고 B번은 주어진 스트링 중 두 스트링 이상의 Longest Common Prefix를 찍는 문제였습니다. A번은 읽고 짜고 맞는 문제고 B번은 트라이부터 시작해서 많은 방법이 있을 것 같네요. 우리 팀은 팀노트 테스트도 할 겸 가져간 Suffix Array를 구현해서 제출해봤는데 답변이 안옵니다. 어디가 틀렸나 고쳐서도 내보고 괜히 출력 형식도 바꿔보고 난리 부르스를 춰도 답변이 안옵니다. 이상해서 스탠딩을 잘 보니 B를 제출한 모든 해외팀은 펜딩중...!?
대체 무슨 의미가 있었던건진 아직도 잘...
...
대회 문제 링크
이하 본 대회 후기입니다. 솔루션들이 좀 있을테니 스포일러 / 졸림주의.
시작하고 문제를 잡습니다. 제가 A, 다른 팀원들이 B와 C를 읽어주네요.
A가 크게 어렵지 않은 단순 구현 문제였습니다. 바로 코딩에 들어갔고, 예제가 잘 나오는 것을 확인한 뒤에 제출했습니다.
Run ID 5.
타자 잘 치시는 분들 많구나 하고 다음 문제를 보니 다른 팀원이 D까지 읽고 있네요.
E를 읽어봅니다. 한참을 읽는데도 A번 답변이 안와요. 저지단에 일터졌다는 촉이 옵니다. 오늘 대회 사고없이 끝날 수 있을지 걱정이 되네요. E는 대충 0, n - 1번 노드 양쪽에서 다익스트라 돌린 뒤 모든 노드에 해당하는 길이정보를 페어로 만들어서 정렬한 뒤에 터너리서치를 이용해서 풀면 될 것 같습니다. 팀원들에게 E 다풀었는데 코딩에 시간이 걸리는 문제라고 이야길 해 두고 다음 문제로 넘어가려던 찰나 A번 답장이 왔네요.
YES(0:04).
안심하며 다음 문제로 넘어가려는데 First solver가 우리팀이다...?
.............
그렇다고 합니다.
E를 고민하는 새에 다른 팀원들이 H까지 보고 있습니다. 바로 I를 읽었는데, A보다 약간 어려운 수준의 구현문제입니다. 전 직접 숫자를 의미있는 후보만큼 올려보는 작업을 반복했는데, 이 문제를 가장 빨리 푼 서울대 이야기를 들어보니 그냥 10! 가지수 모두 만들어 놓은 뒤에 찾아봤다고... 여튼 바로 풀고 넘어갈 문제이지 싶어서 바로 코딩에 들어갑니다. 맞았네요(0:27). 실제 대회 결과에서도 A번 다음으로 가장 많이 풀린 문제였습니다.
I를 푸는 동안 팀원들 사이에서 J 해법이 나왔습니다. 행렬연산을 이용하는 DP의 전형적인 유형이라네요. 제가 코딩하는 동안 둘이 검토를 끝내놓고 이후 팀원A가 바로 코딩에 들어갑니다. 전 코딩에서 나와 팀원B과 읽은 문제들에 대해서 공유를 시작합니다. 쭉 보니 C가 n이 좀 크긴 한데 그냥 짜는 것 말고 딱히 다른 솔루션이 있는 것 같지 않네요. 게다가 스탠딩에서도 푼 팀이 등장하기 시작... 다음 문제는 이 문제다 싶어서 C번을 봅니다. 대충 설계가 끝나가던 차에 J를 짜던 팀원 A가 일어납니다. 예제가 안나온다고... 일단 코드를 프린트하고 C번이랑 자리 스왑.
간단한 실수가 있었던 모양입니다. C번을 짜던 중 J번을 간단하게 조금 수정해서 예제 나오는 것을 확인하고 제출, WA. 다시 고통받으러 갑니다.
저도 C번 코딩을 끝내고 제출, TLE. 이렇게 C와 J가 동시에 막히게 되면서 대회는 수렁속으로...
각 문제마다 틀렸던 이유를 살펴보자면, C는 n = 10,000,000 인 문제에 대해서 n까지의 소수의 갯수를 구한 뒤에 O(nlgn)으로 해결을 시도했습니다. 문제는, TLE가 난 뒤에 TLE에 대한 이유를 O(nlgn)이라고 생각하지 못하고 앞에 소수를 구하는 부분이라고 생각한 게 원인이었지용. 이 부분 시간을 줄이기 위해서 precalc한 뒤에 소스코드에 10만 단위로 미리 연산결과를 저장해놓은 코드를 제출해도 TLE. 한숨 푹푹쉬며 이걸 sqrt(n) 단위로 잘라보니 소스코드가 너무 커지고... 어으아 하고 있는데 옆에서 팀원이,
팀원B: "형 그거 제가 전에 름에서 에라토네스 체로 구해봤는데 걍 매우 빠르던데, 혹시 아래에 문제가 있는거 아닌가여"
나: "에라토네스 체가 O(nlgn)보다 빠른...가?"
팀원B: "ㅇㅇ"
나: "ㅇㅇ????????"
그래서 테스트를 위해 일단 에라토네스 채로 바꾼 뒤에 아래부분 로직을 다 날려버립니다. WA. OMG...
네 에라토네스 채 많이 빠르네요.
...
평소엔 왠지 메모리낭비같은 느낌이 강해서 늘 루트만큼 돌면서 소수를 구하던게 버릇인데, n = 10^7쯤 되니 이게 의미가 있는 차이가 되네요. 시간제한 넘 빡쎘음..ㅠㅠ
사실 아래부분이 O(nlgn)이 된 이유는 precalc된 결과를 사용하기 떄문이고 실시간으로 소수를 다 구할 경우에는 O(n)만에 바로 답을 알 수 있습니다. 그래서 아랫단을 수정해서 O(n)으로 고쳐 제출하자 YES(2:38) 27분에 YES를 받고 나서 2시간만에 3번째 문제를 해결합니다.
한편...
옆에서 패러랠하게 말리고 있는 J는 모듈러가 원인이었습니다. 어떤 경우의 가짓수를 주어진 숫자 M으로 모듈러를 취한 값을 출력하는 문제인데, M <= 10^12 거든요. 아마 J에 말린 많은 팀들이 이 부분에서 실수를 하지 않았나 싶습니다. 알아채고 난 뒤 이걸 자바로 다시짜야하나 해당 코드를 빅인티저로 바꿔야 하나 고민하다 결국 바꾸기로 하고 짜는데, 멘탈이 살살 빨리는지 코딩도 두어번 실수하고 4번 시도끝에 YES(2:51). 이렇게 10분 간격으로 두 문제를 연달아 풀어냅니다.
아무튼 말리던 문제를 풀어 낸 건 의미가 있는 일이고, 시간은 두시간 남짓 남은 상황. CJ를 풀던 도중 솔루션이 나온 H를 팀원B가 코딩에 들어갑니다.
나온 팀원A와 남은 문제들에 대해서 이야기를 하는데 D가 전형적인 Min-cost Matching 문제입니다. 어 이거 짜면 되겠는데 하고 보니 n = 5000입니다. C에 이어서 n제한이 참 그래요 참... 헝가리안은 없고 그나마 가진건 Edge기반의 MCMF 라이브러리뿐이라 H 코딩이 끝나면 한번 짜 보기나 하고 다른 문제를 봅니다.
B번이 Kirchhoff's theorem이네요. 알지도 못하고 네 풀지도 못합니다 ㅜㅜ. 버리고 다른 문제로.
남은 문제가 E, F, G인데, 처음에 안다고 호언장담했던 E 솔루션은 사실 CJ 말리던 도중에 팀원B에게 챌당합니다. 급 미뤄둘 문제가 되고, 대회 스탠딩을 봐도 끝까지 안풀릴 삘이기에 보니 남은 문제는 F, G. G를 읽어보니 코드잼 2008년 기출과 매우 흡사합니다. 해당 문제 솔루션을 기반으로 본 문제에 대한 솔루션도 제안했는데, 오더를 매기기가 애매하네요. n = 1000인데 단순하게 보면 O(n^4). 문제 조건때문에 확 줄으리란건 알지만 얼마나 줄을지 당시에는 감이 오질 않는데다 코딩도 순식간에 끝날 문제는 아니라 일단 미뤄둡니다. 나중에 한국와서 안 사실이지만 저거 오더 O(n^2)까지 줄어들게 되어서 아마 대회때 짰으면 맞지 않았을까 싶군여.
고민하던 도중 H YES(3:48). 한번에 풀어내면서, H를 최초로 푼 팀이 됩니다.
이때까지만 해도 D가 혹시 헝가리안 없이 MCMF로 풀리지 않을까... 그럼 D풀고(D가 edge ~= 50000개정도) F풀면 7개로 거의 월파권 아닐까 좋아하던 도중 스탠딩이 굳고 바로 D 코딩에 들어갑니다. TLE. 한숨.
바로 포기하고 F와 G를 재어보던 중 현재 스탠딩에서 좀 더 많이 풀린 F에 모든 힘을 쏟기로 합니다. 남은 시간 3명이 F에 붙어서 규칙도 찾아보고 백트랙킹으로 찍어서 관찰도 해 보고 이래저래 봤지만 결국 시간내에 답을 찾아내지 못하고 5문제로 대회를 종료합니다.
헉헉 쓰고보니 짱기네요. 이쯤 돼야 일기답지...
총평하자면 07년 Danang도 그랬고 올해도 그렇고 베트남은 충실한 라이브러리 준비가 여타 지역보다 훨씬 강조되는 것 같습니다. 실제로 월드파이널 진출권은 두 라이브러리의 유무로 거의 판가름이 났고, 07 스트링문제를 Suffix Tree로 시도했는데 TLE가 난 곳이 여기니...
사실 예상했던 바이기도 해서 나름 예년 대회성향을 토대로 라이브러리를 준비해보긴 했는데 적중률은 하늘나라로 ㅜㅜ
여러분도 답이 보이는데 떠나보내야 하는 기묘한 경험 피하시려면 팀노트 잘만드세요. 두번만드세요. 히히
###후기
개인적으론 어쩌면 마지막 ICPC 출전이 되지 않을까 생각하며 출전한 해였습니다.
작년초까지만 해도 팀원을 구하기가 힘들거라 생각해 ICPC 출전을 거의 포기한 상태였는데, 운이 좋게 대회를 좋아하는 두 친구를 만나서 고맙게도 올 해 한번 더 대회에 나와 볼 수 있었네요. 그나마 올 해가 지나면 또 다시 뭉치기 힘들지도 모르는 상황이라, 한번 마지막으로 열심히 해보잔 생각으로 해외 대회까지 의욕적으로 다녀왔습니다.
비록 목표치에 다다르진 못했지만 나름 제 역대 최고성적도 갱신했고(...) 대회중에 말렸던 문제들을 모두 다 풀어내고 다음 문제로 나아간 점에선 여러 면에서 점수를 많이 주고 싶네요.
이제 학기만 잘 마무리하면 되는데말이죠. 대회다녀왔더니 기말까지 2주남았다는게 김트루...
과연 내년에는 후기를 쓸 수 있을까용.
10년 전