아직 최종결과가 나오지 않았지만, 나름 후기를 먼저 적어봅니다. MM에 관심을.. ^^
개인적으로 이번시합이 매우 중요한 대회였습니다.
현재 스코어 1502점.. 3점만 떨어지면 아이디가 파란색으로 바뀌게 되는... -_-;; 벼랑끝에 몰린 심정으로 대회에 임했더랬습니다.
추석 때 부산에서 서울까지 9시간에 걸친 운전..
피곤하긴 한데 SRM도 있고 해서... 컴퓨터앞에 앉았습니다.
문제는 PolygonArea
대충 설명하자면 10 * 10 의 square에 존재하는 다각형의 넓이를 계산하라~.
한 점을 찍으면 그 점이 다각형의 안에 존재하는지 밖에 존재하는지를 알려주는 라이브러리를 제공한다.
다각형은 5~20각형이고, 점을 찍을 수 있는 횟수는 100~300 사이에서 지정된다.
호~ 구미가 땡기는 문제입니다.
- 1차 시도 -
평일은 회사 일이 바빠서, 주말에는 애들 때문에 손도 못 대고 있다가 일요일 밤에 다행히 애들이 일찍 자는 바람에 시간이 좀 나서 컴퓨터 앞에 앉았습니다. 사실 마라톤 매치는 코딩하는 시간보다 생각하는 시간이 많이 필요합니다. 출퇴근 시간에 이런 저런 생각을 하다보면 시간도 잘 가고 좋습니다.
마라톤 매치가 arena에 들어가서 그런지 생각보다 많은 사람들이 등록을 하셨더군요. 우리나라 사람도 8명인가가 등록을 하셨는데.. 대부분 submission을 하지 않으셔서 안타깝습니다. 현재 점수가 있으신분이 7명인가 그래서 국가 순위에도 Korea는 빠져 있습니다. 어서 10명이 되기를 바랍니다.
일단, 도형 안에 들어가는 한 점을 찾습니다.
그 점에서 22.5도 마다 binary search 하는 방법으로 도형안에 들어가는 점을 찾습니다.
그렇게 생성되는 점들을 가지고, 다각형의 넓이를 구합니다.
2500점 만점에 2173점.. 저조합니다. 다음번엔 파란색으로 되겠더군요..
처음 시도는 디버깅 작업때문에 시간이 많이 걸립니다.
그래서 끝난 시간이 새벽 3시 -_-;
출근 해야 되는데 큰일 났습니다.
2차 시도 -
월요일.. 새로운 생각이 떠올랐습니다.
한 점을 찾고, 상하좌우로 binary search를 하여 4점을 찾습니다.
그 점들로 다각형을 만듭니다.
그리고, 각 변의 중점을 처음 점에서 일정한 크기만큼 증가시켜 검사를 합니다.
polygon 안에 있다고 나오는 점들로 다시 다각형을 만들고, 위를 반복합니다.
11시 반 경에 2차 시도를 했는데..
결과는 0점 ㅠ_ㅠ
배열의 크기를 너무 크게 잡아서 1024 MB의 메모리 제한을 초과한 것 같습니다.
한번 시도를 하면 4시간동안은 못하기 때문에 일단 취침..
3차 시도 -
화요일 아침.. 일어나자 마자 배열의 크기를 줄여 다시 제출하였습니다.
결과는 2353점.
180점 정도 올랐습니다. 흡족해 하며 출근을 했습니다.
4차 시도 -
제가 만든 다각형은 제출된 다각형보다 작기 때문에 적당한 보정치가 필요할 것 같습니다.
이런 거 계산할 때는 수학적인 방법으로 계산해야 하나.... 그런 것 없습니다.
1/2, 2/3 등등 몇가지 값을 만들어서 테스트 케이스를 5000개 정도 만들어서 회사 서버에서 냅다 돌렸습니다.
오전에 걸었는데.. 퇴근할때쯤 결과가 나오더군요.
가장 좋은 값으로 보정치를 집어넣었습니다.
2370점. 17점 올랐습니다.
5차 시도 -
이때 등수가 57등 정도였던걸로 기억됩니다.
순위예상사이트에서 계산해보니 1500점이 아슬아슬 합니다.(이런 사이트도 만들고, 대단합니다.)
하루가 남았으니, 순위는 더 떨어질 건데 다 나은 방법을 찾아야 할 것 같습니다.
아예 새로운 방법을 고민하기에는 시간이 부족하고..
in에만 신경쓰지 말고, out을 고려해보는게 어떨까 합니다.
in-out 뒤에는 out 이라는 생각이 들어.. 점을 하나 찍어볼때마다 모든 점의 in-out pair를 체크하여, out부분을 표시하였습니다.
각 변의 중점에서 중심을 상대로 연장하여 체크하는 것을 각 변에서 수직으로 증가시키도록 변경하였습니다.
폭이 아주 좁은 도형인 경우 넓이가 많이 근접해 지게 됩니다.
20초 시간제한에 걸리지 않을까 걱정했는데.. 2초도 안걸리는군요.
좀 더 복잡하게 했어야 하나 하는 생각을 해보지만.. 시간이 없어서 포기.
그렇게 시도를 하니, 2432점 47등입니다. 아이디는 노란색깔을 유지할 것 같습니다.
6차 시도 -
보정치를 계산해야 되는데..
집 컴퓨터가 느려서 많은 테스트를 해보기 힘들었습니다.
대충 계산해서 마감 3분전에 제출을 하니..
2441점.. 42등입니다. 이정도면 안정권이 아닐까 합니다.
provisional score 1등은 jdmetz님. 2500점 만점에 2493.68점.. 괴물입니다.
시스템 테스트 전의 최종 순위입니다. -> http://www.topcoder.com/longcontest/?module=ViewStandings&rd=10929
마라톤 매치는 지금부터가 재미있습니다.
게임 도중에는 각자의 시도에 대한 토론이 금지되어 있습니다.
Forum에 post your approach라는 글이 올라오면서 참가자들이 각자의 해결방법을 올리고, 거기에 대한 토론이 이루어집니다.
저는 영어가 짧은 관계로 글을 잘 올리지는 않지만.. 볼때마다 느끼는 거지만 세상에는 참 똑똑한 사람 많습니다. ㅎㅎ
시스템 테스트는 각자의 소스를 대량의 테스트를 하여 결과를 만듭니다.
결과가 나오려면 1주일정도 걸리고, 순위가 바뀌는 경우도 많습니다.
1등한 사람의 소스를 분석해보는 것도 재밌습니다.
이번 jdmetz의 소스는 도무지 이해가 되지 않는군요.
제 생각을 두서없이 나열하다 보니 글이 엉망입니다. 양해를 부탁드립니다.
다음번 마라톤매치는 10일 밤에 열립니다.
2주일짜리 문제군요..
많은 분들의 참석을 기다립니다.
하나반
아직 최종결과가 나오지 않았지만, 나름 후기를 먼저 적어봅니다. MM에 관심을.. ^^
개인적으로 이번시합이 매우 중요한 대회였습니다.
현재 스코어 1502점.. 3점만 떨어지면 아이디가 파란색으로 바뀌게 되는... -_-;; 벼랑끝에 몰린 심정으로 대회에 임했더랬습니다.
추석 때 부산에서 서울까지 9시간에 걸친 운전..
피곤하긴 한데 SRM도 있고 해서... 컴퓨터앞에 앉았습니다.
문제는 PolygonArea
대충 설명하자면 10 * 10 의 square에 존재하는 다각형의 넓이를 계산하라~.
한 점을 찍으면 그 점이 다각형의 안에 존재하는지 밖에 존재하는지를 알려주는 라이브러리를 제공한다.
다각형은 5~20각형이고, 점을 찍을 수 있는 횟수는 100~300 사이에서 지정된다.
호~ 구미가 땡기는 문제입니다.
- 1차 시도 -
평일은 회사 일이 바빠서, 주말에는 애들 때문에 손도 못 대고 있다가 일요일 밤에 다행히 애들이 일찍 자는 바람에 시간이 좀 나서 컴퓨터 앞에 앉았습니다. 사실 마라톤 매치는 코딩하는 시간보다 생각하는 시간이 많이 필요합니다. 출퇴근 시간에 이런 저런 생각을 하다보면 시간도 잘 가고 좋습니다.
마라톤 매치가 arena에 들어가서 그런지 생각보다 많은 사람들이 등록을 하셨더군요. 우리나라 사람도 8명인가가 등록을 하셨는데.. 대부분 submission을 하지 않으셔서 안타깝습니다. 현재 점수가 있으신분이 7명인가 그래서 국가 순위에도 Korea는 빠져 있습니다. 어서 10명이 되기를 바랍니다.
일단, 도형 안에 들어가는 한 점을 찾습니다.
그 점에서 22.5도 마다 binary search 하는 방법으로 도형안에 들어가는 점을 찾습니다.
그렇게 생성되는 점들을 가지고, 다각형의 넓이를 구합니다.
2500점 만점에 2173점.. 저조합니다. 다음번엔 파란색으로 되겠더군요..
처음 시도는 디버깅 작업때문에 시간이 많이 걸립니다.
그래서 끝난 시간이 새벽 3시 -_-;
출근 해야 되는데 큰일 났습니다.
17년 전