이 문제는 무작위화(randomized) 알고리즘을 의도하고 만들어진 문제입니다. 각 선물을 고를 확률을 어떻게 설정하느냐에 따라 서로 다른 비율이 나타나게 됩니다. 아무리 그렇다 하더라도 어느 정도의 확률로는 풀 수 있어야 하기 때문에 확률 계산을 엄밀히 해서 "정해는 근사적으로(독립 시행을 정규 분포로 근사하는 정도로) 테스트 케이스 하나에 대해 99.9% 이상의 확률로 정답을 받을 수 있다"는 것을 증명하고 출제했습니다. 이 증명이 틀렸습니다. 이 확률(competitive ratio)의 평균 계산은 제대로 했으나 표준편차의 계산이 완전히 틀려, 실제로는 95% 정도로만 정답을 받을 수 있는 테스트 케이스가 있음에도 불구하고 이 테스트 케이스에 대해 99.9% 이상의 확률로 정답을 받을 수 있다고 잘못 계산해 조건 p = 50을 잡았습니다.
대회가 시작하기 전도 아니고 (따라서 제한을 바꿀 수 없으며) 데이터 개수의 지수승에 비례하게, 즉 매우 높은 확률로 풀이를 틀리게 할 수 있습니다. 또한 정해가 틀린 상황에서 데이터 추가를 막는 것도 의미가 없습니다. 따라서 이 문제를 채점 준비중으로 바꾸기로 결정했습니다.
이 문제는 제2회 키파컵 D번 문제였습니다. 제 닉네임을 건 대회에 정해가 틀린 문제를 당당하게 출제한 것에 큰 부끄러움을 느끼고 있습니다. 크리스마스를 전후하여 상품 공지를 하겠지만, 이 문제의 특별상을 대신해서, 제2회 키파컵에서 이 문제에 제출하신 분(18명) 전부에게 작은 선물을 드릴 예정입니다. 이런 문제가 포함된 셋을 풀어 주시고 이 문제에 제출해 주셔서 감사합니다. 데이터를 만들어서 제가 틀린 것을 직접 증명해 주신 ho94949님께도 감사드립니다.
kipa00 6년 전 19
안녕하세요, 출제자입니다.
먼저 죄송하다는 말씀을 드립니다.
이 문제는 무작위화(randomized) 알고리즘을 의도하고 만들어진 문제입니다. 각 선물을 고를 확률을 어떻게 설정하느냐에 따라 서로 다른 비율이 나타나게 됩니다. 아무리 그렇다 하더라도 어느 정도의 확률로는 풀 수 있어야 하기 때문에 확률 계산을 엄밀히 해서 "정해는 근사적으로(독립 시행을 정규 분포로 근사하는 정도로) 테스트 케이스 하나에 대해 99.9% 이상의 확률로 정답을 받을 수 있다"는 것을 증명하고 출제했습니다. 이 증명이 틀렸습니다. 이 확률(competitive ratio)의 평균 계산은 제대로 했으나 표준편차의 계산이 완전히 틀려, 실제로는 95% 정도로만 정답을 받을 수 있는 테스트 케이스가 있음에도 불구하고 이 테스트 케이스에 대해 99.9% 이상의 확률로 정답을 받을 수 있다고 잘못 계산해 조건 p = 50을 잡았습니다.
대회가 시작하기 전도 아니고 (따라서 제한을 바꿀 수 없으며) 데이터 개수의 지수승에 비례하게, 즉 매우 높은 확률로 풀이를 틀리게 할 수 있습니다. 또한 정해가 틀린 상황에서 데이터 추가를 막는 것도 의미가 없습니다. 따라서 이 문제를 채점 준비중으로 바꾸기로 결정했습니다.
이 문제는 제2회 키파컵 D번 문제였습니다. 제 닉네임을 건 대회에 정해가 틀린 문제를 당당하게 출제한 것에 큰 부끄러움을 느끼고 있습니다. 크리스마스를 전후하여 상품 공지를 하겠지만, 이 문제의 특별상을 대신해서, 제2회 키파컵에서 이 문제에 제출하신 분(18명) 전부에게 작은 선물을 드릴 예정입니다. 이런 문제가 포함된 셋을 풀어 주시고 이 문제에 제출해 주셔서 감사합니다. 데이터를 만들어서 제가 틀린 것을 직접 증명해 주신 ho94949님께도 감사드립니다.
다시 한 번 대회 문제를 꼼꼼이 확인하지 않고 출제한 점 사과드립니다.
감사합니다. kipa00 드림.