본문 바로가기
problem solving/TopCoder

TCO09 Marathon Match Round 2 - Gearing

toysmars 2009. 3. 19. 16:04
문제

주어진 기어를 잘 배치해서 마지막 기어의 속도를 최대로 낮추면서 기어들이 차지하는 면적을 최소화 하라



D-6

문제는 모두 이해한 것 같다. 

지금은 Psyho가 빠르게 1위로 치고 올라온 상황이다.

나의 상황은 뾰족한 방법이 떠오르지 않는 상황.... 100명이 R3에 진출하는데 어쩌면 어려울 것 같다는 생각이 든다. 




수업시간에 수업 안듣고 문제를 어떻게 풀지 생각해봤는데 가능성이 보이는 방안이 생각났다.

- 우선 기어를 동력을 주는 그룹(G1) 과 동력을 받는 그룹(G2)로 나눈다.
- G1과 G2 각각에 대해 기어가 나올 순서를 정한다.
- 이 순서가 유망한지 미리 검사한다.
- G1[k]가 G2[k]에 동력을 전달한다.
- G2[k]와 G1[k+1]은 같은 축에 묶여있다.
- 모든G1은 모든G2보다 작다

여기까지는 문제에서 주어진 사항이고..

- G1[0]를 위치시킨다.
- G2[0]를 G1[0]에 맞물려 위치시킨다.
- G1[1]은 G2[0]와 같은 위치에 있다. G1[1]이 위치할 평면을 정한다.
..
정리가 잘 안되는구나... 

- 어쨋든 다 위치 시키고 바운더리의 크기를 계산한다.

까지가 기어를 위치시키는 방법이고.. 정리를 좀 더 해야할 듯

기어를 위치시키고 나면 G1에서 두 개의 기어를 골라 순서를 바꾼다. G2에서도 마찬가지로 한다. 그리고 다시 기어를 위치시켜 보고 결과가 향상되면 가지고 가고 결과가 나빠지면 되돌린다.

30초 동안 계속 해보자......




새미나 시간에 새미나 안 듣고 계속 마라톤 생각 함

- 가급적 큰 기어를 먼저 배치한다.
- 시계 방향 혹은 반시계방향으로 기어를 배치한다.
- 새로 놓을 기어 G2[k]의 중심은 G1[k]의 중심으로 부터 G2[k].반지름 + G1[k]반지름 - 오버랩(9~10) 만큼 떨어져야한다. 그리고 기존에 놓은 {G2[1.... k-1] ∪ G1[0]} 의 원소 g에 대해 MAX(g.반지름, G2[k].반지름) + 축.반지름(=10) 만큼 떨어져야한다.
- 같은 평면상에 이미 배치한 기어들과 접촉되지 않아야 한다.
- 위의 조건을 만족하는 점들 중 이미 정한 방향(시계 혹은 반시계)방향에 위치한 점을 골라 기어를 놓는다.
- 주욱 계속...

코딩 가능해 보이고 가능성도 있어보이고 점수도 그럭저럭 나오긴 할 듯???????

지금 현재 상황은 Psyho가 여전히 1위하고 있고 그 뒤 4위까지 90점이 넘는 점수를 얻고 있다. 상대점수인대도 90점 이상이 4명인거 보면 이 4명 모두 최적에 거의 근접한것 같다.




D-5

구현에 상당히 어려움을 겪고 있다.

일단 두 원의 교점을 구하는 코드는 겨우겨우 구현했다.(고등학교 수학을 다 잊어버린듯 ㅠ)

현재 상황은  ACRush, Psyho, chokudai 가 1, 2, 3위를 달리고 있다. 특이한 점이 있는데 20명이 넘는 사람들이 39점대의 동일한 점수를 얻고 있다. 아마 다들 똑같이 구현한것 같은데... 아주 기본적인 아이디어로 간단히 구현하면 저 정도 점수가 나오는것 같다.



교점을 이용한 방법을 구현을 했는데 뭔가 잘 되지 않는다.

다른 방법을 생각해봐야겠다.



D-4

Submission 1 - Score: 51.72(81)

첫번째 서밋을 했다.

아직 점수를 많이 올려야 할 필요가 있다. ㅠㅠ

두 원의 교점을 이용하는 방법을 그대로 사용하였다. 하나 추가한게 있는데 새로운 기어를 추가하고 그 기어와 같은축에 놓이게 될 다음 기어까지 고려하여 교점을 구한 후 유망한 자리를 찾도록 하였다. 그리고 최종 배치후에는 0~360도 까지 회전하면서 면적이 가장 작게되는 경우를 찾는다.

