TCO09 Marathon Match Round 3 - BounceOff

문제

세로로 세워진 2차원 공간에 공을 하나 떨어뜨린다. 공은 당연히 중력의 영향을 받아 자유낙하운동을 한다. 이 2차원 공간안에 공이 반드시 지나가야할 타겟이 여러군데 있다. 직선의 장애물을 설치하여 공이 최대한 많은 타겟을 지나가도록 하라

D-13

문제는 모두 이해했다. 

역시 R3답게 문제가 상당히 까다롭게 느껴진다. 물리법칙 구현은 비주얼라이저를 참고하여 구현하면 될듯하긴 한다. 어떻게 해야 좋은 점수를 받을 수 있을지는 전혀 아이디어가 떠오르지 않는다.

Submission 1 - 18.73

ㅋㅋㅋ 첫번째 서밋결과 꼴지를 달리고 있다.

공을 지그재그로 달리도록 아주 대충 구현해봤다. 하지만 결과는 너무 캐 구리다. 어차피 모든 점을 지나지 못할 거라면 장애물의 수를 줄이는게 낫겠다.

장애물을 하나만 설치해봤다. ㅋㅋ 코드는 겨우 3줄!!!! 서밋해보고 싶은데 아까 서밋때문에 서밋을 못한다.

D-12

Submission 2 - 33.65

ㅋㅋ 장애물을 하나만 설치했더니 점수가 세 배로 뛰었다. 하지만 아직 많이 모자란 점수군... 

좋은 아이디어가 떠오르지 않는다.

D-13

Submission 3 - 31.34(22th)

물리엔진을 구현해서 여러가지 시뮬레이션을 20초동안 하도록 고쳐서 서밋을 했다. 점수는 오르긴 했지만 아직 만족스럽진 않아(18.69 -> 31.34) 3줄 코드에 비해 겨우 2배도 안되는 점수라니!! 죽어야지!!

이번 라운드에서도 오덕러쉬가 미친듯이 달리고 있다. 2위와의 격차는 무려 20점!!! 내 점수의 3배!!! 절반 이상의 케이스에서 모든 타겟을 지나가도록 구현을 했을것으로 예상된다. 덕후같은 녀석!!

노컷님은 41점으로 11등을 달리고 계시군.. 나도 분발해야겠다.

- 공이 떨어지자 마자 장애물을 하나 설치하여 공의 진로를 변경하였다.

- 장애물의 각도를 10가지 경우로 조절을 하면서 최적의 솔루션을 찾는다.

- 수평 장애물을 하나 더 설치하는 경우에 대해 수평 장애물의 높이와 첫번째 장애물의 각도를 변경하면서 좋은 값을 찾는다.

지금 부터 할 일

- 새로운 아이디어를 생각해보자

- 머릿속에 있는 휴리스틱을 구현할 방법에 대해서도 생각해보자(구현이 거의 불가능할 듯 ㅠㅠ)

- 물리엔진부분을 좀 더 효율적으로 만들 수 없을까??

Submission 4 - 37.50(14th)

 과감하게 뉴턴메소드를 없애버리고 4차방정식의 근의 공식을 넣었다. 그리고 TLE가 걱정되서 19초까지만 시뮬레이션을 하도록 수정했다. 4차방장석의 근의 공식을 넣으면서 break문을 잘 못 넣는 바람에 두 시간 동안 근의 공식을 잘못 코딩했나 찾아봤다. ㅠㅠ 어쨌든 버그를 잡았으니 다행~~ 뉴튼매소드를 근의 공식으로 고치니 속도가 최소 5배정도 빨라진것같다!! 유후~~~

 

 점수가 상승하긴 했는데 역시 다른 아이디어를 찾아봐야겠다(30.37 -> 37.50)

D-12

Submission 5 - 48.99(13th)

 결혼식 다녀오는 전철안에서 머릿속에 있는 휴리스틱을 구현할 방법이 불현듯 생각나서 집에오자마자 구현해서 서밋을 했다. (구현하는데 3시간 넘게 걸림 ㅠㅠ.. 아직 반 정도 밖에 구현못함!) 아무래도 20초를 좀 더 효율적으로 사용할 수 있는 방법을 찾아야 할 것같다. 이래저래 코드 튜닝을 하고 있긴 하지만 근본적인 대책이 필요하다. (34.06 -> 48.99)

- 시뮬레이션 함수를 수정했다

전체 타겟에 대해 검사하지 않고 주어진 타겟에 대해서만 공이 모두 지나가는지 검사한다

새로 설치한 평행선과 기존에 설치된 평행선 사이에 존재하는 타겟들에 대해서만 검사하기 위한 목적

