이글은 제가 문제를 풀면서 생각했던 것과 고민하던 것에 대해서 얘기하고 더 나은 해결책을 토의해보기 위해서 올립니다.
서밋 점수 기준으로 97.24점이었는데, 아무리 고쳐도 96.5~97.5 정도가 박스권으로 보였습니다. 10등이 99.46인데 제 느낌은 2점 차이가 20점 정도는 차이나는 것으로 보였습니다 -_-;;
특히 저를 밟고 상위 랭킹에 올라가신 (축하드립니다 ㅋㅋ) 일루님과 하나반님의 좋은 글도 기대하며 ㅎㅎ
<문제>
문제는 간단히 말하면, 심시티를 하는데 제한된 돈으로 편의점도 건설하고, 노래방도 짓고, 피씨방도 짓고, 커피숖도 지어야 합니다. 각각은 건설하는데 중요도와 건설비가 있구요. 건물은 모든 지역이 아닌 제한된 지역에만 지울 수 있구요
최종 점수는 100*100 평면에 각 격자점마다 사람이 살고 있고, 이 사람이 (각 서비스에 가기 위한 거리*중요도의 합)^2 입니다.
<생각>
1. 대개 MM은 복잡한 연산이 줄지어 있습니다. 건물을 하나 지어버리면 같은 위치에 다른 건물은 못 지을 뿐만 아니라 다른 종류의 건물의 위치까지 조정해줘야 합니다(쉽게 말하면 모든 요소들이 엮여 있는 것처럼 보입니다) 이런 경우에 한꺼번에 계산하면 부분 최적화에 빠져서 답이 안나옵니다. 그래서 주요 요소를 어떻게 나눠서 구하느냐가 문제로 보입니다. 결국 "1.거리합의 최소화, 2.몇개의 서비스를 놓느냐"로 나눴습니다.
1) 거리의 합이 적다고 총점이 낮게 나오는 건 아닙니다. 2개의 건물이 2점중 한점에 모여 있는 것과 각각 나눠져 있는 것은 같은 거리합 이더라도 총점은 다르게 나옵니다. 예를 들어 (1,1)^2+(4,4)^2 = 64, (1,4)^2,(4,1)^2 = 50 으로 같은 거리합을 가지고 있어도 다른 서비스에 따라서 총점은 변합니다.."만!!" 저는 일단 무조건 거리의 합을 최소화 하도록 했습니다.
2) 서비스를 몇개씩 놓느냐가 문제인데, 이것은 실제로 1개,2개,3개로 늘어날수록 효용이 줄어듭니다. 1개에서 2개로 늘어나는 게 5개에서 6개로 늘어날 때보다 비용 효과가 크죠. 해당 감소분은 직접 한번 놔보면 알 수 있습니다. 그래서 일단 처음에 다 1개씩 놓고, 하나를 추가했을 때 비용대비 최대한 이익(서비스*거리합)^2 이 되는 것을 하나씩 늘렸습니다.
그리고 하나의 서비스가 늘어나면 기존의 자리가 빠지므로 다른 서비스의 거리를 그리디로 조정했습니다.
2. 이렇게 하고, submit하면 96점 정도 나왔었고, 여기서 모든 이동 가능한 점으로 한번 움직여보면서 최종 점수가 높아지면 이동하도록 했습니다. 그리디 한건데 별로 효과가 없더군요. 거의 효과가 없었습니다 -_-;; 0.5점 미만? 보통 사람들이 MM은 많은 시간을 투자한다고 생각하지만, 사실은 코딩하기 전 처음에 어떻게 접근하느냐를 결정하는 것에서 끝나는 거 같습니다. 실제로 MM 시작하면 1등은 시작하고 얼마 안되서 바로 결정되고 나머지 사람들이 따라가는 형식으로 진행되더군요.
<아이디어>
1. 거리를 구하는 것은 DP로 구해놓으면 연산할 필요가 없고, 점수를 계산할 때 모든 칸보다는 10칸마다, 5칸마다 하는 식으로 계산할 수 있습니다.
2. 실제 코드에 적용하진 않았지만, budget이 남는 것을 감안해서 마지막 budget 1-2개를 빼고, 다른 것들로 대체해봐서 더 이익이면 그렇게 배치해도 이득이 있겠네요.
<후기>
처음의 전제조건: 1. 서비스 간에는 서로 상관없다 연산은 vector로 들어온 x,y로만 한다
아시다시피 2가지다 문제의 해석을 잘못한 것이었습니다.
그치만 다행히도 대세에 큰 상관이 없이(점수 계산 방법만 바꾸면 되는) 문제였고, 전 오히려 덕택에 스테이지 별로 나눠서 문제를 생각하게 되었습니다.
문제는 이런 상황에서 아무리 해도 87점대 이상은 안 올라갔습니다. (토요일)
일요일 내내 이런 저런 방법을 써서 결국은 "더 이상의 최적화는 (거의)없다" 하는 수준인데도 87점이었습니다.
이런 경우는 문제가 원하는 방향과 제가 원하는 방향이 맞지 않을 때 생기는 문제입니다.
!! 서비스 가능 지역으로부터 계산하는 게 아니라 모든 점에서 계산하는 거더군요.
그래서 점수 계산하는 함수를 좀 고치니까 바로 95점, 계산을 좀 손보니 바로 97점대가 됐습니다.
화요일: 50등대에서 서서히 밀리는데, 역시 이상한 일이 벌어집니다.
계산을 10칸 단위로 하지 않고 세세하게 5칸 단위, 2칸 단위로 하는데, 점수는 그대로거나 더 떨어집니다.
이런 경우도 제가 원하는 뱡항과 다르다는 것이죠. 그래서 문제 해설에 관해서 물어보기도 하고(대회 규정에도 문제 해석은 얘기할 수 있습니다)
포럼의 글을 읽어보기도 했습니다
!! 맙소사!! 최종점수에는 서비스 간에 영향이 있었습니다. 그렇다면 가급적 점이 서로 떨어져 있는 게 유리합니다.
왜냐면 (거리*중요도들의 합)^2 이기 때문에 하나가 너무 소외되면, 그지역의 값이 상승하게 됩니다.
또다른 징조는 이제 마지막으로 점의 근소한 차이를 수정하면 된다고 생각했고 실제로 제 계산에서는 이득이 있었습니다.
그런데, 오히려 점수가 대폭 떨어지더군요.
이제 총점을 구하는 함수를 만들고, 시간을 체크해서 20초에 다가가면 대충(?) 계산하고 남는 시간은 약간이라도 총점에 이득이 있으면 움직이도록 했습니다. 낮은 97점대가 되더군요 -_-
결과적으로는 처음에 잘못된 전제 조건 덕택에 나눠서 생각하게 되었고, 본의아니게 좋은 경험을 하게 되었습니다;;;;
다음에는 깨달음을 얻어 언젠가 MM 에디토리얼을 쓰는 날이 오길 기대해 봅니다 ㅋ
<궁금한 것>
1. 다른 분들은 어떤 기준으로 문제에 접근했었는지 궁금합니다.
2. 저 같은 경우는 쪽팔린 얘기지만, 뭔가를 찾을 일이 있으면 모든 점을 계산하는 방법을 썻습니다. 예를 들어 평면위에 2점의 최적 지점을 찾을 때도 계속 모든 점에 찍어보고 이득이 있으면 이동, 그리고 다시 돌리는 식으로 했습니다(그래서 시간이 모자;;;;)
근처에 있는 점만 조사하기도 했는데, 점수가 더 안 좋게 나와서 못 썻구요. 어떻게 해야 할지...
3. 저 같은 경우는 처음에 서비스간의 관계나 점수 계산법을 무시하고, 그냥 평균거리*서비스중요도 만 최소화 되도록 합니다. 그래서 그닥 근사하지 못합니다. (평균거리*서비스중요도값이 낮으면 물론 점수가 올라가겠지만 문제에서 나온 공식과도 틀리기 때문이죠) 제 방식으로는 시간 제한을 없애도 98.5점 정도가 한계라고 보입니다. 99.5 정도가 10등인데, 어떻게 생각해서 접근해야 할까요 ㅠ_ㅠ