3개의 댓글이 있습니다.
-
-
세훈 -
정말 깔끔한 풀이네요
저는 올해 대회에 참가하지는 않았지만 이 문제에 관심이 생겨서 오늘 좀 생각을 해봤는데요,
풀이가 이런 식으로 될 줄은 상상도 못했습니다 :)
다만 저는 기하가 아닌 다른 관점에서 풀었는데요, 생각해보면 위의 해답과 동치인 듯 하네요
아마도 고등학교 팀이 이렇게 풀지 않았을 까...하는 관점에서 올려봅니다.
(Ai, Bi는 i번째 게임에 대한 두 사람 A, B에 대한 만족도를 의미합니다.)
먼저 제 솔루션에 대해 간략히 소개하면 이렇습니다.
Ai >Bi인 모든 점 들 중 Bi가 Maximum인 점 Pi를 찾고,
Aj < Bj인 모든 점 들 중 Aj가 Maximum인 점 Pj를 찾아 두 게임만 고려한 해를 찾는다. (간단한 방정식으로)
Pi나 Pj 중 하나가 존재하지 않는다면, 그 게임만 선택한다
저는 이 해가 위의 해와 동치라고 생각하는데요, 아래에 나름 그 이유를 작성해 보겠습니다.
1. Convex hull
--> Ai > Aj, Bi > Bj이면 게임 j는 무시된다.
실제로 이 문제에서 컨벡스헐의 하반신은 솔루션이 될 수 없기 때문에 대수적으로 보면 저런 식과 Convex hull이
동치이지 않나 싶습니다.
2. 해는 경계선 위에 존재한다.
--> 저는 이걸 솔루션은 최대 2개의 게임을 포함한다..라고 해석해보았습니다.
제 솔루션 중 중요한 부분은
Ai > Bi, Aj > Bj 일 때 Ai > Aj and Bi > Bj일 때만 게임 j가 무시되는 것이 아니라
Ai < Aj and Bi > Bj이여도 게임 j가 무시된다고 생각을 한 것인데요,
이건 x *Ai + y * Aj > x * Bi + y * Bj 이기 때문에
한정된 x + y에서 x * Bi + y * Bj를 Maxmize하기 위해서는 x에 몰아주는것이 유리하기 때문이라고 생각했습니다.
새로운 조건이 추가되면 사용가능한 게임이 딱 2개 아니면 1개로 줄게 됩니다.
이건 결과적으로 해가 경계선 아니면 꼭지점에 있음을 암시하게 되지요.
3. y=x와 교차점을 찾는다.
--> 이건 뭐.. 어떻게 보면 당연한 거구요. 대수적으로도 비슷한 의미가 있죠 ^^;
조금 더 설명을 하자면 y=x와 교차하는 선분은
Ai>Bi인 점 중 Bi가 최대인 점 Pi와 Aj예를 들어 Ai 항상 Ai>Bi인 점들 중 하나를 선택한다고 보면 Bi가 클수록 해가 증가하는 것을 확인 할 수 있습니다.
그 반대도 마찬가지구요.
4. 만약 교차하지 않는 다면, 해는 하나의 점이다.
위에서는 터너리 서치가 나왔는데요... 아마도 제 생각엔 이런 경우 해는 하나의 점이 아닐까 싶습니다.
왜냐면 교차하지 않는단 얘기는 y=x인 직선 위에 모든 점이 존재하거나 아래에 모든 점이 존재하는 경우인데요,
만약 위에 모든 점이 존재한다면
모든 점에 대해 Ai < Bi란 얘기고 이 경우 Ai가 max인 점을 선택하는 것이 Bi와 상관없이 유리하기 때문이지요.
... 비슷한가요?
사무실에서 몰래 쓰다 보니 머리속이 정리가 잘 안되네요.
게다가 금요일 저녁이라 ^^;;
모두들 열공하시고 원하시는 성적 모두 내세요~
16년 전 link
-
-
-
kcm1700 -
음.. 제가 알기로는 고교 팀도 기하로 변형해서 풀었습니다.
고교팀이 한 방식은 convex hull을 직접 구하지 않고 코딩을 더 간결하게 하기 위하여 약간의 테크닉을 사용했습니다.
고교팀의 방식을 정확히 적어보면
먼저 k에 대해 바이너리 서치를 돌려줍니다.
그 다음에 주어진 값들을 2차원 벡터로 표시하고
거기서 거기에서 (k,k) 벡터를 뺍니다. 그런 후에 1사분면에 점이 있으면 무조건 가능하다고 하였고
없다면 2사분면과 4사분면에 있는 벡터들을 하나씩 골랐을 때 사이각이 π이하가 되는 것이 있는지를 통해
실제적으로 k에 대해 가능한지 불가능한지를 체크해보았습니다. 사이각이 파이 이하가 되면 가능한 것은
생각해볼 수 있구요,
음... 그리고 이 알고리즘을 생각해내기 전에
Sum(A_i P_i) >= k
Sum(B_i P_i) >= k
라는 식을 세우고
Sum(A_i P_i) >= k Sum (P_i)
Sum(B_i P_i) >= k Sum (P_i)
라고 한 뒤
Sum( (A_i - K) P_i ) >= 0
Sum( (B_i - K) P_i ) >= 0
을 통해 벡터로 표현할 생각을 하였다고 하네요
16년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
JongMan
[문제 보러 가기]
"풀지 말라고 냈는데 두팀이나 풀었다" 라는 주최측의 커멘트에서도 알 수 있듯이 이 문제는 가장 풀기 어려웠던 문제 중
하나입니다. 문제를 적절히 수학적으로 변환하고, 이 문제를 계산기하(computational geometry) 를 이용해 푸는
풍부한 센스가 있어야 하는 문제죠.
각 게임에 대한 사람별 만족도를 각각 벡터로
나타냅시다. Si 는 i번째 게임에 대한 두 사람의 만족도를 포함하는 2차원 벡터라고 합시다. Ai 가 i번째 게임을 할
확률이라고 하면, sum(i = 1 to n) Ai * Si 벡터는 각 사람이 마지막으로 느낄 총 만족도를 담는 벡터가 되겠지요.
그러면, 이 문제는 계수(coefficient) 들의 합이 1인 Si 의 선형 결합(linear combination) 중, 최소 component 를 최대화하는 문제로 바뀝니다. 그런데 이 때 계수의 합이 1인 Si 의 선형 결합의 개수는 무한합니다. 따라서 각각을 하나씩 시도해볼 수는 없죠. 좀더 다른 식견, insight가 필요합니다.
입
력 벡터들이 2차원이라는 점을 이용해서 이 벡터들을 시각화해 봅시다. 각 벡터들의 끝점을 2차원 평면 위에 찍어 보는 거죠. 이
때, 우리가 구하는 선형 결합 결과 벡터의 끝 점들이 있을 수 있는 위치를 다 찍어 봅시다. 그러면, 실제로 이 점들은 입력
벡터의 끝점들을 모두 포함하는 볼록 껍질(Convex hull) 안의 모든 점들이 된다는 것을 알 수 있어요. (사실 이와 같이, 계수들의 합이 1이 되는 선형 결합들을 특별히 볼록 결합Convex combination 이라고 부르기도 합니다)
따라서, 입력 벡터에 주어진 점들을 모두 포함하는 볼록 껍질을 우선 계산한 뒤, 이 영역 안에 있는 점들 중 min(x, y) 를 최대화하는 점을 찾으면 이 문제를 풀 수 있습니다. 이를 풀기 위해 두 가지 방법이 있습니다:
중 최소값을 최대화하는 문제라면, 우리가 찾는 점은 y = x 위에 있겠지요. y = x 직선을 그은 뒤 볼록 껍질이 이 직선과
교차하는 점들 중에 답이 있을 것입니다. (단, 이 경우 볼록 껍질이 y = x 와 교차하지 않는다면 다른 답을 찾아야
합니다.. 어떻게일까요? ^^)
않다면, y 나 x 중 하나나 둘 다를 증가시키는 방향으로 그 점을 밀어갈 수 있기 때문입니다) 따라서, 볼록 껍질을 이루는 각
선분 위에 있는 점들 중에서 우리가 원하는 점을 찾으면 됩니다. 선형계획법(Linear programming) 문제를 해결하기 위한 심플렉스법(Simplex algorithm) 과 비슷하게 해결하셔도 되고, 각 선분 위에서 터너리 서치를 해도 되겠지요. 여기까지 오셨다면 이 문제가 어렵진 않으실 테니 이만.. :)
실로 풀지 말라고 냈다는 말이 이해가 될 정도로 어려운 문제로군요. :) 푼 두 팀, 대단합니다!
덧) 들리는 바로는 이 문제를 푼 두 팀 중 하나는 고등학교 팀이던 도전대학교(...) 팀이라는군요. 정말 대단하네요. 한국 CS 의 미래가 밝습니다~ :)
16년 전