공이 새로 설치한 평행선 아래로 떨어지면 당시의 상태를 리턴한다

0. 장애물 하나를 여러 각도로 설치해본다

1. 수평 장애물 하나를 가장 높은 곳에 위치한 타겟의 높이에 맞춰서 설치한다

2. 설치한 수평 장애물보다 위에 위치한 모든 타겟을 공이 지나가고 나서 장애물 아래로 내려오는 경우를 찾는다

3. 2번을 만족하는 경우에 대해서만 시뮬레이션을 계속 진행한다

3. 2번을 만족하는 경우 아랫쪽에 수평 장애물을 하나 더 설치하여 시뮬레이션을 해본다

 첫번째 서밋에서 시도해봤던 방법(여러개의 수평장애물을 설치하여 전체 공간을 몇 개의 층으로 나눈 뒤 하나의 층씩 클리어하기)을 제대로 구현해서 한 번 해봐야겠다

D-11

Submission 6 - 42.57(22th)

45.33 -> 42.57

이럴수가!!! 어떻게 점수가 떨어지지.. 로컬에선 엄청나게 성능이 향상되었는데 ㄷㄷㄷ

머릿속에 있던 휴리스틱의 나머지를 구현했다

- 층을 위에서 부터 하나씩 설치하면서 그 층 위에 존재하는 타겟을 공이 모두 지나갔을 때 아랫층으로 진행한다

- 층의 높이를 적절히 조절해 가면서 그 층이 클리어되면 아랫층으로 안되면 윗층으로 백트레킹한다

- TLE를 신경쓰자

- 현재층을 클리어 한 경우라도 기대되는 최대의 점수가 현제 best보다 작으면 아래층으로 진행하지 않는다(가지치기)

- 코드 튜닝을 조금 하였다

- 랜덤을 사용하는 부분에서 메모이제이션을 하여 똑같은 시뮬레이션을 반복하지 않도록 하였다

Submission 7 - 55.86(10th)

42.18->55.86

아~~~점수가 생각만큼 올라주지 않는군. 60점 넘었어야 했는데;; ACRush는 도대체 어떻게 90점을 받은거야!!!!!

최적화를 좀 더 해야겠다.

아까전에 서미션에서 엄청난 버그가 있었다. 당연히 점수가 떨어질 수 밖에.....

엄청난 버그를 고치고 테스트를 하던 중 점수계산 과정에서 잔 버그를 또 발견했다. 내가 계산한 점수랑 비주얼라이저에서 계산한 점수가 다른 경우가 있어 시드 50~100까지 돌려보면서 케이스들을 찾아 버그를 고쳤다.

시뮬레이션을 두 단계로 나누었다. 

- Go3 16초까지: 위에서 부터 층을 하나씩 만들면서 층을 클리어하면서 아래로 내려온다

- Go2 19초까지: 두 개의 층을 랜덤으로 만들면서 시뮬레이션을 한다

엄청난 버그

- 공이 설치한 층 아래로 떨어지면 그 상태를 리턴하도록 했는데, 이때 그 공이 바닥에 튀는 경우가 있다. 이런 경우 그 담음에 새로운 층을 설치할때 새로운 층에서 공이 바운드되어야 하는데 바닥에 바운드 된 리턴값을 사용하기 때문에 싱크가 맞지 않아 엄청난 오류가 발생하였다. 따라서 공이 층아래로 떨어져 바닥에 바운드되는 경우 그 전 상태를 리턴하도록 수정하였다.

머릿속에 있던 알고리즘도 다 구현했는데...... 이 상태로는 최적화를 아무리 잘해도 최종 10위는 힘들다 ㅠㅠ 최적화는 나중에 생각하고 다른 아이디어를 계속 생각해야겠다... 근데 머릿속엔 최적화 생각밖에 안드네... ㄷㄷㄷ

D-10

Submission 9 - 57.17(8th)

어잿밤에 짠 코드를 아침에 일어나서 서밋했다. 결과는 예상보다 많이 올라서 57.17!! 하지만 라스베거스에 안정적으로 가려면 25점을 더 올려야 한다 ㅠㅠ

Submission 8 까지의 코드가 층을 설치할 때 백트레킹을 하였던 반면 이번 서밋은 한 층계씩 설치를 하면서 그 중 가장 결과가 좋을것으로 예상되는 것 하나만 골라서 진행하게 하였다(그리디 스럽게). 따라서 백트랙은 없다. 점수가 상승한 요인은 백트래킹의 경우 시간이 너무 오래 걸려 수많은 좋은 후보를 시뮬레이션 해보기도 전에 시간이 종료되었던 반면, 이번 서밋은 수많은 좋은 후보들 중 좋아 보이는 후보들만 골라서 시뮬레이션을 하기 때문에 효율적인 측면에서 이점이 있었던것같다.

