4149번 - 큰 수 소인수분해
https://www.acmicpc.net/board/...
이전 게시글에도 언급된 적 있듯, Pollard-Rho 알고리즘은 무작위화 요소가 있으나 제대로 구현하면 충분히 정확도 99.99% 이상을 얻을 수 있습니다.
https://solved.ac/guideline
solved.ac 의 가이드라인에도 "해결 가능성"에 대하여 "첫 제출의 오답률을 0.01% 미만으로 낮출 수 있는가"를 명시하고 있습니다.
(0.01% == 0.0001)
그러나 현재의 데이터 수(161)는 위 두 조건을 만족시키기에 너무 적습니다. 채점 데이터 개수를 약 10000개 정도로 늘리는 것을 건의합니다.
채점 데이터가 10000개가 넘으면 서버가 감당이 안 됩니다. 그거랑 별개로 글이 잘 이해가 안 가는데요. 채점 데이터가 10000개 정도가 아니면 무슨 문제가 생기나요?
99.99% 확률로 맞는 풀이가 있느냐가 중요한거지, 99.99% 미만의 확률로 맞는 코드를 반드시 틀리게 만드는 것이 중요한 것 같지는 않습니다. 본문에서 언급하신 soved.ac의 가이드라인도 전자를 말하는 것이지 후자와는 관계가 없습니다. 애초에 언급하신 "너무 적은 데이터 때문에 정답 확률이 99.99% 미만인 코드가 맞는" 것은 이 문제 뿐만 아니라 모든 랜덤 문제에 해당됩니다.
이해했습니다. 상세한 설명에 감사드립니다.
댓글을 작성하려면 로그인해야 합니다.
rootsquare 4년 전
https://www.acmicpc.net/board/...
이전 게시글에도 언급된 적 있듯, Pollard-Rho 알고리즘은 무작위화 요소가 있으나 제대로 구현하면 충분히 정확도 99.99% 이상을 얻을 수 있습니다.
https://solved.ac/guideline
solved.ac 의 가이드라인에도 "해결 가능성"에 대하여 "첫 제출의 오답률을 0.01% 미만으로 낮출 수 있는가"를 명시하고 있습니다.
(0.01% == 0.0001)
그러나 현재의 데이터 수(161)는 위 두 조건을 만족시키기에 너무 적습니다. 채점 데이터 개수를 약 10000개 정도로 늘리는 것을 건의합니다.