djm03178   3달 전

문제의 시간 제한이 매우 애매한 곳에 걸려 있습니다. 요세푸스 시리즈를 봤을 때 이 문제는 O(nlogn)의 풀이를 요구하는 버전인 것으로 보이지만, 널리 알려진 것처럼 라이브러리 함수에 의존하는 O(n^2) 풀이가 여전히 700ms로 통과됩니다. 로직이 같아도 조금만 비효율적이거나, 언어에 따라서 불가능할 수도 있습니다.

n 제한을 변경할 수는 없으니, 시간 제한을 바꿔서 둘 중 하나를 택해야 할 것으로 보입니다. 제한을 0.3초 수준으로 줄여 이러한 풀이들이 모두 막히게 하거나 (하지만 이것은 O(n^2)이 통과된다는 소문을 듣고 온 수많은 사람들을 배신하게 됩니다), 10초 정도로 늘려 이 로직을 아무리 비효율적으로 짜더라도 통과될 수 있게 만들 수 있습니다.

또는 이 문제를 채점 준비중으로 만들어 봉인하고, 새로운 n 제한의 문제를 이 자리에 끼워넣는 것도 하나의 방법일 것 같습니다.

pichulia   3달 전

n이 10만인데 n^2이 통과된다는 소문을 듣고 온 사람들은 배신당해도 될듯 합니다.

재채점으로 혼내줄 가치가 있습니다.

jh05013   3달 전

0.3초로 줄인다면 추가 시간 제한 없음을 걸어 주세요.

startlink   24일 전

재채점했습니다.

jh05013   24일 전

"(추가 시간 없음)"이 걸려 있는데, 제 코드 중 0.5초를 초과한 것이 재채점을 통과했습니다.

djm03178   23일 전

추가 시간 없음에 부가적으로 일부 언어별 제한이 따로 걸려 있습니다.

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