하지만 그리디적인 방법이기 때문에 훨씬 더 좋은 해를 그냥 지나처버리는 문제가 있을 수 있으니 그리디를 하는 과정에서 최종 결과가 좋은 것을 선택할 수 있도록 휴리스틱을 잘 만들어야 할 것 같다. 

지금은 [500초 중 남은 시간] * [님은 공간의 높이] 가 가장 작은 시뮬레이션을 선택하게 해 놓았다. 

저 수식을 고친다고 해도 [남은시간]은 여전히 중요한 요소일 것이고.... 남은 타겟의 수라던가 뭐 이런것들로 시뮬레이션을 해볼 필요가 있다.

테스트는 R의 값에 따라 따로따로 테스트를 하여 케이스별 가장 적합한 변수를 찾도록 해야겠다. 물론 테스트는 나중에~~ 더 이상 짜낼 아이디어가 없을 때 시행하도록 하자...  간이 테스트에 대해서는 로컬에선 제한시간을 반으로 줄여서 테스트를 해야겠다.

Submission 10 - 63.18(8th)

65점 이상을 기대했는데 점수가 생각보단 덜 올랐다. (57.05 -> 63.18)

문제에선 공이 바운스되는 횟수가 10만번이 되는 순간 시뮬레이션이 종료되는 것으로 되어있는데, 버그를 잡다가 이 때문에 어떤 케이스에서 공이 10만번을 튈 동안 계속 시뮬레이션을 하는 경우를 발견하였다. 그리고 이런 경우는 상당히 빈번하게 발생한다는 것을 알았다. 아주 의미없는 시간소비!!! 그래서 나의 시뮬레이션에서는 공이 1000번 튀면 시뮬레이션을 종료하게 하였다(좋은 결과를 내는 솔루션은 아무리 많이 공이 튀어도 1000번은 안되겠지)

그리고 한 번 클리어 한 층위로 다시 공이 튀어 올라가는 경우가 있는데 이 경우에도 시뮬레이션을 종료하도록 하였다(마지막 층 클리어중일 때 빼고). 이 경우를 뺌으로써 시뮬레이션 속도가 조금 증가한것을 확인하였는데... 오히려 좋은 해를 없애버리는 경우가 있지는 않는지 의심스럽긴 하다. 다음 서밋은 이 if 문장에 주석을 달고 서밋을 해봐야겠다

소스를 수정하는 과정에서 버그와 혈전을 벌여야 했다. 코드가 점점 더러워지고 있다. ㅠㅠ 다음 수정을 위해 한번 깔끔하게 정리를 할 필요가 있는데 엄두가 안난다.

여전히 클리어 하지 못하는 케이스가 있다 (seed 3, 7 등등등) 이런 케이스까지 클리어 할 수 있도록 방안을 생각해봐야겠다.

Submission 11 - 62.34(9th)

Go4 에서 현재 시뮬레이션이 유망한지 검사하는 수식에 남은 타겟의 수를 시간에 더하도록 고쳤다.

벌서 이런 자잘한 최적화 하고 있으면 안되는데 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

점수도 오히려 떨어지는군. (62.46 -> 62.34)

D-9

Submission 12 - 56.45(12th)

뭥미~~ 자야겠다.

뭘 고쳤는지 기억도 잘 안난다 ㅠㅠ

뭔가 고치면서 버그를 만들어버린듯하다 제길제길제길 (61.80 -> 56.45)

디버그중에 중요한 사실을 하나 알았다

속도의 y성분은 그닥 중요하지 않다. 중요한건 x축 성분이다!!! 가로방향의 속력을 높일 방안은 자명한데... 그러자니 명중률이 떨어진다.. 추가적인 장애물을 설치하기는 또 싫고 아아아아아아 골때려

Submission 13 - 66.62(9th)

이번 서밋은 예상보단 점수가 많이 올랐다 ㅋㅋㅋㅋ

시뮬레이션을 나눠서 하는 과정에서 버그가 있었다. 방금전에 바운드 된 장애물을 바로 다시 만나는 것으로 인식하는 문제가 있어 공이 반대 방향으로 튀는 현상이 발견되어 수정했다. 하지만 submission 12에서 저렇게까지 망하게 할만한것 같지는 않은데.. 어쨌든 버그는 하나 수정!!