기어는 반시계방향으로 돌면서 배치되도록 유도를 하려고 노력을 하였다. 다만 여러 케이스에서 뜻대로 되지 않는다..
기어의 배치를 유연하게 하는 방법을 생각해봐야겠다. 그리고 혹시나 0점을 받는 케이스가 존재하는지도 살펴봐야하겠다.

시간은 대략 10ms도 안쓰는 것 같은데... 30초를 충분히 활용할 수 있도록 수정을 조금 하는것도 고려할 사항




두번째 서밋을 기다리고 있다.
- 일단 0점을 받는 케이스는 없을 것으로 보인다.
- 29.5초를 활용하여 각각의 그룹(G1, G2)에서 두 개의 기어를 골라 배치되는 순서를 맞바꾸어 배치를 한 후 결과가 좋으면 유지하고 결과가 나빠지면 롤백한다.
- 배치를 하기 전에 미리 배치가 불가능한지 여부를 검사한다.
- 반시계방향으로 돌되(비주얼라이저에선 시계방향), 기존에 배치된 기어와 겹치는 면적이 가장 넓은 지점을 선택한다.
- 0~90도까지 0.01도 간격으로 돌면서 최적의 각도를 찾는다.

- 지역 최적해로 수렴하는 문제를 어찌 해결할것인지.. ㅠㅠ
- 아래 함수가 맞는건지..

bool ValidCheck() 
    {
        for (int i = 1; i < G1.size(); i++) {
            if (G1[i].r + G2[i].r - 9.99999 < G2[i-1].r + 10.000001) return false;
        }
        return true;
    }




Submission 2 - Score: 70.61(59th)
 
생각보단 점수가 많이 오르지 않은 것 같다. 기어를 배치하는 방법을 다시 생각해봐야할듯!!!

80정도를 받아야 안정권이 될듯하다.




Submission 3 - Score: 82.29(30th)

자다 깨서 서밋함. 생각보다 점수가 많이 오른것 같다.

- 버그를 수정하였다. (오버랩된 면적을 구하는 코드에 PI를 안 곱한 부분이 있었다)
- 0~90도 까지 0.1간격으로 체크한다.
- 코드 최적화를 좀 했다

버그를 수정한 것이 점수에 좀 영향을 미친것 같다.



Submission 4 - Score: 82.26(30th)

음.. 생각한 만큼 아주 초큼 점수가 오른 것 같다.(81.84 -> 82.26) 그래도 생각한 것 보단 너무 조금 올라서 좀 실망 ㅠㅠ

- 4초동안 anneal이 안되면 지금까지의 결과를 저장하고 첨부터 다시 공간 탐색을 시도한다.
 
점수를 올릴 수 있을만한 방법을 생각해보자
- GA를 사용한다. (될까?? 지역 최적화는 어찌하지??)
- 전체의 그림을 봤을 때 기어가 정사각형의 모양으로 배치되도록 유도한다(어떻게??)
- 버그를 심어본다
버그를 심는것이 가장 그럴듯해 보이는 이유는 뭐지 ㅠㅠ


Submission 5 - Score: 84.73(15th)

생각보다 점수가 너무 많이 올라서 놀라 자빠질뻔했다 ㅠㅠ (80.96 -> 84.73)

R1때와는 달리 사람들의 서밋 러쉬가 이어지고 있다. 1위를 위한 경쟁이 대단히 치열하다.. 나랑은 상관없는 일이지만 ㅋㅋ
- 처음에 기어를 랜덤으로 배치하게 수정
- 무조건 반시계방향으로 하는것이 아니라 진행방향을 기준으로 처음엔 오른쪽 중 오버랩이 가장 많은 곳을 찾고 오른쪽에 없으면 왼쪽으로 찾도록 수정
- 로테이트 구현에서 버그를 발견하여 고침
- 사용하지 않는 기어 선택하는 부분 에러 발견 ㅠㅠ
- 케이스별 공간 탐색 재시도 대기시간을 변경하도록 하였다
- 아주 약간의 코드 최적화

- 사용하지 않는 기어 선택부분에서 버그를 수정한게 점수를 올려준것으로 생각됨

오늘은 여기까지하고 자야지 ㅠㅠ



D-3

Submission 6 - 87.85(9th)

일어나보니 등수가 25등까지 밀려있었다 점수는 84.00점

