안녕하세요. 처음으로 이 게시판에 글을 써보네요
 이번 TCO Round 1 은 상위 250명이 시드를 받은 50명과 함께 Round2에 진출하게 되는 MM이었습니다. 당초에는 200등 정도만 해서 Round2에만 진출하자고 생각했었는데 하다보니 욕심이 생겨서 꽤 열심히 했던것 같네요.
 일단 문제입니다.
[spoiler="더 보기..."]D-6
문제를 봤다. 우선은 다행스럽게도 문제를 이해하기는 쉽다는 느낌이다. 
D-4
지금까지 생각한 방법을 적어보자.
방법 1.

• 지역 최대와 최소점을 포함한 몇 군데 지점을 measure 해본다.- 지형 만드는 공식을 적용하여 지도를 만들어본다.- D값을 변화시키면서 등고선을 뽑아서 주어진 등고선과 대조한다. 등고선이 가장 유사한  D를 찾는다.- 등고선의 에러를 측정하여 기준점의 파라메터를 변경한다.- GA나 기타 다른 서치 알고리즘을 응용해서 최적의 파라메터를 찾는다. 방법 2.
• 등고선을 뽑아낸다.- 지역 최대최소 포함 등고선을 모두 measure 한다.- 지역 최대최소를 뺀 등고선의 높이를 기준으로 가장 적합한 D를 찾는다.- D를 기준으로 등고선의 높이를 다시 조정한다.- 선형보간으로 등고선 사이의 지형의 높이를 결정한다. 방법 1이 그럴듯해 보이긴 하는데 아무래도 구현이나 프로그램의 동작 시간이나 힘들 것 같다. 기준점의 파라메터를 변경하기위해서 적절한 수학적 모델을 찾아봐야하는데, 전혀 가능성이 없어보인다. 조사해야할 변수가 너무 많다. 방법2는... 뭐랄까.. 좀 간단한 방법이긴 한데 점수가 어찌 나올런지..... Submission 1 - Score: 19.7 (67th) 방법 2을 구현하였다.  결과는 생각보다 나쁘지 않은 것 같다. 튜닝을 잘하면 1위(58점) 와 비슷한 점수대까지 끌어 올릴 수 있을 것같다. 기본적인 접근 방법이 전혀 엉뚱한 방향은 아닌것 같다는 생각이 든다. 이 정도 점수면 여기서 그만둬도 라운드1은 통과할 수 있을 것 같다.
• 우선 DFS로 외곽선을 뽑아낸다. 외곽선은 인접한 4개의 점까지만 인정한다. 문제가 되는 케이스가 있는데 등고선이 너무 조밀하게 붙어 있어서 서로 다른 등고선인데도 하나로 레이블링 되는 경우가 있다. 이런 케이스는 일단 접어두었다.
• 다음으로 세그먼트(등고선과 등고선 사이의 지역)를 조사한다. 세그먼트에 인접한 등고선이 하나 밖에 없는 경우 이 세그먼트 안에 반드시 지역 최대 혹은 최소점이 존재할것이므로 이런 세그먼트를 조사하여 세그먼트의 한 가운데를 measure하도록 하였다.
• 모든 등고선과 지역 최대 최소점을 measure한다.
• D값을 찾는 함수(AdjustElevation)가 잘 동작하지 않는다. d값을 2.0에서 10.0 까지 0.01씩 증가시키면서 측정된 등고선과의 오차의 제곱이 가장 작은 d값을 찾으려 했으나 원래 지형의 d값의 정수배 혹은 약수의 언저리에서 에러가 더 작은 경우가 발생한다.
• 예를들어 원래의 D가 4.5인 경우 4.5에서의 에러보다 9.0 언저리에서의 에러의 합이 더 작게 나오는데 오차의 제곱의 합을 기준으로 했으므로 당연한 결과이다. 오차의 제곱의 평균을 기준으로 잡으면 4.5와 9.0이 거의 비슷해 진다. 하지만 이때 2.0이 훨씬 작은 값을 가지는 경우가 있다. 
• 위의 이유로 일단 D값을 찾는것은 제외하고 measure한 값을 그대로 사용하였다.
• 선형보간이 잘 되는것 처럼 보이기는 하는데... 하나의 세그먼트에 인접한 등고선이 3개 이상이 되는 경우 잘 되지 않는다. 일단은 3개 이상의 경우에는 가장 가까운 2개를 기준으로 선형보간을 하였는데 초큼 맘에 들지 않는다. 3개 이상인 경우에도 자연스럽게 보간을 할 수 있는 식을 생각해봐야겠다.
• 선형보간을 위해 각 점에 가장 가까운 등고선의 높이와 거리를 알아야 하는데, BFS로 구현하였다. 확장은 등고선에서 시작하여 다음 등고선을 만날때 까지 동서남북 4방향으로 한다. 졸려서 자야겠다..... D-3 Submission 2 - Score: 20.71 (49th) 안잤다... 지금 시간은 새벽 6시.. 아까전에 서밋한 솔루션에 중대한 버그를 발견하여 수정했다. 하나의 세그먼트에 인접한 등고선이 3개 이상인 경우 선형보간의 하는 공식에 문제가 있었다. 기본적인 아이디어는 한 지점의 높이는 그 근처에 존재하는 measure된 지점(등고선과 지역최대, 최소점)의 거리에 반비례하여 영향을 받을 것이라는 것인데, 아까전에 구현한 내용은 이 반비례를 구현하면서 곱셈을 하지 않고 덧셈을 해버렸다(멍청이!!)
• Distance(어느 한 지점에서 그 세그먼트에 인접한 등고선까지의 거리들) 측정을 좀 더 정확히 하기 위해 우선순위 큐를 이용하여 해보려고 했는데 생각보다 너무 느려서 포기했다. 버그를 수정하고 부푼기대를 안고 서밋을 했는데.. 점수가 생각보다 팍 튀어 오르지는 않는다.. 에잇!!!! 자야지!!! 하나 더 지형을 세그먼트를 노드로 하고 등고선을 에지로하는 그래프로 표현할 수 있을 것 같다. 하지만 구현을 어떻게?????

