DEATH 문제가 잘못된 것 같아요. 투명드래곤 어떤 사람이 지목한 사람은 딱 한명인데, 일반적으로 구현하는 방법대로라면 매 iteration 마다 1/(2T+1)씩의 확률을 다시 계산해서 사람이 바뀔 수도 있는것과 마찬가지잖아요. 예를 들어서 사람 수 N=10, 오차 T=1, 숫자 X=3이고 1->2, 2->3, 3->8, 4->7, ... 이라고 할 때 2가 걸릴 확률을 구하면 실제 확률은 2->2의 확률인 1/3이지만 정답은 1/9가 되는데요, 음... 제가 써놓고도 무슨 말인지...;;; 아무튼 알아보셨으리라 믿고.. 이 문제의 진짜 정답을 구하려면 어떻게 해야 할까요? 13년 전
4개의 댓글이 있습니다. Being 그러니까.. 어떤 사람 p가 가리키고 있는 사람은 유일하게 결정되어 있는데 X가 충분히 클 때 그 사람 p를 여러 번 거치게 되는 경우 그 사람의 선택이 매번 다르게 결정된다 이런 말씀이신가요? ㅎㅎ 13년 전 link Being 예를 들어 이런 경우겠네요. 5명의 사람이 앉아 있고 오차 범위 T = 1입니다. 모든 사람이 자기 자신을 가리키고 있고 X = 4라 합시다. 이러면.. 1->2->1의 시나리오가 일어날 확률은 1/3*1/3 = 1/9입니다. 그런데, 1->2->1->2->3의 시나리오가 일어날 확률은 0이어야 합니다. 이 부분이 잘못되었다는 말씀..맞나요 :) 13년 전 link Being 약간 정정하자면 1은 항상 자신의 선택을 정확하게 아는군요. 여튼간에 2의 선택이 1이었다가 3이었다가 할 수는 없다는 이야기입니다 ㅎㅎ 13년 전 link 투명드래곤 네 ㅎㅎ 제가 하고싶었던 말이 저건데.. 정리 감사합니다 :) 13년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
투명드래곤
어떤 사람이 지목한 사람은 딱 한명인데, 일반적으로 구현하는 방법대로라면 매 iteration 마다 1/(2T+1)씩의 확률을 다시 계산해서 사람이 바뀔 수도 있는것과 마찬가지잖아요.
예를 들어서 사람 수 N=10, 오차 T=1, 숫자 X=3이고 1->2, 2->3, 3->8, 4->7, ... 이라고 할 때 2가 걸릴 확률을 구하면
실제 확률은 2->2의 확률인 1/3이지만 정답은 1/9가 되는데요,
음... 제가 써놓고도 무슨 말인지...;;;
아무튼 알아보셨으리라 믿고.. 이 문제의 진짜 정답을 구하려면 어떻게 해야 할까요?
13년 전