더 이상 아이디어는 없고 코드를 최적화하고 있었는데 각도를 갱신하는 부분에 미묘하게 버그를 만들어버렸다. 근데 어쩐 일인지 기어가 신들린듯이 배치되더니 점수가 껑충 뛰어올랐다..  버그로 인한 현상은 기어가 항상 시계방향으로 배치되는 것이 아니라 가끔씩 반대 방향으로 배치가 된다는 것이다. 

이 버그가 동작을 하는 경우는 K가 3이고 M이 큰 경우인것 같은데 이 때 기어가 2줄로 이쁘게 지그재그로 배열이 되면서 엄청 좋은 점수를 얻어낸다.

역시 버그를 심는게 해결책이었어 ㅠㅠ 우왕ㅋ굿ㅋ

서밋결과 87.85점 까지 점수가 올랐다.. 생각보단 적게 오르는군
- 쓸데없는 계산을 하는 부분을 발견하여 하지 않도록 수정.
- 각도 계산 횟수를 1회 줄이려다 벌레가 기어들어감 -> 점수 상승???
- 버그를 적절히 이용하여 버그가 점수를 올려주는 케이스에서 버그가 작동하도록 함 -> 케이스를 좀더 살펴볼 필요가 있음(버그가 작동하는 케이스 vs 버그 없는게 좋은 케이스)

 

Submission 7 - 86.71(8th)

기어를 배치할 층을 선택할때 차례차례 순서대로 우선순위를 주던것을 이전 층의 다음층을 우선하도록 고쳐서 한번 서밋해봤다. 예상외로 점수가 올랐다(85.76 -> 86.71) 1점 정도는 랜덤값이 잘 나오느냐 잘 안나오느냐에 따라 달라질 수 있는 점수이기 때문에 크게 의미를 두고 있진 않지만 어느게 유리한지는 한 번 생각해 봐야겠다.



100% 버그있는코드로 서밋한번 해고 자려고 했는데 까먹고 VMware를 꺼버렸다... ㅠㅠ
다시키긴 귀찮고 내일 일어나서 해봐야지



D-2

모든케이스에 버그를 적용시켜봤다. 버그를 적용시켰다니 좀 막장같긴한데... 서밋을해보려고 했는데 큐가 넣무 밀려있어서 학교가서 해야겠다.


Submission 8 - 85.14(15th)

음.. 아무래도 케이스를 분석을 해서 버그가 힘을 내는 케이스에만 버그를 심는게 좋을듯하다.


Submission 9 - 85.46(12th)

Submission 7 에서 재시도 대신 3.5초간 5회 실행 후 가장 좋은 결과를 남은 시간동안 계속 강화시키는 전략을 사용해봤는데 생각만큼 결과가 좋지 않다.



마지막 서밋을 위해 100개의 케이스에 대해 테스트 시행 중

후보1. 버그쓰고 5트라이 후 하나 선택해서 최적화
후보2. 버그쓰고 트라이 후 개선 안되면 처음부터 재시도
후보3. 버그 안쓰고 5트라이 후 하나 선택해서 최적화
후보4. 버그 안쓰고 트라이 후 개선 안되면 처음부터 재시도



Submission 10 - 86.22(9th)

테스트 결과 5회 시도후 하나를 선택하는 방법보다 하나를 시도하다가 더 이상 개선이 안될 때 순서를 바꿔서 다시 시도해 보는 방법이 점수가 더 잘나오는것을 확인하였다. 버그의 사용유무에 대해서는 K가 4, 5 일때는 거의 모든 케이스에서 버그를 쓰는것이 결과가 좋고 K가 3, 6일때는 N과 M값에 따라 버그를 쓸지 안쓸지 결정을 하는것이 바람직해 보인다.

하지만 이런 결과로 봐서는 Submission 8에서 점수가 저렇게 떨어져선 안될것 같은데.... 200회 테스트를 해봐야겠다.



D-1

Submission 11 - 79.42(72th)

200회 테스트 결과를 반영해서 적절하게 적용해서 테스트를 했는데 결과가 이 모양이다. 이번 테스트는 망했군

어떻게 7점이나 떨어질 수 있는지 이해가 잘 되지 않는다.


- 재시도 할때 버그의 사용 유무를 바꿔가면서 한다.
- 0점을 받을 수 있는 가능성을 발견하여 가능성을 줄이는 코드를 넣었다. (200 테스트에 1회 발생: K가 작고 N이 엄청크고 M이 엄청 작은 케이스에서 발생가능, 기어를 끝까지 연결시키지 못하다 끝남)