Go4에서 현재 층계의 유망성을 판단하는 기준으로 (현재 층을 클리어하는데 걸린 시간 / 현재 층까지 진행거리) 즉 단위 시간당 진행 거리를 기준으로 삼았다. 대부분의 케이스에서 점수가 향상되었다. 

D-8

Submission 14 - 67.49(10th)

Go4에서 층계를 클리어하고 난 후 다음 층을 추가하기 전에 시뮬레이션을 계속 진행하여 혹시나 아래가 모두 클리어되는지를 검사하도록 하였다. 이 경우 추가적인 시뮬레이션으로 인해 시간이 낭비되는 경우 vs 추가적인 시뮬레이션에서 좋은 해가 찾아지는 경우의 트레이드오프가 존재한다. 로컬에서의 200개의 케이스에서 테스트 결과 전반적으로 성능이 향상되었기 때문에 서밋을 해보았다. 점수는 예상했던 것 만큼 상승했다(65.73 -> 67.49)

하지만 이런 미세한 값의 조정으로는 1~2 점 정도의 점수 상승효과밖에 가져오지 못할듯하다. 성능을 1.5배 정도 향상시켜 최종점수를 80점 이상을 받게 해줄 아래와 같은 팩터가 두세개 정도 있을듯 한데 R2에서처럼 우연으로라도 찾았으면 좋겠다.

- 라운드2에서 각도 계산중에 발생한 버그가 점수를 5점 정도 상승시켜주었음

- 이메진컵07 알고리즘 라운드2에서 시뮬레이션 초반에 점수계산 방식을 그대로 따르지 않고 분산을 더 중요하게 생각하는 가중치가 최종적으로 전체적으로 온도분포를 고르게 만들어 성능을 1.5배정도 향상시킴

이번 라운드에서도 위와 같은 잘 보이지 않지만 점수 향상에 큰 역할을 할 인자가 있다고 믿는다.. 찾자 찾자!!!

- 속도의 x축 성분을 증가시킬 방안을 고민해 보자.. 슬로프를 주어 속도를 증가시키는 방법이 있긴 한데 시뮬레이션 결과 오히려 점수가 안좋아지는 케이스가 더 많다. 생각을 더 해보자

- Go4에 약간의 백트래킹을 추가하는 방법도 좋을것 같긴한데 제한시간이 안습.. 탑코더 서버가 너무 느리다.

- 젤 처음 공의 x축 성분에 속도를 더해주는 45도 기울기의 슬로프는 현재의 각도와 높이가 최적일것으로 생각된다.

- Go4와 Go3에서 R에 따라 인자를 최적화해야 하는데 1,2 점 정도의 상승효과정도에 그칠것으로 생각된다.

- Go4에서 유망한 후보를 찾는 공식에 대해 여러가지 실험을 해보자

D-6

Submission 15 - 69.73(9th)

지금은 새벽5시 ㅡ.ㅡ

어제아침에 버스를 타고 가다가 생각난 방법을 구현했다. 어제 너무 할일이 많아서 계속 못하다가 집에와서 겨우 코딩하다 밤새게 생겼다 ㅠㅠ. 내일은 컴씨가야해서 MM을 또 못한다 -_-

이번 서밋은 Go4의 비효율을 극적으로 개선했다고 생각한다.(이제부터 이놈이 Go2이다) 위에서 부터 층계를 놓을때 마다 DFS로 진행하지 않고 가령 1층을 놓는다고 하면 모든 가능한 1층들의 집합들 중 유망한 순으로 후보를 정한뒤 가장 우수한 100여개 정도의 후보만을 선정하여 그 후보로 부터 2층을 놓는다. 다시 2층들의 집합들 중 가장 유망한 후보들을 선정하여 3층을 쌓고 ......

어쨌든 기존 코드가 너무 드러워서 대대적인 보수작업을 했는데 컴파일에러를 잡고나니 별다른 버그없이 잘 돌아가서 약간 불안하긴하다 ㄷㄷㄷ

집에서 노트북으로 하다보니 노트북은 탑코더 서버보다 속도가 느려 왠지 성능이 나빠지는가 했더니.. 시간제한을 탑코더 서버와의 속도차를 고려하여 맞추고나니 성능이 상당히 좋아졌다. 이 방법에서 남은 문제는 탑코더 서버에 최적화된 후보의 수를 찾는 것인데 이건 나중에 하도록 하고 또 다른 아이디어를 찾아봐야겠다.

서밋결과 성적은 예상보단 조금 올랐지만 그래도 꽤 많이 올랐다 (63.09 -> 69.73) 하지만 아직 Las Vegas에 가기엔 역부족인듯

D-4

컴씨 갔다오느라 하루동안 MM을 못했다. 그사이 등수는 3등이 떨어져 12등을 하고 있었다(67.44)

