2014 ACM-ICPC Kuala Lumpur Contest 참가 후기

  • mjy0503
    mjy0503

    OriGoGi팀의 mjy0503입니다.
    인터넷 예선에서 학교순으로 3등을 하여 항공비 지원을 받고 2014 ACM-ICPC Kuala Lumpur regional 에 다녀오게 되었습니다.
    공식 홈페이지
    다음번에 Kuala Lumpur에 가실분들을 위해 후기를 남겨봅니다.

    Kuala Lumpur

    말레이시아의 수도로 적도 바로 위쪽에 존재하고 있습니다.
    매우 더워요. 심지어 습해서 기분도 나쁩니다.
    공용어가 말레이시아어, 영어라서 영어가 잘 통하는 편입니다. (발음은 기대하지 않는게 좋습니다)

    그리고 대부분이 오토바이를 타고 다녀서 걸어다니는 사람을 위한 배려가 없습니다.
    보행자 신호등은 작동안하는 것이 대부분이고, 횡단보도도 없어서 길을 건너려면 무단횡단을 해야 됩니다. 게다가 차들은 보행자들 신경도 안쓰고 지나다닙니다...
    한국보다 물가가 싸고, 시내에 큰 쇼핑몰들이 많아서 쇼핑하기는 좋습니다.



    ###1일차
    IIUM이라는 Kuala Lumpur 북쪽에 있는 대학에서 대회를 진행합니다.
    올해는 호텔에 셔틀버스를 보내줘서 셔틀버스를 타고 대회장을 왕복했습니다.
    대회에는 외국팀이 로컬팀보다 많아서인지 진행을 영어로 하며, 스태프들도 영어를 할 줄 알기 때문에 편합니다.

    Opening Ceremony에서는 각 팀을 학교별로 간단히 소개해주고 축사를 한 후, 간단한 다과를 제공합니다.
    그 후 practice session에서는 5문제가 나왔고, 1시간 가량을 줍니다.
    컴퓨터는 대전과는 다르게 운영체제로 ubuntu를 사용합니다.
    대회장은 자리3개에 컴퓨터만 1대가 있는 실습실을 이용하는데, 아래 그림처럼 생겼습니다.
    대회장

    2일차

    아침 일찍 가서 간단히 챙겨주는 아침을 먹습니다. 호텔에서 아침을 먹고 와서 먹지는 않았는데, 빵같은 종류였던걸로 기억합니다.
    입장전에 무슨 문제가 있는지, 몇몇 팀만 따로 부르더니 30분쯤 늦게 대회를 시작합니다.
    이하는 본대회때 있던 일(풀이 포함)입니다.

    시작하고 문제를 봅니다. 총 12문제로, 짧은걸 찾아 읽는데 전부 2페이지 이상입니다 -_-

    팀원이 A 해법을 알겠다며 코딩하기 시작합니다.
    또 다른 팀원은 J의 해법을 찾고 다른 팀들이 빠르게 푼 B번 문제를 보기 시작합니다.
    A를 제출 했지만 WA. 프린트를 하고, 다른 팀원이 J를 코딩하기 시작합니다.

    C번은 간단한 구현만 하면 되는 문제로, 해석을 하니 바로 풀이가 나와서 다른 문제를 봅니다.
    J를 제출하고, YES(0:18)가 나옵니다.

    바로 A 소스에서 틀린걸 찾고 다시 제출을 했는데 또 다시 WA. 풀이를 듣는데 딱히 틀린게 없고, 순위를 보니 다른 팀들도 같이 틀리고 있습니다. 데이터가 틀렸을거라 판단하고 C번을 설명해준 다음에 팀원이 코딩을 다시 시작합니다.

    H를 푼 팀이 보여서 다시 생각을 해보니 MST를 조금만 응용하면 되는 문제라 코딩을 어떻게 할지 생각하는 와중에 팀원이 C번을 제출하고 YES(0:24)가 나옵니다. 그리고 남은 문제중 풀린 문제인 K를 보기 시작합니다.

    H를 코딩하고 제출해서 YES(0:36)가 나옵니다. 그리고 바로 도쿄대가 A가 맞은걸 보고 뭘 틀렸나 소스를 보기 시작합니다. B는 그렇게 쉬운 문제는 아닌지 해법이 잘 나오지 않습니다.

    1시간여가 되었을 때, B 해법이 나오고 팀원이 코딩을 시작합니다. YES(1:28) 동시에 A번은 벨만포드만 돌리는게 아닌 BFS까지 추가해야 풀리는 문제였다는걸 깨닫습니다. 이걸 해결하니 YES(1:29)가 나옵니다.

    5문제를 풀고 순위를 보니 상위권에 위치해있습니다. 근데 1등인 도쿄대는 9문제! all solve의 기운이 팍팍 풍깁니다.

    팀원이 약간의 노가다가 필요한 F를 코딩하기 시작합니다. WA가 나옵니다.
    L을 보던 중 이분매칭임을 깨닫고 F를 출력한 후 L을 코딩을 시작합니다.
    초기화문제로 WA가 한번 뜬 후 YES(2:02)가 나옵니다.

    F는 팀원의 말을 들어보면 문제 description에 불명확한 부분이 있어서 의심되는 부분을 고쳐서 몇번 더 제출하지만 계속 WA. 소스를 봐도 딱히 틀린곳이 안보여서 일단 다른 문제를 보기로 합니다.
    이 사이에 도쿄대는 12문제 all solve를 띄워버립니다...

    G를 좀 더 생각해보니 aho-corasick을 이용한 DP로 풀린다는 것을 깨닫고 코딩을 시작합니다. 이 사이에 팀원이 bit count를 이용한 E번 solution을 냅니다. G번 코딩을 마치고 예제를 넣었는데 예제가 안나와서 출력을 하고 E 코딩을 시작합니다.

    E번을 제출하고 YES(3:45)! 1시간 반가량의 존야를 풀고 YES를 받습니다.

    G는 디버깅을 하다보니 실수한걸 깨닫고 고쳐서 메모리제한으로 WA를 한번 받은 후 YES(4:00)을 받습니다.

    F는 팀원이 의심가는 부분을 고쳐본다고 한 후 제출하더니 YES(4:08)을 받습니다. 단어의 구분이 문장부호로 되어있다고 명시가 되어있는데, 예제에는 부호 다음에 공백이 항상 있어서 그걸 착각했다고 하네요.

    K번은 N이 10^18이라 고생하고 있었는데, modulo 3이므로 파스칼의 삼각형을 분해하는 아이디어를 던져주니 고민을 하더니 코딩을 시작합니다. YES(4:35)

    I번은 시간이 없어서 던지고, D번을 확실하지 않은 방법으로 코딩하기 시작합니다. 역시나 결과는 WA. 거기에 혹시나하면서 grundy number를 추가해서 마지막으로 시도해봅니다. 대회가 끝나고 나서, 결과가 나오는데 YES(4:59)!

    끝나기 1분전 YES를 받으면서 총 11문제를 풀고 대회가 끝났습니다.
    프리징이 된 후 4문제를 풀어 10등근처에서 6등까지 올라오면서 월파 메달권 대학을 제외한 1등을 차지했습니다.

    대회 중간중간 샌드위치랑 과자를 챙겨줍니다. 문제 푼다고 정신이 없어서 먹지는 않았네요.
    도쿄대를 제외하고 11문제가 최대인걸 봤을 때 대회의 난이도 자체는 적당한 것 같습니다. 그냥 도쿄대는 사람이 아닙니다...
    문제들은 기하와 노가다를 심하게 요구하는 문제는 출제되지 않고, 수학적 지식이 필요한 문제들이 많이 출제되는 것 같네요.
    다만, 문제 description이 조금 부정확한게 아쉽습니다.

    대회가 다 끝나면 늦은 점심을 주고 결과가 확정될 때 까지 2시간 가량 쉬게 합니다.
    그 후 Closing Ceremony에서 폐회식, Problem Analysis, Ranking 순으로 발표합니다.
    마지막으로 저녁을 간단히 준 후 모든 공식 행사가 끝나게 됩니다.

    ###후기
    올해는 월파를 목표로 공부하고 있었는데, 마침 인터넷 예선 성적으로 항공편을 지원해줘서 해외 리저널까지 갔다 왔습니다.
    처음 나가본 해외 리저널인데, Kuala Lumpur는 괜찮은 선택이었던것 같습니다.
    환경면에서도 나쁘지 않았고, 문제들도 저희 팀에게는 괜찮았던것 같네요.
    끝나고 3시간 짜리 도심투어가 있었지만 항공편 사정으로 인해 참가를 못했다는게 아쉽군요 ㅜㅜ
    만약, 해외리저널에 갈 생각이 있고 자신의 팀이 수학을 잘한다면 갈만할 리저널인거 같습니다.


    5년 전
5개의 댓글이 있습니다.
  • VOCList
    VOCList

    ㅅㅍㅇㄹ 나우로딩
    베트남-말레이시아-필리핀 리저널군은 거의 매번 디스크립션이 좀 부정확한 문제가 있는 것 같네요. 이쯤되면 리저널 특성...


    5년 전 link
  • Being
    Being

    @VOCList 헐 세터한테 이를거임!


    5년 전 link
  • VOCList
    VOCList

    @Being 인네와는 다르다 인네와는!


    5년 전 link
  • mjy0503
    mjy0503

    스포일러 추가했습니다.
    2주정도 지나서 정확히 기억은 안나지만 최대한 기억을 살려서 써보았습니다.


    5년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

    like


    5년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.