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개 정도로 늘리는 것을 건의합니다.

koosaga   4년 전

채점 데이터가 10000개가 넘으면 서버가 감당이 안 됩니다. 그거랑 별개로 글이 잘 이해가 안 가는데요. 채점 데이터가 10000개 정도가 아니면 무슨 문제가 생기나요?

Green55   4년 전

99.99% 확률로 맞는 풀이가 있느냐가 중요한거지, 99.99% 미만의 확률로 맞는 코드를 반드시 틀리게 만드는 것이 중요한 것 같지는 않습니다. 본문에서 언급하신 soved.ac의 가이드라인도 전자를 말하는 것이지 후자와는 관계가 없습니다. 애초에 언급하신 "너무 적은 데이터 때문에 정답 확률이 99.99% 미만인 코드가 맞는" 것은 이 문제 뿐만 아니라 모든 랜덤 문제에 해당됩니다.

rootsquare   4년 전

이해했습니다. 상세한 설명에 감사드립니다.

댓글을 작성하려면 로그인해야 합니다.