Submission 16 - 65.31(13th)

Simulation을 수정하여 층과 층사이에 조금이라도 타켓이 걸치게되면 그 층을 돌면서 타겟을 처리할 수 있는 것으로 변경하였다. 이 때 하나의 타겟이 두개의 층에 걸쳐있는 경우의 처리가 귀찮아서 미루고 미루고 미뤄오다가 결국 했다.

로컬에서의 테스트결과는 물론이거니와 탑코더에서의 example 테스트 결과 모드 엄청나가 결과가 좋아졌는데 왠지 서밋했더니 점수가 떨어졌다..(67.44 -> 65.31)

Sumission 17 - 74.48(9th)

좋아 대박이다!!!!!!!!!!!!!!!!!!

처음으로 70점을 돌파했다. 1위를 제외한 상위권과의 점수차가 크지 않다. 최적화를 잘하면 순위를 유지할 가능성이 보인다. 아래에 wata, Emk, venco, KOTEHOC, ploh, chokudai, ika등의 강자들이 있어 방심할 수 없다. 

며칠전부터 계획하고 있었던 경사를 주는 코딩을 해버렸다. 이제 층계를 설치할때 좌우에 평평하거나 기울어진 4개의 층계중 하나를 선택하여 고르게 된다. 일단 경사진 층계의 경우 왼쪽끝과 오른쪽끝의 차이가 4만큼 차이가 나도록 하였다. 확실히 경사가 x축 성분에 속도를 더해주는 효과를 줘 타겟을 빠르게 처리할 수 있다.

지금은 일단 케이스별 최적화는 전혀 되어있지 않는 상황이다. 기울기도 최적화하지 않았다. Go2는 매 층계를 놓을때 마다 50개의 후보를 선정하도록 하였다. 

변수 최적화를 할 부분은 다음과 같다

- 선정할 후보의 갯수(가장 중요하다)

- 후보를 선정하는 기준이 되는 점수를 구하는 함수(변경할일이 없을것같다)

- 층계 사이의 최소 거리

- 층계 사이의 최대 거리

- 슬로프 경사(이것도 중요할 듯)

- 또 뭐가 있지........................

머릿속에 있었던 아이디어를 하나도 남김없이 다 구현한듯하다. 또 다른 아이디어가 생길지 모르겠다.. 내일까지만 방법을 더 찾아보고 월요일에 상황을 봐서 변수 최적화를 시작할지 결정을 해야겠다.

D-3

Sumission 18 - 73.45(11th)

Go2의 후보의 수가 50개였는데 제한시간 20초에 처리하기에 좀 버거운 느낌이 있어서 40개로 줄여서 서밋을 해봤다. 점수는 거의 그대로 (73.43 -> 73.45)

아~~~ 더 이상 해볼게 없다

Sumission 19 - 74.57(11th)

유망성을 판단하는 함수를 고쳐서 서밋을 해봤다. 

변수를 이래저래 고쳐봐서는 절대 탑10에 들 수 없는데 이런거 밖에 할게 없다 ㅠㅠ

다른 아이디어가 필요해

Submission 20 - 77.04(11th)

여러가지로 고쳐보면서 테스트를 하고있다.

층계에 경사가 생기면서 공이 위로 다시 튀어올라가는 경우를 체크하는 곳에서 버그가 발생한 것을 발견하여(체크가 안되고 있었다) 수정했다.

점수는 소폭 상승하긴 했는데(74.68 ->77.04) 아직 더 올려야 돼

D-2

Submission 21 - 79.32(10th)

다시 10위에 진입했다. 피말린다.

여러가지로 테스트를 하고 있지만 성능이 크게 향상되지 않는다. 그래도 이번 서밋은 생각보단 많이 올랐다 (76.65 -> 79.32)

일단 이번 서밋은 경사도가 2인 경우와 5인 경우를 혼용해서 사용하도록 해봤다. 후보의 수는 35이다. 테스트의 수가 1.5배 늘었지만 Submission 20에서 버그를 고쳐서 시뮬레이션의 속도가 약간 빨라져서 후보의 수는 크게 줄이지 않았다. 테스트 결과 35가 40보다 더 좋았다. 30은 아직 안해봤다.

다른 경사도를 적용시켜서 테스트를 해봐야겠다. 그리고 N과 R값에 따라 최적의 파라메터를 찾는일을 시작해야겠다.

더 이상 아이디어가 없다 ㅠ

-seed 157에서 미묘하게 점수가 틀린 현상이 있다. 버그를 잡아야 한다

