5개의 댓글이 있습니다.
-
-
Dynamical -
예를 들어서, X를 1번째, 2번째 tree 사이의 높이차(에 해당하는 확률변수), Y를 2번째, 3번째 tree의 높이차(에 해당하는 확률변수)라 한다면 E[X+Y] = E[X] + E[Y]를 만족하는 것이죠. 실제로 두 개의 사건이 결코 독립적이지 않지만 (예를 들어서, 2번째 트리가 무엇이냐에 따라서 1-2 사이의 cost와 2-3 사이의 cost에 영향을 주겠죠) Expectation을 계산하는 데 있어서 사건간 연관성은 관련이 없습니다.
E[X + Y] = ∑∑(X(i) + Y(j))P(X(i)∩Y(j)) = ∑X(i)∑P(X(i)∩Y(j)) + ∑Y(j)∑P(X(i)∩Y(j)) = ∑X(i)P(X(i)) + ∑Y(j)P(Y(j)) = E[X] + E[Y]
12년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
ibroker
근데 이건 왜 editorial이 없죠? ㅎㅎ
member붙는 건 editorial 작성을 안하나요.. ㅜ
100번 질문 있는데요.
간단하게 문제 설명하자면,
N개의 tree가 있는데, i'th tree의 높이는 low[i]~high[i]에서 uniform하게 distribute됩니다.
random하게 tree의 높이를 배정하다보면 1번째 트리부터 N번째 트리까지 높이가 지그재그가 되는 때가 있겠죠.
이런 나열이 만들어졌을 때, 이 나열의 cost는 | height[i]-height[i+1] | 1<=i<N 이 됩니다.
즉, tree높이가 1 3 2 로 만들어 졌다면, 이것의 cost는 |1-3| + |3-2| = 3이 되겠죠.
근데 만약 트리의 높이가 지그재그가 되지 않는 경우에는 몇 개의 tree를 제거할 수 있는데, 이 때 나오는 결과의 cost는 만들 수 있는 것 중 최대가 되야 합니다.
1 3 4 2 와 같은 경우에는 3을 제거하거나 4를 제거할 수가 있는데, 3을 제거하는게 더 cost가 크므로 3을 제거한 1 4 2 나열로 만듭니다.
이렇다고 했을 때, expected cost를 구하는 것이 문제입니다.
높이는 최대 10000이 될 수 있고, tree의 개수는 50개 입니다.
제가 생각한 방법은... tree를 제거하는 부분은, 사실 cost가 높이의 차이를 이용해서 구하기 때문에 제거하지 않아도 무방하다고 보여져서, 그냥 모든 경우의 expected cost를 구하면 된다고 생각을 했습니다.
(1 3 4 2에서 |1-3| + |3-4| = |1-4| 가 되니깐요.)
D[i, j] = 1~i'th의 tree에서 마지막 tree의 높이가 j일 때의 expected cost를 저장하면 되지 않을까하고 문제에 접근해 봤는데요.
1~i'th tree의 기대값은 all of sum_1_to_i / (pr_1 * pr_2 * ... * pr_i) 과 같은 식으로 만들어지고, i+1번째 tree의 기대값은
( all of sum_1_to_i + | (i+1)'th height - i'th height | ) / (pr_1 * pr_2 * ... * pr_i+1)
이렇게 나오더라고요.
그러면 분모랑 분자의 값을 따로 저장한 후에 마지막에 둘을 나눠줘야 하는데, 범위를 당연히 넘어가 버리게 되므로 문제가 발생하네요..
제 접근 방법이 아예 잘못됐는지, 아니면 개선의 여지가 있는지 궁금합니다.
힌트 조금만.. ^^;;
12년 전