[editorial] Nasa-Topcoder MM 후기

  • 일루
    일루

    Provisional score : 720.42예상 등수: 30~40등 정도?
    문제 설명 링크는 지금 구할 수가 없네요. 최종 결과가 나오면 나중에 달도록 하겠습니다.
    처음 4일: 좀 놀았습니다 ㅠ.ㅠ 사실 부족 도끼가 총 3000개가 오네여 -_- 막느라 아무것도 못함
    D-6: 문제와 포럼을 읽었습니다. 어라, training data와 provisional data와 final data가 다르네요. 음.... final data가 꽤나 중요할 것 같단 느낌을 받았습니다. 어떤 방법으로 짜야 training data에 과최적화되지 않게 할 수 있을까? 여기서부터 이제 데이터 분석에 들어갑니다.
    D-5: 각 이벤트에 쓰이는 리소스와 각 리소스에 쓰이는 이벤트들을 정리해봅니다. 음.. 이벤트별로 쓰이는 리소스들이 많습니다. 만만치 않네요... 이제 한번 각 이벤트의 best/worst 발생 분포를 살펴봅니다. 뭔가 규칙성이 있는것 같으면서도 없는 것 같으면서도. 잘 모르겠네요.
    D-4: 어떤 방법으로 구현해볼 것인지를 구상해봅니다. 기본적으로는 어떤 답이 있다고 할 때, 리소스를 추가해보거나 빼보거나 하면서 확률을 계산해나가면서 최적화를 해보려고 했습니다. 그러려면 현재 리소스 상태에서의 평균 탈출 횟수를 구해야하죠. 이걸 빠른 시간에 구하는 모듈이 있는 것이 무엇보다도 중요하구나 라고 생각했습니다. 사실 현재 리소스를 가지고 10만개에 대해서 다 돌려보니 이건 완전 시간이 엄청 오래 걸리고 데이터 오버핏도 많이 될거 같아서 기각..
    D-3: 이벤트에 따라서 이항분포나 포아송 분포를 따르는 것 같습니다. 근데 best는 그렇다 쳐도 worst는 잘 모르겠네요. 뭔가 새로운 분포를 따르는 것 같습니다. 어쨌든 이벤트들이 서로 연관되어 있으면 걍 미션을 통째로 사용하는 수밖에 없으므로, 연관성을 분석해봅니다. 근데 연관성이 없네요. 그러면 이벤트 단위로 분석을 더 해봐야겠단 생각이 들었습니다. 이제 이벤트를 각 시나리오별로 뽑아서 분석해봅니다. 또한 어떤 리소스는 아예 싣지 않는 것이 좋겠단 생각도 했습니다. 대략 수십개를 표시해봅니다. (이건 결국 안쓰였습니다 ㅠ.ㅠ
    D-2 아침: 일단 휴가를 내서 방에 틀어박혔습니다. 방법을 '빈 상태에서 미션(이벤트 사이는 독립적이므로 각 이벤트는 랜덤한 미션에서 뽑아옵니다) 하나씩 처리할 수 있도록 리소스를 계속 실으면서, 현재 확률 * 실은 리소스의 가중치 가 최대치가 되는 것으로 정한다' 라고 대략 정했습니다. 이거 빼고는 저 가공할만한 검색공간을 처리할 방법이 없어보였습니다.
    D-2 이른오후: worst가 어떻게 발생하는지 알아봅니다. 시나리오 분석 결과, worst가 한번 발생하면 연속적으로 발생하는 경향이 있고, 각 이벤트의 처음이나 마지막에서 발생하는 확률이 두 배정도로 높으며, worst가 두개 발생하면 한개 발생하는 경우보다 탈출횟수가 2배가 아닌 4배, 3개 발생하면 3배가 아닌 9배가 되는 것 같습니다. 이런것까지 어떻게 처리하지? 라고 생각하다 드디어 포기. 10만개 데이터를 받아서 각 이벤트별로 시나리오를 정리하게 하기로 했습니다.
    D-2 저녁: 위에서 서술한 방법대로 코딩을 해봅니다. 방법 자체는 그리 어렵지 않았습니다. 그리고 확률계산 모듈은 백트래킹으로 구현했습니다. 각 이벤트에 대해 시나리오별로 찾아가다가, 특정 확률 미만이 되면 더이상 검색하지 않고 리턴합니다. 근데 이벤트 갯수가 수십개만 되어도 무지 느려집니다. 음... 난관입니다.
    D-2 밤: 결국 백트래킹에 적절한 컷을 넣기로 합니다. 가벼운 리소스 순서대로 잘라가면서, 서로 연관되지 않은 이벤트 그룹의 크기가 10이 넘는 것이 나오지 않을 때까지 자릅니다. 자른 리소스에 대해서는 사용가능한 최대치를 넣습니다. 나머지 크기 10 이하의 이벤트 그룹에 대해서는 백트래킹을 시전합니다. 이건 사용 가능할 정도로 빠릅니다. 암튼 코드가 최초로 돌아는 갑니다. 한번 제출해봅니다. 아 근데 제출하고 나니 score = 1000 / weight * prob 에서 weight 가 0이면 score가 +inf가 나서 코드가 뻑이 나네요.. 아.. 망했어요 망했어요 망했어요... 근데 프로비져널 스코어가 암튼 33점이 돌아왔는데 참 신기합니다;
    D-1 아침~이른오후: 어제 리소스별로 최대치를 넣었더니 답이 10~15% 정도 안좋아집니다. 대신 각 리소스별로 (리소스가 이만큼 있을때 이 리소스의 부족과 관여되어 생기는 평균 탈출횟수)를 구하는 코드를 만들어서, 바이너리 서치를 통해 각 리소스 별로 (주어진 횟수 p에 대해, 저 횟수 p 미만의 추가가 일어나는 최소 리소스)를 구합니다. 이제 어제의 최대치 넣는 부분 대신 이 리소스 양을 넣는 것으로 바꾸고, 대신 예상횟수를 그만큼 증가시켜줍니다. 그리고 리소스 선정 기준을 약간 개선했습니다. 오버헤드가 10~15%에서 2~5% 정도로 많이 감소하네요. 이 버젼으로 제출해봅니다. 558.33점이 나왔네요.
    D-1 오후: 원랜 리소스들을 추가하다가 이전 답에서 오버가 되면 걍 싹 비웠는데, 이젠 그 이벤트만 제외하고 다시 다른 이벤트를 적당한 횟수까지 넣어봅니다. 이거 했더니 이터레이션 수는 극심하게 감소했는데 점수가 퀀텀점프하네요;; 결과는 꽤 좋아졌지만 어쨌든 이터레이션 수가 많이 부족해진 것은 사실이므로 그리고 속도개선을 이차저차 해서 한 2배 정도 했습니다. 이 버젼으로 내봅니다. 670.89점이네요.
    D-1 밤: 정신이 대략 멍해집니다. 지금 돌이켜보면 결과에 너무 만족했던 것 같습니다. 시간이 좀 더 있었으면 수정할 것들도 있었는데.. 아무튼 확률계산이 좀 과대평가되어있는 것 같아서 수작업으로 좀 줄여주고, 속도를 이리저리 해서 3~4배 정도 빠르게 했습니다. P가 큰 경우에는, 99% 확률로 30점을 받는 대신 70% 확률로 60점을 받는 것을 프로그램이 선호하는 경우들이 등장합니다. 50개 테스트셋에 대해서 돌려보니 점수가 694.77->780.59로 85점 상승합니다. 하나 실패했는데도! 현재 프로비져널 1등이 806점인걸 볼 때, 순위권에 진입하는 것이 상당히 희망이 있어보입니다. 아무튼 마지막엔 새로운 방법에 도전해보기는 힘들다고 생각해서 여러 데이터와 관계없는 파라미터 조정을 하고, 코드 최적화를 하고 gpl 달려있는 랜덤넘버 제네레이터를 좀 적절히 수정해주고 이러다보니 시간이 다 가네요. 밤 2시에 제출했습니다.
    오늘 아침: 아침에 결과를 보니 720.42점이 나왔네요. 확실히 기대이하 ㅠ.ㅠ 20위권이 754점인데 여기 들기도 힘들고 망했단 생각이 절로납니다 냐하하.. 이럴줄 알았으면 어제 밤에 좀 더 고민해볼걸 ㅠ.ㅠ 하지만 애초에 코딩 시작이 너무 늦었단 생각도 납니다.
    타임라인과 관계없는 약간 더 자세한 방법 설명은 아래의 탑코더 게시판에 올린 글을 봐 주세요 :) 한글로 다시 쓰기 흑흑 ㅠ.ㅠ
    http://forums.topcoder.com/?module=Thread&threadID=655680&start=45&mc=46#1164227

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    9년 전
3개의 댓글이 있습니다.
  • A.I
    A.I

    등록은 해 놓고 이것저것 바빠서 submit도 못 했는데... MM은 아무래도 한번 붙잡으면 참 재밌으나 시간내기가 힘드네요. :(


    9년 전 link
  • ltdtl
    ltdtl

    저도 한 줄 후기: 그냥 리소스 필요한 만큼 다 쳐넣었더니 470점 정도 나오더군요. 끝. - _ -;; 아싸 티셔츠.


    9년 전 link
  • nocut98
    nocut98

    [여러줄 후기]
    일단 이번 MM은 티셔츠 때메 시작은 해야 하나 토요일 오전에 6개월 정도 공들인 중요한 일이 있어서 컨디션 관리 등등으로 어짜피 제대로 못하겠다는 생각이 들었습니다(다 각자 일이 있고, 저도 항상 그래왔지만 이번엔 하필 마감도 일요일 3시...ㅜ.ㅜ)
    저의 코딩 시간을 크게 2파트로 나누면, 월화수, 토요일 이렇게 나눌 수 있는데요.
    월화수에는 기본적인 템플릿 코딩해놓고 위에 리토도님처럼 필요한 리소스 다 때려 박아 놓으니 470점 근처로 나오더군요 일단 휴식
    그리고 토요일 전에는 데이터를 엑셀로 정리해서 분석만 했는데, 탈출이 주로 후반에 발생하더군요. 쉽게 말해서 리소스는 쓸꺼면 아예 끝까지 쓰고 안 쓸꺼면 아예 안 쓰는 전략이 괜찮다는 깨달음을 얻었습니다(이번 MM에 간신히 하나 깨달은 사실이고 이것에 기반해서 알고리즘을 구성했습니다)
    드디어 토요일날 일을 끝내고 오니 3시..일단 한숨 자고 일어나서 5시쯤부터 커피숖에 앉아서 코딩을 시작했습니다.
    토요일날 한 것은 주로
    1. 어떤 리소스들끼리 클러스터링을 하면 점수가 잘 나올지 -> 그냥 부피당 탈출횟수 효율성이 좋은 것부터 넣었습니다. Eva 다 찰때까지요
    2. 리소스 셋을 선택시 결과가 빨리 나오도록 최적화
    이렇게 하는 게 짧은 시간에 최대의 효과를 거두는 것이라고 믿었습니다
    하다보니 토요일 저녁 약속은 자연스럽게 째지더군요 간만에 이성들과 어울리는 자리였는데...흙
    이렇게 한 10시까지 하고 조금 더 효율을 좋게 하기 위해서 새벽까지 이것 저것 사소하게 바꾸어봤는데 별 차이 없더군요 -.-
    결국 마지막에 2시 59분에 제출했습니다...컴퓨터가 느려서 제출 못할 뻔;;; 뒤에서 4등했더군요.
    아침에 일어나서 점수보니 670점이었고, 우리방은 경쟁이 치열해서 방 4등 중에서는 제일 높은 점수였습니다 -.-
    개선할 점은
    1. 리소스의 표준편차를 이용하여 좀 필요없는 애들은 깍아주거나...(지금은 최대치를 반환)
    2. 표준편차를 이용해서 P에 좀 더 잘 맞추기 (지금은 그냥 P에다가 0.83을 곱하고 그 수치에 맞추기 때문에 P가 낮으면 0점이 나오고 P가 높으면 P를 충분히 활용하지 못하는 상황)
    어쨌건 저도 티셔츠를 받게 되어 기쁩니다 ^^


    9년 전 link
  • 댓글을 남기시려면 로그인하세요.