Submission 3 - Score: 19.37
등고선의 높이는 d의 배수보다 낮다!! 라는 것을 깨닳고, measure를 하였을때 튀어 나오는 값에 + 0.15를 해서 서밋을 해보았다. 하지만 점수는 약간 하락했다.....
결과를 보니 등고선의 높이가 d의 배수보다 낮은거랑 measure된 값에 0.15를 더하는 거랑 무슨 관계가 있다는 거지??? 라는 생각이 든다. 조금은 억지 스러운 방법인것 같다. 괜한짓을 했다..... 폐기처분!
3.1 절을 맞아 하루종일 MM을 하고 있다.

• 방법 1을 간단히 구현해 보았다.. 하지만 결과는 참담하다..가능성이 안보인다. 방법1은 폐기처분!!
• 정규분포 함수를 이용하여 Adjust를 해봤는데 역시 잘 되지 않는다. 통계학을 공부한지 너무 오래됐다. 기억을 더듬어보면 에러의 제곱의 평균이 가장 작은 D를 찾는것이 타당한 방법인것 같다.
• Adjust 를 이래저래 해보고 있는데 잘 안됨... 전역최대와 전역최소점을 잇는 최단경로(거리상으로 가장 가까운 경로가 아니라 등고선을 가장 적게 지나는 경로)를 찾아서 최단 경로상의 등고선의 갯수를 파악하면 D를 잘 예측할 수 있을 것 같다. 최단경로상 등고선의 수가 k개가 있다면 D는 [100/(k+1), 100/k] 사이의 값이 될 것이다.
• DFS로 최대점에서 최소점까지의 등고선의 수를 새어보려고 했는데 뭔가 심각한 버그가 있는 코드를 만들고 말았다. ㅠㅠ 어쩔 수 없이 submission 3에 제출했던 소스로 되돌림. D-2 Submission 4 - Score: 18.8 Distance측정을 하는 BFS로직에서 확장 방향을 4방향에서 8방향으로 변경해보았다. 결과는 4방향일때에 비해 약간 떨어졌다. 케이스에 따라 4방향이 좋기도하고 8방향이 좋기도 한듯하지만 대체적으론 4방향이 뛰어난것 같다.
• visualizer를 수정하여 내가 리턴한 지형을 볼수 있도록 고쳤다.
• Visual Studio로 컴파일하면 스택오버플로우가 난다. 포럼을 살펴본 결과 스택사이즈는 10MB이다. 컴파일 옵션을 변경하였다.
• 집에 오는 버스에서 곰곰히 생각해 봤는데 마지막에 블러링하면 점수가 오를것 같다!!!!!!
• 디버그를 위해 세그먼트 정보와 등고선 정보를 출력하던 중 이 녀석들을 그래프로 구성하기 위한 정보를 이미 다 가지고 있음을 알게 되었다.(이걸 왜 이제 알았지;;)    Submission 5 - Score: 37.64 (14th) 코딩을 완료하고 테스트 하고 서밋했다. 결과는 좋다. 크크크크크크크크크크
• 우선 이미 다 가지고 있는 정보를 바탕으로 지형을 그래프의 형태로 표현한다. (세그먼트가 노드, 등고선이 에지) 
• 플로이드 알고리즘으로 전쌍 최단경로를 구한다. 특히 전역최대점에서 전역최소점으로 가는 최단거리 k와 경로 p를 알아낸다.
• D값은 [100/(k+1), 100/k] 사이에 있다. 처음부터 짜 놓았던 AdjustElevation 함수를 드디어 사용.
• 대부분의 케이스에서 D값을 오차범위 0.05 이내로 예측.
• 예측된 D값을 기준으로 등고선의 높이를 재조정(가우시안 노이즈가 제거된다)
• 나머지는 동일함!!!
• measure 횟수를 줄이기 위해 여러 방법을 시도해 봤는데 잘 되지 않는다.. (에러가 커져서 점수가 떨어짐)