- 가끔씩 20초가 지나도 결과가 나오지 않는 경우가 발생한다(200번에 한번꼴) 무조건 잡아야된다.

- Go2가 얻어내는 점수를 Go3가 갱신하는 케이스는 거의 없다. 제한시간 20초를 Go2에 최고로 효율적으로 투자할 수 있는 방법을 생각해봐야겠다.

Submission 22 - 79.05(11th)

이래저래 테스트를 해보다가 사소한것 하나 고친것이 로컬에서 아주 약간 점수가 올라서 서밋해봤는데 정말 아주 약간(0.02점) 올랐다

Submission 23 - 79.67(11th)

로컬에서 테스트를 계속 해서 N의 값에 따른 적절한 시뮬레이션 반복횟수를 찾아 적용시켰다.

그리고 더 큰것은 Go3를 아에 없애버리고 Go2로 20초를 채우기 위해 Go2에 백트레킹을 도입했다. 더 이상 후보를 선정할 수 없는 경우 백트랙하여 이전 단계에서 후보에 들지 못했던 층계들에서 부터 진행을 하도록 고쳤는데.... 뭐 '이전단계에서 후보에서 탈락한 놈들이 알고보니 더 좋은해를 만들 수 있는 가능성이 있었다' 라는 케이스는 극히 드문것 같다.

슬슬 한계에 다다르는것 같다. 78.86 -> 79.67

Submission 24 - 80.43(11th)

양끝의 높이차가 4, 6, 8 인 세가지의 슬로프를 혼용해서 사용하도록 해서 서밋을 해봤다.

내심 82점 이상을 노렸는데 80.43이라... GG 칠 시간이 다가온다.

79.22 -> 80.43

D-1

GG!!!

그래도 잘했다

유유

Standings
Handle	Score	Rank	Last Submission Time	Language	Example Tests	Submissions
roma	89.03	1	04.05.2009 02:50:20	C++	19	10
Psyho	87.00	2	04.07.2009 09:22:08	C++	52	30
nhzp339	86.70	3	04.07.2009 10:32:16	C++	135	50
jdmetz	85.74	4	04.06.2009 22:39:30	C++	16	8
KOTEHOK	85.15	5	04.07.2009 05:45:46	C++	14	9
prober	84.88	6	04.07.2009 04:44:30	C++	13	11
ACRush	84.76	7	04.07.2009 09:28:47	C++	89	43
Squier	84.54	8	04.07.2009 09:53:11	C#	10	10
zibada	84.37	9	04.06.2009 16:03:17	Java	4	9
EmK	82.97	10	04.07.2009 06:09:13	C#	33	26
JacoCronje	81.99	11	04.06.2009 17:01:28	C++	7	8
AlexanderL	81.88	12	04.04.2009 19:21:49	C#	2	1
AdrianKuegel	81.01	13	04.06.2009 08:22:22	C++	22	22
ilyoan	78.01	14	04.06.2009 12:44:53	C++	43	24
tomerun	75.88	15	04.06.2009 11:57:50	Java	20	11
tpelkone	73.45	16	04.05.2009 20:23:22	C++	18	16
wata	67.03	17	04.04.2009 15:32:29	Java	6	4
Mimino	66.41	18	04.07.2009 05:02:31	C++	36	20
RatonulBolnav	66.11	19	04.07.2009 08:49:15	C++	44	14
Wernie	65.42	20	04.06.2009 16:38:53	C++	11	10

지지친 현재시점 등수는 14위, 10위와 대략 5점차이

내일 하루가 더 남았기 때문에 등수는 더 떨어질 텐데.. 그래도 20위 안에는 들었으면 좋겠다 

D-Day

관전자의 입장이 되니 맘이 참 편하고 재미있네 그려

마지막날 순위 변동이 예사롭지 않다. 이 사람들의 상상력의 한계는 도대체 어디까지인가!!!! psyho는 신으로 모셔 마땅한 존재이다. 비록 지금 이 글을 쓰고있는 현재 등수는 2위이지만 난 psyho를 믿는다!! ㅋㅋ

마지막 서밋제한시간을 6시간 앞둔 현재(즉 이제 앞으로 최대 두 번의 서밋을 할 기회가 있다. 지금은 오후 6시 50분) 라스베거스를 가시권에 두고 있는 MM훼인들의 리스트는 이렇다

