9개의 댓글이 있습니다.
-
-
일루 -
아마 맞을 겁니다. 좀 더 포멀하게 써보면...
엣지 가중치는 기준점 k에 대한 연속함수입니다. 따라서 두 엣지 가중치의 순서가 달라지려면 함수의 연속성 때문에 필연적으로 두 엣지 가중치가 같아지는 지점을 통과하게 됩니다.
이 지점들은 엣지 a-b와 c-d에 대해 (dist(a-b)-k)^2 = (dist(c-d)-k)^2 인 지점들이므로,
dist(a-b) = dist(c-d) 이거나
dist(a-b)+dist(c-d) = 2k 인 두 가지 경우가 있습니다.첫번째 경우는 k에 대해 독립적이니 따로 생각할 필요가 없고
두번째 경우가 두 엣지 길이의 평균이 되는 것입니다.이제 이 '두 엣지 길이의 평균' 들을 정렬하고, 어떤 인접한 두 점을 생각하면, 두 점 사이에서는 가중치의 순서가 변하지 않게 됩니다. 따라서 그 아무 점인 평균점을 잡아서 크루스칼을 돌릴 수 있게 되는 것입니다.
사실 첫 점 이전과 마지막 점 이후에 정답이 있는 경우도 처리해야 하는데, 표준편차 정의하기 귀찮았는지 n>=3으로 조건을 준 덕분에 처리하지 않아도 되었습니다.
10년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
일루
안녕하세요, 요즘 레이팅이 망해가는 나나입니다.
간단하게 srm611 하면서 받은 느낌을 써봅니다. 스포일러 있으므로 문제 안 풀어보신 분들은 back 버튼을...
https://www.otinn.com/topcoder/al/summary.php?rid=15844&gid=2900
250 - 보는데 전혀 easy하지 않습니다. '제일 작은게 다르면 Not equal이군!' 에서 생각이 멈춰 한참 고민했고, '아 다른것중 제일 작은건 그 전걸로 만들어지기만 하면 되겠구나' 라는 생각이 드는데 시간이 꽤 걸렸습니다. 그나마 생각난게 다행. 입력에 1이 있는 경우 특별 처리 했었는데 입력이 2부터더군요 ㅠㅠ 슬프다....
550 - 550 빨리 풀고 1000 가야지 라고 생각하고 호기롭게 열었는데 헉 minimize(stdev)... 헉.. 헉헉.. 그나마 n<=20 을 보고 약간 체력을 회복하는 듯 했으나 각종 dp 아이디어들이 잘 되지 않는 것 같아서 한참 고민하고 있더랬습니다.
이러다가 '최소 최대치 차이를 최소화하는 문제였다면 가능하지 않을까?' 라는 뻘생각을 하고 있다가 이 생각이 '그렇다면 ave=k 로 고정하면 weight가 고정되니 이렇게 랜덤하게 시간 될때까지 해볼까?' 로 바뀌었고 다시 '시도해봐야 하는 경우의 수가 몇 개지?' 라고 생각이 되었는데 여기서도 한참 헤매다가 결국 정해를 찾을 수 있었습니다.
실행시간 줄이려고 (sum)^2-sum(^2) 을 그냥 수식으로 쓰려고 노력하다가 50점은 까먹은 것 같습니다. 그냥 계산해도 안느린데...
1000 - 보자마자 다이아몬드 dp 느낌이 나서 그림을 좀 그려보다가 위 아래 다이아몬드 절반 구했다고 가정하고 합친 부분부터 짰습니다. 이제 각 다이아몬드에 대해 3차원 dp를 O(n^4) 이내로 구현해야 하는데 결국 효율적 연산을 해야 O(n^5)를 면할 수 있거든요. 이 부분을 한참 생각하다가 수식이 잘 안나와서 대회 종료. 550을 5분정도 빨리 풀었다면 테스트는 해볼 수 있었을텐데 아쉽다는 생각.. 을 또 5분정도 했습니다 ㅠㅠ
Challenge - 아주 수상한 코드를 하나 잡아서 한참 생각 후 챌린지를 했는데 실패! 이유를 보니 한 군데 버그를 다른 데서 카운터를 칩니다.. 물론 서로 독립적인 버그였기 때문에 바로 다음에 챌린지 성공. +25.
결과적으로 11등이긴 했는데 더 잘 할 수 있었어서 아쉽다는 생각이 강합니다. 볼라 안떨어트리고 레이팅 올려서 나름 만족이었습니다.
10년 전