아까전에 서밋한 코드에 약간의 버그를 발견해서 고치고, 추가적으로 몇가지 더 구현했다.

• '예측된 D값을 기준으로 등고선의 높이를 재조정한다' 의 부분에서 최단 경로에 포함되는 등고선은 에러 상관없이 순서대로 d의 배수를 적용.
• 등고선이 따닥따닥 붙어있는 케이스에는 등고선의 높이를 재조정하지 않는다.
• Measure의 횟수가 제한된 횟수를 벗어나는 캐이스를 발견했다. 측정횟수를 기록하여 0점을 받는 케이스가 없도록 수정했다.
• 3x3 컨볼루션 필터를 사용하는 가우시안 블러링을 추가. 로컬에서 테스트해본 결과 점수가 무지막지하게 올랐다(야호!!).  방금전에 서밋을 해서 3시간을 더 기다려야 한다.... 지금은 자고 내일 일어나서 서밋해봐야겠다. D - 1 Submission 6 - 47.7 (5th) 결과가 상당히 좋다!!!!!  1위(chokudai)와 10점차이  Top 5로 매치를 마치고 싶어졌다;;; ....  학교가자 Submission 7 - 51.01 (3th) 블러를 8번 한 소스를 적용하였다. Distance를 구하는 함수도 나눠서 구현했다.
• 블러링 횟수를 8회로 늘렸다.
• Distance2를 만들었다. 어느 지점에서 가자 가까운 등고선 까지의 거리를 BFS로 구하지 않고, 세그먼트 인접한 등고선을 구성하는 모든 점들까지의 거리를 다 재고 그 중 가장 가까운 것을 취하도록 하였다. 
• Distance2가 생각보다 많은 시간을 소요한다. seed 2와 7에서 7초가 넘는 시간이 걸렸다. 500*500에 근접한 지형이라면 TLE가 발생할 가능성이 있으므로 지도의 크기에 따라 적절히 Distance1과 Distance2를  호출하도록 하였다.
• 풀테스트를 위한 배치 프로그램을 만들었다. seed 1에서 100까지 100개의 테스트를 수행한다.
• 블러를 많이 하면 점수가 팍팍 오르는 케이스가 있는데 반면 떨어지는 캐이스도 있다.. 점수제가 상대평가라... 떨어지는 케이스를 버리고 몇개의 케이스에서 고득점을 하는게 유리하려나????? 일단 균형잡인 횟수는 8회인것 같다.
• 크기가 작은 필터를 이용하여 블러를 여러번 하는 것과 크기가 큰 필터로 한 번 하는거랑 어떤 차이가 있을까??
• 점수 공식(100-M/floor(sqrt(W*H))/ERR)에서 M 보다 ERR이 차지하는 비중이 훨씬 크다!!! 두 명이 치고 올라왔다. 지금은 49.59점으로 5위를 하고 있다.. 구현 가능한 아이디어가 떨어져간다.(사실 귀찮다) Top 5가 힘들것 같단 생각이 든다. Submission 8 - 49.59 (5th) 블러 횟수를 7회로 해서 한 번 해봤다. 8회일때랑 동일한 상대점수를 받았다. chokudai와 차이점을 생각해 봤다. 이 녀석은 뭘 했길래 점수가 10점 더 높을까??
• 전반적인 아이디어는 나랑 별반 차이가 없을 것 같다.- measure 횟수가 나보다 적을 것 같다. d값을 예측할 수 있으면 등고선을 다 measure할 필요가 없기 때문에...- 등고선의 간격을 고려하여 선형 보간 대신 어떤 함수를 이용하여 지형의 고도를 측정할 수 있다. 차수가 6차 정도되는 함수로 회기분석을 하거나 혹은 Bezier-Spline곡선을 활용하여 고도를 예측하면 좀 더 정확한 예측을 할 수 있을 것이다.... 하지만 어떻게 구현하지?????????- 사소한 파라메터에서 최적화를 훨씬 더 잘 했겠지???- 블러링 필터가 다르거나 횟수가 다르거나... Submission 9 - 47.52 (6th) 등고선이 막 겹쳐있는 케이스를 처리해서 대충이라도 지형을 예측하게끔 고쳤다. 하지만 점수는 더 떨어짐 ㅠㅠ
• 소스를 수정하면서 생긴 버그는 없지만 얻는 점수가 달라짐.
• 소스를 수정하면서 measure를 하는 순서가 바꼈다. 이전의 소스는 내가 찾은 지역 최대최소(인접한 등고선이 하나밖에 없는 세그먼트의 한 가운데)를 먼저 measure하고 이미 알려진 지역최대최소를 나중에 measure했는데, 지금 소스는 순서가 반대이다. 따라서 각각에 들어가는 가우시안 노이즈가 끼는 순서가 달라지게 되고 점수에 영향을 미치는것 같다.
• 등고선이 막 겹친 케이스의 경우 수정된 버전이 점수를 무려 만배가량 더 많이 얻지만.. 그래봐야 0.1점도 안되는 점수라 best에 비하면 너무 낮은 점수인것으로 생각된다. 그래서 점수가 오르지 않은 것 같다. 그래도 버리긴 아까우니 그대로 두자
• measure 횟수를 줄여보려고 시도를 해보았는데 에러가 커져서 점수가 오히려 떨어진다.
• 포럼을 읽던 중 지도의 최 외곽점에 지역최대나 최소가 있는 경우 + 마크가 되지 않는다는 것을 알았다. (아하!!) 바로 코드에 적용했지만.. 로컬테스트결과 왠지 점수가 떨어짐 ;; 원인 이해 불가능...
• 세그먼트의 중심점을 찾는 소스에서 아주 사소한 버그를 발견, 수정. 점수에는 큰 변동사항 없음 D-day Submission 10 - 45.25(6th) Submission 7의 소스를 한 번 더 서밋해봤다. 그냥 다른 사람이 서밋할 때 내 점수가 어떻게 변하는지 궁금했을 뿐이다... 아마 마지막에 서밋한 점수만 업뎃이 되는것 같다. Submission 11 - 44.26(6th) 아마 마지막 서밋이 될것 같다.  Submisstion 9에 제출한 소스에 세그먼트 중심점을 찾는 부분의 버그를 수정한 버전을 제출하였다.
• 로컬 테스트결과는 서밋9을 수정안한 버전이 점수가 조금 더 높았지만, 버그를 수정한 버전이 최종 테스트에서 더 높은 점수를 받을것이라 생각한다. 남은 시간동안 구현 가능한 아이디어가 없다. MM36에서 처럼 어처구니 없는 실수를 매치가 종료된 후에 발견하는 일이 없도록 제출한 소스를 보고 또 보고는 있지만... 그닥 집중이 되지 않는다. 빠른무한에서 연패를 하고있다;;;;;; D + 1 현재 8위에 있다.  어제 9위까지 떨어졌었는데... 상대점수이기 때문에 누군가 서밋을 하면서 다른사람의 점수가 떨어진것 같다. 1위의 소스를 살펴보았다. 대략적인 아이디어는 나랑 비슷한 것 같은데.... 세부적으로는 잘 모르겠다. 포럼에 gedluk가 자신의 방법을 올렸다. 대략 나랑 비슷하다. 단지 measure횟수를 줄일수 있는 아이디어가 보인다. 왜 진작 생각하지 못했을까...(For the max node scan its contour several times to increase estimation accuracy) 내가 최종 제출한 소스에서 중대한 버그를 발견!! AdjustElevation 함수에서 d값을 기준으로 등고선의 높이를 재조정 하는 부분에서 지역최대최소점 까지 수정을 하고 말았다 ㅠㅠ 아마 에러에 막대한 영향을 미첬을거 같다. ㅠㅠㅠㅠㅠㅠㅠㅠ 지역최대최소점을 최외곽 지점으로 설정한 소스가 오히려 점수가 떨어졌던 원인도 여기에 있는겉 같다. 버그를 수정한 후 로컬에서 테스트를 해보면 얼마나 많은 점수차가 날지 알 수 있겠지만 그닥 알고 싶지가 않아서 그냥 내버려 두기로 했다. [/spoiler]