Standings
Handle	Score	Rank	Last Submission Time	Language	Example Tests	Submissions
AlexanderL	92.69	1	04.08.2009 01:32:42	C#	4	3
Psyho	91.80	2	04.08.2009 00:48:08	C++	57	33
zibada	87.55	3	04.08.2009 03:49:07	Java	6	11
wleite	86.80	4	04.07.2009 22:40:31	Java	36	18
jdmetz	86.38	5	04.08.2009 02:31:35	C++	20	11
roma	85.03	6	04.08.2009 03:31:44	C++	31	14
maniek	84.61	7	04.08.2009 05:23:15	C++	7	8
nhzp339	83.73	8	04.08.2009 03:29:00	C++	154	54
prober	83.68	9	04.07.2009 21:31:42	C++	19	13
KOTEHOK	82.43	10	04.08.2009 02:18:32	C++	25	13
ACRush	82.32	11	04.08.2009 03:06:35	C++	94	47
Squier	82.18	12	04.07.2009 18:21:35	C#	12	12
JacoCronje	81.89	13	04.07.2009 16:33:16	C++	8	9
EmK	80.50	14	04.08.2009 03:22:37	C#	36	30
AdrianKuegel	78.84	15	04.07.2009 19:25:45	C++	23	24
ploh	78.49	16	04.08.2009 02:13:34	C++	9	4

마지막 3일동안 ploh가 대단한 기세로 치고 들어오고 있다. 1위는 누가될지 예측할 수 없는 상황!! 초반 지치지 않는 러쉬를 감행했던 오덕이는 무려 11위까지 밀려난 상황 이대로라면 파이널을 장담할 수 없다. MM기간 내내 중위권에서 헤매던 wleite은 드디어 정신을 차리고 Top 10에 진입했다. 중반 이후 오덕이를 관광보낸 roman은 마지막 서밋(지금 기준으로)이 망하면서 잠시 주춤하고 있다.

R3가 시작되기 전 누군가 포럼에 10명 중 레드가 몇명일까?? 라는 글을 올렸는데 많은 사람들이 7~8명 정도일거라 예측했지만 뚜껑을 열고보니 숨은 옐로우 고수들이 나타나 레드들을 안드로메다로 보낸 형국이다.  아직 끝난게 아니니 기다려 보자. 언젠가 ploh는 케이스별로 나누어서 서밋을 해오다 마지막 서밋에 모든 케이스를 포함하는 솔루션을 내면서 모두를 관광보낸적도 있지 않은가

어쨌든 난 TCO티셔츠를 확보했으니 이걸로 만족하기로 하고..

[18:35] <ILyoan> 음.. 레이팅을 생각해서 최적화좀 할까 라고 생각을 했더니

[18:35] <ILyoan> 제 근처 점수대의 사람들이 없군요

[18:39] <노컷> 안드로메다 성인과 일반인의 중계자 역활을 하시는 듯...

[18:40] <노컷> 14-19등이 10점차가 나는 군요

[18:41] <노컷> 5-12등은 4점차..

그렇다. 지금 당장 새로운 아이디어도 없고 케이스별 최적화 끄적거려봐야 순위변동도 없을테니 걍 딴짓이나 해야지..

노컷님의 현 상황을 살펴보자

Standings
Handle	Score	Rank	Last Submission Time	Language	Example Tests	Submissions
delicato	49.95	41	04.03.2009 16:04:51	C++	1	1
nocut98	49.25	42	04.07.2009 22:12:10	C++	36	16
chokudai	48.54	43	04.07.2009 17:21:28	C#	36	29
Krzysan	48.00	44	04.07.2009 18:24:08	C++	18	11
cant_dance	47.46	45	04.07.2009 21:45:37	C++	33	23
MarkByers	47.15	46	04.03.2009 17:19:41	C#	1	10
Hephest	47.07	47	04.03.2009 20:37:57	C++	22	10
BjarkeDahlEbert	46.33	48	04.05.2009 17:09:31	C#	5	5
mhoefs	46.26	49	04.07.2009 11:21:07	C++	22	10
gedluk	45.51	50	04.04.2009 22:14:22	C++	12	9

무려 레드의 사이에서 더블팀을 당하고 있는 형국이다. 티셔츠를 받게되는 50위 컷오프와 점수차는 대략 4점 정도라 이대로 끝난다면 무난히 티셔츠가 확보되겠지만 아직 6시간이 남아있으니 방심할 순 없겠다.

R1, R2에서 괴력을 과시해 MM49를 포함하여 무려 3회 연속 Top5를 기록했던 chokudai 께서는 43위로 레드 꼴지!! 를 달리고 있으니 후지산이 무너져 신간센이 탈선하여 안드로로 달리고 있다. 아직 두번의 서밋이 남았으니 기다려보자

D+1

마지막 서밋을 살펴보자

