rootsquare   4년 전

@skeep194

제 정답 코드 : https://www.acmicpc.net/source...

정상적인 방법으로 풀 수 없는 문제입니다. 배열의 무작위로 n/4 개의 원소에 특정한 수가 더해졌으나, 이 더해진 수에 규칙이 없으므로 사용자는 배열에서 특정 수가 더해진 칸과 그렇지 않은 칸을 "확실하게(정확도 100%)" 구별할 수 있는 방법이 없습니다.

제 코드의 경우 초반 몇 개의 항을 확인한 다음 이후 랜덤하게 정수를 뽑아서 답을 구하고 있는데, 이 방법이 틀릴 가능성이 있는데도(성공 확률이 99.99% 이상이긴 합니다.) 맞았습니다!! 를 받고 있습니다.

다른 정답 코드를 살펴보니까 그분들도 모두 무작위화/난수를 활용하여 문제를 푸셨습니다.

채점 환경이 적응적이지 않으므로, 현 상황에서 위와 같은 상황에 대해 반례 케이스를 만드는 것은 불가능할 것 같습니다.

혹시 이 문제에 대하여 난수 없이 정확도 100%를 보장할 수 있는 풀이가 존재하나요? 만일 존재한다면 이 문제를 "랜덤 방지", 아니라면 "번외" 처리해야 할 것 같습니다.

인터넷에도 이 문제의 공식 풀이가 보이지 않아서 질문 드립니다...

amel   4년 전

채점기가 "적응적"이지 않으므로, 우리의 입력에 알맞게 악랄하게 정답을 바꾸지 않습니다.

따라서 Randomization 을 적용할 수 있는 문제라고 판단되고, 아마 그게 정해일 겁니다.


실제로 랜덤 박는게 정해인 인터랙티브 문제가 종종 있습니다.

그냥 이런 것도 있네~ 하고 넘어가면 좋을 것 같습니다.

skeep194   4년 전

@rootsquare

제가 이 문제를 만들 당시 완성한 후 대회기간에 군대 훈련소에 있었어서 솔루션 관련 부분은 동아리 회장한테 맡겼었는데 어떻게 된지는 잘 모르겠네요.

윗 두분이 말하신것처럼 제 의도 또한 무작위화를 통한 99.9% 이상으로 수렴하는 정답이었고 다들 그렇게 풀어주셨습니다.

특정한 랜덤 시드를 저격하는 데이터를 넣을 수는 있지만 그렇게는 하지 않았고 만약 그렇다 하더라도 시드를 바꾸면 바로 풀린다는게 보장됩니다.

rootsquare   4년 전

자세한 설명에 모두들 감사드립니다. 한 번 연습해봐야 겠군요.

shiftpsh   4년 전

일반적으로 컴퓨터가 고장날 확률보다 낮은 확률로 틀리는 문제는 커뮤니티에서 decent 하게 보고 있는 것 같습니다.

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