간단히 문제 해설을 드리면, 하나의 곡선이 있습니다. 이걸 최소한 변형해서 N개의 곡선을 만들어서 주면, Topcoder에서 그 곡선을 변형한 다음 다시 줍니다. "이건 몇 번째 곡선을 변형한 거게?" 이렇게 임의의 곡선을 선택해서 100번 물어보고, 리턴값으로는 0부터 (N-1)까지 문제의 번호를 주면 됩니다.
채점 방식은 (변형양의 제곱 * 2^오답의 갯수) 입니다. 여기서 최소의 점수를 얻는 게 중요한데, 일단 하나라도 틀릴때마다 2배씩 늘어나므로 100개 중 5개라도 틀리면, 변형한 정도에 32배를 곱하게 되겠죠.
각 문제마다 최소의 점수를 반환할 경우 1000점을 얻게 됩니다. 100번의 테스트를 하는 거 같으니 최대 점수는 10만점이 되겠죠.
아무튼 시작 하자 마자 wleite 이 무지막게 하게 치고 올라갔죠. 대략 6만점 정도 였던듯 시간이 좀 지나서 venco가 6만점을 얻고 wleite를 3만점정도로 만들어 버립니다. 일주일쯤 지나 Loks가 등장해서 상당한 점수차로 3파전이 되었죠. 전 그 3명중에 1등이 나오는 줄 알았습니다;;;
그렇게 셋이서 6만~3만 정도의 점수로 치고박고 하고 있는데, (5등의 점수는 만점정도...)
paranoia가 등장하면서 혼자 7만점인가 받으면서 나머지 셋을 3-4만점으로 만들어 버리더군요. 와- 쩐다...이러고 있는데
대회 후반이 되니 psyho랑 wata가 등장하면서 다른 애들을 바로로 만들고 투톱 체제를 형성 하더군요. 둘이서 7만점대고 다른 3등부터는 4만점이 안되게요...초반에 압도적 1등이던 wleite는 10위권 밖으로 밀려서 들어올 생각을 안하네요.
제일 재밌는 건 마지막 날이었는데, 꽤나 늦게 ploh가 치고 올라옵니다. Psyho는 계속 서밋을 하면서 점수를 차차 늘려서 wata와의 점수 차이를 벌렸구요. 그래서 결국 psyho, wata, ploh의 순서로 순위가 결정되고, 마지막 10분을 남겨놓고, 이 3명이 전부 마지막 서밋을 하네요?
wata, psyho, ploh 순서로 서밋 결과가 나오고, 순간 wata가 8만점을 넘었다가 psyho가 재역전해서 다시 1등...
...이러고 있는데, 게시판에 ploh가 이런 말을 남깁니다. 내가 지금까지 한 건 전체가 아니라 부분만 테스트 한 점수일 뿐이다. C값이 1~10인데, 각 서밋마다 적당한 C값만 처리하도록 한거죠. 아래처럼...
1. C = 5, 6
2. C = 7, 8
3. C = 1, 2, 3, 4
4. C = 9, 10
5. C = 9, 10 (with an improvement that decreased the score slightly)
6. C <= 8
7. The real thing (최종 서밋용, 모든 C값에 대해서 처리하기)
즉 전체 테스트는 최후의 서밋에서 나오도록 한 거죠.... 그러고는 결국 현재는 2위인 psyho와 1만점 차이로 1등이 되었네요.
실제 결과는 나와봐야 알지만, 이 정도 점수 차이를 뒤집기는 어려워 보입니다... 같이 대회에 참가한 제현군이 물어봤더니 자신은 응용수학을 전공하고 있어서 이런 문제에 상당히 강하다고 하더군요.
[문제 분석 + 개인적 후기]
별로 관심 없으시겠지만 그냥 간단히 저의 접근 방법은 곡선 변형의 특성상 수평성분은 쉽게 제거가 되는데, 수직 성분은 일정 영역의 평균을 내면 상당히 남아있게 된다고 분석했구요. 그래서 수직성분이 일정한 부분이 어디일까? 예를 들어 가파르게 올리가는 변곡점에서는 일정한 값을 유지하기가 어렵겠죠. 그래서 선택한게 극대/극소점들에 약간 더하는 걸로 했구요.
각 극대/극소의 갯수가 7개라면, 2진법으로 자신의 번호를 표시해 놓는 거죠. 예를 들어 3번은 0000011 이런식으로요.
대충 그렇게 코딩해 놓고, 1000점만 되다오 하고 서밋했더니 1500점으로 나름 20위권이더군요. 버그를 잡고 개선해서 올렸더니 간신히 20위권 안팍을 들락날락. 근데 그 방식으로는 최적화 해봤자 1만점을 넘는 건 불가능해 보여서 다른 방법을 찾아봤구요. 확률/통계를 이용해서 끝점의 변화량을 구해서 마킹값을 최소화하는 방법을 고안해서 모듈 테스트를 돌렸더니 훌룡하더군요. 그때부터 그 방식을 이용하려고 했는데, 이게 처음에 너무 장대하게 시작했더니 (각 극대/극소를 다 체크해내서 그 중에 극점의 변화량에 제일 적은 -> 제일 완만한 극대/극소점에다 마킹, 끝을 좀 뭉퉁하게 깍아서 변화량 줄이기, 평균값을 구하는 넓이를 조정...) 마지막날 쯤에는 뭔가 문제가 생겨서 에러율이 엄청 올라가더군요
결국 그래서 자존심(새로운 방법)도 버리고 그냥 처음의 방법을 좀 만 바꾸고 엎드려 탑코더의 자비를 비는 방식을 선택했습니다. ㅋㅋㅋ
nocut98
일단 저는 이번에 애당초 발려놔서 후기 쓸 입장도 아니고 그냥 관전기를 쓰겠습니다.
간단히 문제 해설을 드리면, 하나의 곡선이 있습니다. 이걸 최소한 변형해서 N개의 곡선을 만들어서 주면, Topcoder에서 그 곡선을 변형한 다음 다시 줍니다. "이건 몇 번째 곡선을 변형한 거게?" 이렇게 임의의 곡선을 선택해서 100번 물어보고, 리턴값으로는 0부터 (N-1)까지 문제의 번호를 주면 됩니다.
채점 방식은 (변형양의 제곱 * 2^오답의 갯수) 입니다. 여기서 최소의 점수를 얻는 게 중요한데, 일단 하나라도 틀릴때마다 2배씩 늘어나므로 100개 중 5개라도 틀리면, 변형한 정도에 32배를 곱하게 되겠죠.
각 문제마다 최소의 점수를 반환할 경우 1000점을 얻게 됩니다. 100번의 테스트를 하는 거 같으니 최대 점수는 10만점이 되겠죠.
아무튼 시작 하자 마자 wleite 이 무지막게 하게 치고 올라갔죠. 대략 6만점 정도 였던듯 시간이 좀 지나서 venco가 6만점을 얻고 wleite를 3만점정도로 만들어 버립니다. 일주일쯤 지나 Loks가 등장해서 상당한 점수차로 3파전이 되었죠. 전 그 3명중에 1등이 나오는 줄 알았습니다;;;
그렇게 셋이서 6만~3만 정도의 점수로 치고박고 하고 있는데, (5등의 점수는 만점정도...)
paranoia가 등장하면서 혼자 7만점인가 받으면서 나머지 셋을 3-4만점으로 만들어 버리더군요. 와- 쩐다...이러고 있는데
대회 후반이 되니 psyho랑 wata가 등장하면서 다른 애들을 바로로 만들고 투톱 체제를 형성 하더군요. 둘이서 7만점대고 다른 3등부터는 4만점이 안되게요...초반에 압도적 1등이던 wleite는 10위권 밖으로 밀려서 들어올 생각을 안하네요.
제일 재밌는 건 마지막 날이었는데, 꽤나 늦게 ploh가 치고 올라옵니다. Psyho는 계속 서밋을 하면서 점수를 차차 늘려서 wata와의 점수 차이를 벌렸구요. 그래서 결국 psyho, wata, ploh의 순서로 순위가 결정되고, 마지막 10분을 남겨놓고, 이 3명이 전부 마지막 서밋을 하네요?
wata, psyho, ploh 순서로 서밋 결과가 나오고, 순간 wata가 8만점을 넘었다가 psyho가 재역전해서 다시 1등...
...이러고 있는데, 게시판에 ploh가 이런 말을 남깁니다. 내가 지금까지 한 건 전체가 아니라 부분만 테스트 한 점수일 뿐이다. C값이 1~10인데, 각 서밋마다 적당한 C값만 처리하도록 한거죠. 아래처럼...
1. C = 5, 6
2. C = 7, 8
3. C = 1, 2, 3, 4
4. C = 9, 10
5. C = 9, 10 (with an improvement that decreased the score slightly)
6. C <= 8
7. The real thing (최종 서밋용, 모든 C값에 대해서 처리하기)
즉 전체 테스트는 최후의 서밋에서 나오도록 한 거죠.... 그러고는 결국 현재는 2위인 psyho와 1만점 차이로 1등이 되었네요.
실제 결과는 나와봐야 알지만, 이 정도 점수 차이를 뒤집기는 어려워 보입니다... 같이 대회에 참가한 제현군이 물어봤더니 자신은 응용수학을 전공하고 있어서 이런 문제에 상당히 강하다고 하더군요.
[문제 분석 + 개인적 후기]
별로 관심 없으시겠지만 그냥 간단히 저의 접근 방법은 곡선 변형의 특성상 수평성분은 쉽게 제거가 되는데, 수직 성분은 일정 영역의 평균을 내면 상당히 남아있게 된다고 분석했구요. 그래서 수직성분이 일정한 부분이 어디일까? 예를 들어 가파르게 올리가는 변곡점에서는 일정한 값을 유지하기가 어렵겠죠. 그래서 선택한게 극대/극소점들에 약간 더하는 걸로 했구요.
각 극대/극소의 갯수가 7개라면, 2진법으로 자신의 번호를 표시해 놓는 거죠. 예를 들어 3번은 0000011 이런식으로요.
대충 그렇게 코딩해 놓고, 1000점만 되다오 하고 서밋했더니 1500점으로 나름 20위권이더군요. 버그를 잡고 개선해서 올렸더니 간신히 20위권 안팍을 들락날락. 근데 그 방식으로는 최적화 해봤자 1만점을 넘는 건 불가능해 보여서 다른 방법을 찾아봤구요. 확률/통계를 이용해서 끝점의 변화량을 구해서 마킹값을 최소화하는 방법을 고안해서 모듈 테스트를 돌렸더니 훌룡하더군요. 그때부터 그 방식을 이용하려고 했는데, 이게 처음에 너무 장대하게 시작했더니 (각 극대/극소를 다 체크해내서 그 중에 극점의 변화량에 제일 적은 -> 제일 완만한 극대/극소점에다 마킹, 끝을 좀 뭉퉁하게 깍아서 변화량 줄이기, 평균값을 구하는 넓이를 조정...) 마지막날 쯤에는 뭔가 문제가 생겨서 에러율이 엄청 올라가더군요
결국 그래서 자존심(새로운 방법)도 버리고 그냥 처음의 방법을 좀 만 바꾸고 엎드려 탑코더의 자비를 비는 방식을 선택했습니다. ㅋㅋㅋ
15년 전