안녕하세요 Round 1 에 이어서 에디토리얼을 쓰고 있네요.
이번 MM Round2는 Round1에서 상위 250명과 시드를 받은 50명을 합쳐서 300명이 참가자격이 있었구요. Round2에 참가하지 못하는 사람들을 위해 MM52가 같이 열렸습니다. R2에서 100명이 R3에 진출하게 되고 R3에서 50위를 하면 티셔츠를 받을수가 있습니다 +_+.. 10위안에 드는 기적이 일어나면 파이널 라운드에 갈 수 있구요...
일단 문제입니다.
문제 링크
N개의 기어가(N은 짝수)의 톱니수가 주어집니다. 이 N개의 기어를 K개의 평면에 층층이 배치해서 이 기어를 둘러싸는 직사각형의 넓이가(부피가 아님)최소가 되도록 하는것이 문제입니다. 이 때 마지막 출력기어의 토크가 반드시 최대가 되어야 합니다(원래 문제에는 돌아가는 속도를 가장 느리게하는 것으로 되어있지만 전 토크를 최대로 하는것으로 생각하는게 편하더군요). 직사각형은 축에 평행합니다.
좀더 설명하자면 첫번째 기어의 축이 동력을 가지고 있습니다. 그럼 첫번째 기어가 맞물려 있는 두번째 기어에 동력을 전달하게 되고 이때 두 기어의 톱니의 숫자에 반비례하여 토크가 증가하게 됩니다. 이렇게 주욱 연결고리를 타고 마지막 기어까지 동력이 전달되는데 이때 마지막 기어의 속도가 반드시 최소가 되어야 합니다. 이 조건을 만족하지 못하면 0점 입니다.
기어의 톱니수를 T라면 그 기어의 반지름은 10T가 됩니다. 반지름이 각각 T1, T2인 두 기어의 거리가 10*(T1+T2) 이내가 되면 두 기어는 오버랩되는데, 오버랩되는 길이가 [9, 10] 사이가 되면 두 기어는 서로 맞물려 돌아가게 됩니다. 저 법위를 벗어나서 기어가 겹치게 되면 이는 불법이구요 0점을 받게됩니다.
모든 기어는 중심축을 가지고 있는데요 이 중심축은 반지름이 10이고 모든 평면을 지나 갑니다. 따라서 이 축에 끼어진 기어들을 제외한 다른 어떤 기어도 축과 겹쳐서는 안됩니다(겹치면 0점). 다른 평면에 있는 두 개의 기어의 중심좌표의 거리가 0.01이내가 되면 두 기어는 같은 중심축에 끼어져 있는것으로 봅니다.
추가
- 처음과 마지막 축을 제외한 모든 축에는 두 개의 기어가 있고 이들은 각각 다른축에 있는 기어중 하나와 맞물립니다.
- 큰기어가 작은기어에게 맞물려 동력을 전달할 때 회전속도가 떨어집니다.
- N개의 모든 기어를 다 사용할 필요는 없습니다. (어쨌든 토크만 최대로 만들면 됨)
- 시간제한은 30초이고 메모리는 1024MB를 사용할 수 있습니다.
- 같은 축에 있는 두 개의 기어는 동일한 속도로 회전합니다.
Constraint
- 기어의 크기는 10~100 사이의 랜덤넘버입니다.
- 정수 M이 5~40 사이에서 랜덤으로 선택됩니다.
- 각 기어의 톱니수는 M과 50사이의 랜덤넘버입니다.
- 층의 수는 3~6 사이입니다.
관전기
이번 마라톤은 1위와 컷오프까지의 솔루션의 성능차가 그리 크지 않아 마지막까지 피말리는 매치였는데요. 마지막날에는 Full submission의 결과를 보기위해서 2시간을 넘게 기다려야 할만큼 submission이 폭주하기도 했습니다. 혹자는 Linden Lab의 서밋이 10분 이상걸린다며 포럼에 불평을 하기도 했습니다. (Linden Lab Full Submissions)
이번 매치에서 윈을 차지하기 위한 경쟁은 압도적인 포스를 내뿜은 ACRush덕분에 싱겁게 끝나버렸습니다. 대회 초반부터 막바지까지 ACRush, chokudai, Psyho가 1위 자리를 놓고 3파전을 벌였는데 chokudai가 19번이나 서밋을 하면서 1위를 하기위한 엄청난 노력을 하였음에도 불구하고 ACRush는 그게 머 어쨋냐는 듯이 무려 23번의 서밋을 하면서 1위 자리를 굳건히 지켰습니다. 반면 Psyho는 9번의 서밋을 하였네요.
100테스트 결과 ACRush가 2위와 2점 정도의 차이로 앞서고 있기 때문에 1위를 지킬것이 거의 확실시되는 가운데, 저는 개인적으로 101위를 누가 차지하게 될지가 궁금하군요
우리나라에서는 저(ilyoan)를 포함해서, nocut98, ryuwonha, JeHyun (이상 탑코더 핸들) 님들이 참가했구요. 저랑 nocut98 님이 컷을 통과할것으로 보입니다.
접근방법들
Post your approach 쓰레드에 이번 마라톤에 참가했던 분들이 열심히 자신의 접근방법을 올렸습니다. 무려 23번씩이나 Submit을 하면서 압도적인 포스를 풍기면서 1위를 한 ACRush는 글을 올리지 않았는데요.. 거의 대적할 만한 점수를 얻은 chokudai와 psyho등을 비롯한 상위랭커들이 자신의 접근방법을 설명해 놓았습니다. ACRush도 크게 다르진 않을듯싶구요.
대부분의 R3진출자들은 아래 그림처럼 톱니바퀴를 지그재그로 배치하는 전략을 선택한 것 같네요
기어를 이렇게만 배치해도 기본적으로 70점이 넘는 점수를 얻을 수 있었던 것으로 보입니다. 여기에 기어를 효율적으로 배치하기 위한 휴리스틱과 SA를 접목하여 점수를 최대한 끌어올리는 것이 대부분의 참가자들의 접근방법이 아니었나 싶군요..
Psyho는 K가 3인경우 이런식으로 기어를 지그재그로 배치한 반면 K가 4이상인 케이스에서는 N의 크기에 따라 기어를 4층으로 쌓는 방법을 선택했다고 합니다. Psyho의 방법은 확실히 기어를 겹치는 면적을 넓게 만들어주기 때문에 점수의 상승을 가져오게 되겠네요. chokudai도 여러층에 걸쳐 기어를 배치한것으로 보입니만, 기어를 지그재그로 배치한 것은 아니고 단지 결과를 보면 지그재그로 배치한 것과 비슷한 모양을 하고 있습니다.
저는 면적을 최소화 하기 위해서는 기어들끼리 겹처지는 면적을 최대로 해야한다고 생각을 했고 그러려면 바운더리가 정사각형이 되는것이 가장 이상적이라고 생각했었습니다. 그래서 택한 전략은 배치할 기어의 순서를 미리 정하고 시작기어를 아무네나 놓고 그 다음 기어들을 시계방향으로 돌면서 배치를 하였습니다. 이전 기어가 배치된 각도를 0이라고 하면 이 각을 기준으로 0~180도 사이에서 가장 겹치는 면적이 넓은 좌표에 다음 기어를 배치하도록 하였고 0~180도 사이에 가능한 점이 없으면 -0 ~ -180도 사이에서 찾습니다.
기어의 배치순서가 정해지면 배치는 결정적으로 이루어지기 때문에 SA에서 고려할 사항은 배치의 순서를 어찌할까였는데요.. 저는 두개의 기어의 순서를 바꿔서 배치해본 후 결과가 좋아지면 가져가고 결과가 나빠지면 롤백하도록 하였습니다. 사실 SA라고 하기엔 좀 거시기(??)한데.. 어쨌든 점수향상에는 도움이 되었습니다. 이런 방법으로는 80~82점 정도의 점수를 얻을 수 있지 않았을까 생각합니다.
나머지 2~3점을 더 올릴수 있었던 것은 막판에 발견한 버그 덕분인데요;; 코드 최적화를 하던 도중 작은 버그를 만들었는데 이 버그가 기어의 배치를 항상 시계방향으로 하지 않고 어쩌다 한 번씩 반시계방향으로 배치하게 만들더군요.. 그 결과 지그재그 모양으로 기어가 배치가 되었구요. 버그를 고치려고 하는 순간 점수를 보니 엄청나게 향상된 솔루션을 밷어내는 케이스가 존재하는것을 발견하였습니다. 모든 사람들이 알고있던 지그재그배치의 위력을 그 때 깨닳고 이 버그를 적절히 이용하기로 하였고, 버그가 보답을 해주었습니다.
버그 덕분에 편안히 R3에 진출하게 되었는데 R3에서도 열심히 해서 좋은 성적을 내는 것을 목표로 해야겠네요. 10위에 들어서 온사이트에 가면 더할나위 없겠지만 일차 목표는 티셔츠를 받는것으로 하고 혹시 막판에 20위 언저리에 있으면 온사이트를 위한 올인을 하게될것 같습니다. ㅠㅠ 노컷님께서는 휴가까지 써서라도 마라톤에 올인하시겠다고 하시더군요. ㅋㅋㅋ
Psyho가 1등 이면서도 서밋 계속하는 걸로 악명이 높은데, 이번에는 린든랩때문인지 좀 덜하더군요(이건 통과만 하면 되고 린든랩은 상금이 ㄷㄷㄷ ㅎㅎㅎ) 사실 저는 회사에서 눈치보면서 해도 되는데 양심에 찔리고, 그렇다고 퇴근후에 하자니 피곤하고 주말에는 가끔 약속 있고 이러면 각이 잘 안 나오더라구요. 아무튼 R3 진출하게 될지 모르겠지만, 통과하면 올인입니다. ㅎㅎㅎ
에디토리얼 성실하게 써주셔서 감사합니다^^ 아 읽는 분들을 위해 기어의 회전수를 줄이는 건 그냥 기어를 반으로 나눠서 큰거랑 작은 거랑 매치하면 마지막 기어에서는 항상 최소의 회전비가 나옵니다.
ILyoan
안녕하세요 Round 1 에 이어서 에디토리얼을 쓰고 있네요.
이번 MM Round2는 Round1에서 상위 250명과 시드를 받은 50명을 합쳐서 300명이 참가자격이 있었구요. Round2에 참가하지 못하는 사람들을 위해 MM52가 같이 열렸습니다. R2에서 100명이 R3에 진출하게 되고 R3에서 50위를 하면 티셔츠를 받을수가 있습니다 +_+.. 10위안에 드는 기적이 일어나면 파이널 라운드에 갈 수 있구요...
일단 문제입니다.
문제 링크
N개의 기어가(N은 짝수)의 톱니수가 주어집니다. 이 N개의 기어를 K개의 평면에 층층이 배치해서 이 기어를 둘러싸는 직사각형의 넓이가(부피가 아님)최소가 되도록 하는것이 문제입니다. 이 때 마지막 출력기어의 토크가 반드시 최대가 되어야 합니다(원래 문제에는 돌아가는 속도를 가장 느리게하는 것으로 되어있지만 전 토크를 최대로 하는것으로 생각하는게 편하더군요). 직사각형은 축에 평행합니다.
좀더 설명하자면 첫번째 기어의 축이 동력을 가지고 있습니다. 그럼 첫번째 기어가 맞물려 있는 두번째 기어에 동력을 전달하게 되고 이때 두 기어의 톱니의 숫자에 반비례하여 토크가 증가하게 됩니다. 이렇게 주욱 연결고리를 타고 마지막 기어까지 동력이 전달되는데 이때 마지막 기어의 속도가 반드시 최소가 되어야 합니다. 이 조건을 만족하지 못하면 0점 입니다.
기어의 톱니수를 T라면 그 기어의 반지름은 10T가 됩니다. 반지름이 각각 T1, T2인 두 기어의 거리가 10*(T1+T2) 이내가 되면 두 기어는 오버랩되는데, 오버랩되는 길이가 [9, 10] 사이가 되면 두 기어는 서로 맞물려 돌아가게 됩니다. 저 법위를 벗어나서 기어가 겹치게 되면 이는 불법이구요 0점을 받게됩니다.
모든 기어는 중심축을 가지고 있는데요 이 중심축은 반지름이 10이고 모든 평면을 지나 갑니다. 따라서 이 축에 끼어진 기어들을 제외한 다른 어떤 기어도 축과 겹쳐서는 안됩니다(겹치면 0점). 다른 평면에 있는 두 개의 기어의 중심좌표의 거리가 0.01이내가 되면 두 기어는 같은 중심축에 끼어져 있는것으로 봅니다.
추가
- 처음과 마지막 축을 제외한 모든 축에는 두 개의 기어가 있고 이들은 각각 다른축에 있는 기어중 하나와 맞물립니다.
- 큰기어가 작은기어에게 맞물려 동력을 전달할 때 회전속도가 떨어집니다.
- N개의 모든 기어를 다 사용할 필요는 없습니다. (어쨌든 토크만 최대로 만들면 됨)
- 시간제한은 30초이고 메모리는 1024MB를 사용할 수 있습니다.
- 같은 축에 있는 두 개의 기어는 동일한 속도로 회전합니다.
Constraint
- 기어의 크기는 10~100 사이의 랜덤넘버입니다.
- 정수 M이 5~40 사이에서 랜덤으로 선택됩니다.
- 각 기어의 톱니수는 M과 50사이의 랜덤넘버입니다.
- 층의 수는 3~6 사이입니다.
관전기
이번 마라톤은 1위와 컷오프까지의 솔루션의 성능차가 그리 크지 않아 마지막까지 피말리는 매치였는데요. 마지막날에는 Full submission의 결과를 보기위해서 2시간을 넘게 기다려야 할만큼 submission이 폭주하기도 했습니다. 혹자는 Linden Lab의 서밋이 10분 이상걸린다며 포럼에 불평을 하기도 했습니다. (Linden Lab Full Submissions)
이번 매치에서 윈을 차지하기 위한 경쟁은 압도적인 포스를 내뿜은 ACRush덕분에 싱겁게 끝나버렸습니다. 대회 초반부터 막바지까지 ACRush, chokudai, Psyho가 1위 자리를 놓고 3파전을 벌였는데 chokudai가 19번이나 서밋을 하면서 1위를 하기위한 엄청난 노력을 하였음에도 불구하고 ACRush는 그게 머 어쨋냐는 듯이 무려 23번의 서밋을 하면서 1위 자리를 굳건히 지켰습니다. 반면 Psyho는 9번의 서밋을 하였네요.
100테스트 결과 ACRush가 2위와 2점 정도의 차이로 앞서고 있기 때문에 1위를 지킬것이 거의 확실시되는 가운데, 저는 개인적으로 101위를 누가 차지하게 될지가 궁금하군요
.png)
우리나라에서는 저(ilyoan)를 포함해서, nocut98, ryuwonha, JeHyun (이상 탑코더 핸들) 님들이 참가했구요. 저랑 nocut98 님이 컷을 통과할것으로 보입니다.
접근방법들
Post your approach 쓰레드에 이번 마라톤에 참가했던 분들이 열심히 자신의 접근방법을 올렸습니다. 무려 23번씩이나 Submit을 하면서 압도적인 포스를 풍기면서 1위를 한 ACRush는 글을 올리지 않았는데요.. 거의 대적할 만한 점수를 얻은 chokudai와 psyho등을 비롯한 상위랭커들이 자신의 접근방법을 설명해 놓았습니다. ACRush도 크게 다르진 않을듯싶구요.
대부분의 R3진출자들은 아래 그림처럼 톱니바퀴를 지그재그로 배치하는 전략을 선택한 것 같네요
기어를 이렇게만 배치해도 기본적으로 70점이 넘는 점수를 얻을 수 있었던 것으로 보입니다. 여기에 기어를 효율적으로 배치하기 위한 휴리스틱과 SA를 접목하여 점수를 최대한 끌어올리는 것이 대부분의 참가자들의 접근방법이 아니었나 싶군요..
Psyho는 K가 3인경우 이런식으로 기어를 지그재그로 배치한 반면 K가 4이상인 케이스에서는 N의 크기에 따라 기어를 4층으로 쌓는 방법을 선택했다고 합니다. Psyho의 방법은 확실히 기어를 겹치는 면적을 넓게 만들어주기 때문에 점수의 상승을 가져오게 되겠네요. chokudai도 여러층에 걸쳐 기어를 배치한것으로 보입니만, 기어를 지그재그로 배치한 것은 아니고 단지 결과를 보면 지그재그로 배치한 것과 비슷한 모양을 하고 있습니다.
저는 면적을 최소화 하기 위해서는 기어들끼리 겹처지는 면적을 최대로 해야한다고 생각을 했고 그러려면 바운더리가 정사각형이 되는것이 가장 이상적이라고 생각했었습니다. 그래서 택한 전략은 배치할 기어의 순서를 미리 정하고 시작기어를 아무네나 놓고 그 다음 기어들을 시계방향으로 돌면서 배치를 하였습니다. 이전 기어가 배치된 각도를 0이라고 하면 이 각을 기준으로 0~180도 사이에서 가장 겹치는 면적이 넓은 좌표에 다음 기어를 배치하도록 하였고 0~180도 사이에 가능한 점이 없으면 -0 ~ -180도 사이에서 찾습니다.
기어의 배치순서가 정해지면 배치는 결정적으로 이루어지기 때문에 SA에서 고려할 사항은 배치의 순서를 어찌할까였는데요.. 저는 두개의 기어의 순서를 바꿔서 배치해본 후 결과가 좋아지면 가져가고 결과가 나빠지면 롤백하도록 하였습니다. 사실 SA라고 하기엔 좀 거시기(??)한데.. 어쨌든 점수향상에는 도움이 되었습니다. 이런 방법으로는 80~82점 정도의 점수를 얻을 수 있지 않았을까 생각합니다.
나머지 2~3점을 더 올릴수 있었던 것은 막판에 발견한 버그 덕분인데요;; 코드 최적화를 하던 도중 작은 버그를 만들었는데 이 버그가 기어의 배치를 항상 시계방향으로 하지 않고 어쩌다 한 번씩 반시계방향으로 배치하게 만들더군요.. 그 결과 지그재그 모양으로 기어가 배치가 되었구요. 버그를 고치려고 하는 순간 점수를 보니 엄청나게 향상된 솔루션을 밷어내는 케이스가 존재하는것을 발견하였습니다. 모든 사람들이 알고있던 지그재그배치의 위력을 그 때 깨닳고 이 버그를 적절히 이용하기로 하였고, 버그가 보답을 해주었습니다.
버그 덕분에 편안히 R3에 진출하게 되었는데 R3에서도 열심히 해서 좋은 성적을 내는 것을 목표로 해야겠네요. 10위에 들어서 온사이트에 가면 더할나위 없겠지만 일차 목표는 티셔츠를 받는것으로 하고 혹시 막판에 20위 언저리에 있으면 온사이트를 위한 올인을 하게될것 같습니다. ㅠㅠ 노컷님께서는 휴가까지 써서라도 마라톤에 올인하시겠다고 하시더군요. ㅋㅋㅋ
15년 전
2개의 댓글이 있습니다.
nocut98
Psyho가 1등 이면서도 서밋 계속하는 걸로 악명이 높은데, 이번에는 린든랩때문인지 좀 덜하더군요(이건 통과만 하면 되고 린든랩은 상금이 ㄷㄷㄷ ㅎㅎㅎ) 사실 저는 회사에서 눈치보면서 해도 되는데 양심에 찔리고, 그렇다고 퇴근후에 하자니 피곤하고 주말에는 가끔 약속 있고 이러면 각이 잘 안 나오더라구요. 아무튼 R3 진출하게 될지 모르겠지만, 통과하면 올인입니다. ㅎㅎㅎ
에디토리얼 성실하게 써주셔서 감사합니다^^ 아 읽는 분들을 위해 기어의 회전수를 줄이는 건 그냥 기어를 반으로 나눠서 큰거랑 작은 거랑 매치하면 마지막 기어에서는 항상 최소의 회전비가 나옵니다.
15년 전 link
김우현
ILyoan 님 MM 에디토리얼 잘 보고 있습니다.
R3에서 좋은결과내셔서 파이널 가셨으면 좋겠네요!
한국분들 화이팅^^!
15년 전 link
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.