Standings
Handle	Score	Rank	Last Submission Time	Language	Example Tests	Submissions
*AlexanderL	96.29	1	04.08.2009 07:49:14	C#	5	4
*Psyho	93.58	2	04.08.2009 07:56:36	C++	58	34
zibada	85.70	3	04.08.2009 11:58:36	Java	9	12
*roma	84.62	4	04.08.2009 07:43:32	C++	35	15
*maniek	84.28	5	04.08.2009 11:23:18	C++	9	9
wleite	83.91	6	04.07.2009 22:40:31	Java	36	18
*jdmetz	83.44	7	04.08.2009 02:31:35	C++	21	11
*prober	82.07	8	04.08.2009 06:31:21	C++	20	14
Squier	80.29	9	04.08.2009 11:47:55	C#	15	13
*nhzp339	79.89	10	04.08.2009 11:50:22	C++	162	56
*KOTEHOK	79.60	11	04.08.2009 02:18:32	C++	25	13
ACRush	79.55	12	04.08.2009 11:58:11	C++	106	49
EmK	79.46	13	04.08.2009 07:22:45	C#	37	31
JacoCronje	79.08	14	04.07.2009 16:33:16	C++	8	9
*marsavic	78.62	15	04.08.2009 11:35:49	Java	4	4
*ploh	78.33	16	04.08.2009 11:45:51	C++	12	6

http://www.topcoder.com/longcontest/?module=ViewStandings&rd=13768

대략 여기까지가 최종 테스트 10위의 가능성이 보이는 후보들인것같다. 압도적인 점수를 낸 AlexanderL과 Psyho를 제외하고 3위부 부터 16위까지 점수대가 촘촘히 분포되어 있다. 특히 10위와 16위의 점수차가 1.6점밖에 안나기 때문에 마지막 결과가 나오기전엔라스베가스 티켓을 따게되는 최후의 10인을 쉽사리 예측하기 어렵다

Post Your Approach에 사람들이 자신의 아이디어를 올리고 있는데 의외로 Psyho의 아이디어가 나의 아이디어와 상당히 흡사하다. 거의 같다고 해도 무방할 만큼 비슷한데, 다른점이 있다면 나는 층계단위로 search를 한 반면 Psyho는 시간단위로 search를 한 것 같다. 그리고 가장 큰 차이점은 바로 후보들의 유망성을 판단하는 함수인데 Psyho가 사용한 함수는 또다시 놀랍게도 AlexanderL이 사용한 함수와 거의 흡사하다. -ㅁ- 어떻게 서로 다른 두 사람이 거의 비슷한 형태의 함수를 사용하여 비슷한 결과를 내놓을 수 있는지 신기할 따름이다. 얼마나 내공이 쌓이면 그들에게 저런 함수를 생각할 수 있는 능력이 생기는 것일까. 심지어 AlexanderL은 Newton Method를 그대로 사용하고도 저 점수를 내놓았다. 

 join states by the number of targets hit counting from the top - i.e. state group no 5 joins all the states where the targets 1..5 were already hit (and potentially something else). Scoring function for a state is - current_time + ~21 * obstacles_number - 2 * other_targets hit. In each group I remember the best 5 states. And then I just iterate on each group.

Psyho

scoring function is endpointTime + ~21 * obstaclesCount - weight_of_visited_targets
where weight_of_visited_targets is sum of weights of each visited target.
weight of target is defined as (targetY[i] > 350)? (targetY[i] - 350) / 4: 0;

AlexanderL

어쨌든 매치는 끝났고 최종 50위 안에 포함되는 것은 100% 확신할 수 있는 상황이니 당초 목표였던 TCO 티셔츠는 확보를 했다.

이번 TCO를 하면서 매치마다 내가 생각한 아이디어는 베스트 솔루션의 아이디어와 큰 틀에서 같은 맥락을 가졌었다. 물론 세세한 부분으로 들어가면서 다른점이 나오는건 어쩔 수 없는 일이지만. 문제는 항상 베스트의 70%까지는 달성을 하지만 그 이상으로 끌어올리는데 실패를 하고 있다는 점이다.

해가 좋아질 수록 더 좋은 해를 만들기 어려운 것은 진리다. 내가 더이상 전진하지 못하는 상황에서도 훌륭한 경쟁자들은 계속해서 더 좋은 해를 만들어낸다. 무엇이 이런 차이를 만들어 내는가. 끈기, 이론적 배경, 경험, 천재성 등등등.. 여러 요인들 중 극복 불가능한 것(천재성 같은거)이 있는 반면 열심히 쫓아갈 수 있는 요인들도 있을것이다.

올해는 일단 목표를 달성했으니 내년에는 부족한 부분을 보완하여 라스베가스 티켓에 도전장을 내밀어봐야겠다.