Example 18 에서 무더기 TLE가 쏟아졌다... 단 두 줄 바꾼 코드가 tle를 만들어 냈을리가 없는데... 이건 뭘까..
아무래도 submitt 11도 TLE때문에 망한것 같다.



아... 이번 마라톤 싫다. 계속 이래저래 코드최적화만 하고 있고.. 시러시러 ㅠ 이번 서밋이 마지막이었으면 좋겠다. 87점 받자!!!

Submission 12 - 85.84(16th)

제길............................. 이 정도로 만족해야겠다. 
내일 submisson 11을 한 번 더 내보고 더 좋은걸 최종선택해야겠다.  

- 시간체크를 좀 더 여유롭게 하게 고쳤다. (TLE 나지마 ㅠㅠ)

오덕러쉬가 서밋하러 빠지니 0.5점이 올라간다.



D + 1

매치가 끝났다.

Standings
Handle Score Rank Last Submission Time Language Example Tests Submissions
*ACRush 95.29 1 03.18.2009 11:35:02 C++ 20 23
*olg2002 93.36 2 03.17.2009 20:42:42 Java 3 8
*chokudai 93.13 3 03.18.2009 05:48:57 C# 31 19
*Psyho 92.74 4 03.18.2009 02:03:42 C++ 13 10
*murrayr 90.57 5 03.17.2009 16:53:52 C++ 9 9
*ika 90.17 6 03.18.2009 11:43:58 Java 3 8
*Hephest 89.32 7 03.17.2009 12:59:37 C++ 22 10
*delicato 88.05 8 03.15.2009 18:20:20 C++ 4 5
*KOTEHOK 88.04 9 03.17.2009 00:44:44 C++ 12 10
*wata 88.04 9 03.18.2009 07:24:07 Java 8 9
*ploh 87.75 11 03.18.2009 07:59:39 C++ 0 5
*venco 87.74 12 03.17.2009 22:20:57 C++ 9 10
*tpelkone 87.51 13 03.18.2009 02:01:36 C++ 5 5
*JacoCronje 87.44 14 03.18.2009 11:42:39 C++ 8 8
*haskell-master 87.21 15 03.18.2009 01:52:17 C++ 7 6
*RatonulBolnav 87.09 16 03.18.2009 03:27:42 C++ 15 4
*AlexanderL 87.02 17 03.18.2009 11:59:09 C# 5 7
*wleite 86.98 18 03.17.2009 22:35:07 Java 13 10
*Squier 86.26 19 03.17.2009 07:46:35 C# 9 11
*ALight 85.73 20 03.18.2009 01:24:24 C++ 1 7
*prober 85.49 21 03.18.2009 02:10:03 C++ 6 4
*rahulgarg123 85.24 22 03.18.2009 02:22:31 C++ 22 15
*pashka 85.20 23 03.18.2009 11:20:04 Java 6 13
*ilyoan 84.87 24 03.17.2009 07:43:51 C++ 19 12
*Krzysan 84.87 24 03.18.2009 07:12:14 C++ 17 12

100개의 예비 테스트에서 24위를 기록했다.

post your approach 쓰레드에 상위 랭커를 포함한 이번 매치 참가자들이 자신의 접근방법을 올리고 있는데 한결같이 zig-zag로 기어를 배치하는 것에 기반을 두고 SA를 시도한 것 같다.

지금 와서 생각해보면 K=3 인 경우 Zig-Zag로 배치하는것보다 효율적으로 배치하는 방법이 없을것 같기도 하다. 하지만 K가 4이상인 경우에도 지그재그가 효율적인지는 아직 의문인데..  psyho의 점수를 보면 '상당히 효율적이었다' 라고 생각된다. 

나중에 최종 테스트 결과가 나오면 알겠지만 이번 마라톤에서 생각보다 점수차를 좁히지 못한 이유는 K=3인 경우에 zig-zag를 시도하지 않았기 때문인 것 같다. K가 4이상인 케이스에서도 zig-zag보다 점수가 낮다면 할 말 없음..


'problem solving > TopCoder' 카테고리의 다른 글

TCO09 Maratone Match Round 3 - Bounce Off My Result  (0) 2009.04.09
TCO09 Marathon Match Round 2 - Gearing Result  (0) 2009.03.25
TCO Marathon Match Round1 Result  (0) 2009.03.10
TCO 09 Marathon Match Round 1  (0) 2009.03.09
TopCoder SRM 427  (0) 2008.11.26

'problem solving/TopCoder' Related Articles

티스토리툴바