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