오래된 문제 중에는 이런 식으로 테스트 케이스의 수 자체에 의미를 두지 않는 경우가 아주 많습니다. 테스트 케이스의 수 자체가 명시가 안 된 문제도 많고, 대개의 경우 이런 문제는 "출제자가 의도한 시간 복잡도면 통과 가능" 정도의 의미를 내포하고 있습니다. 또한 이런 경우 보통은 테스트 케이스의 수를 1로 가정해도 풀리는 정도로 데이터를 만들고는 합니다. 즉, 테스트 케이스의 수를 그저 단시간에 많은 케이스를 채점하기 위한 도구 정도로 사용한 것뿐입니다.
결코 좋은 문제 구성은 아니라고 생각하지만, 그렇다고 이미 그렇게 만들어진 수많은 문제들에 현대의 '엄격한' 기준을 적용해서 반드시 테스트 케이스의 수를 포함하여 주어진 제한을 빼곡하게 메울 수 있록 이리저리 바꾸는 것도 좋은 생각은 아닌 것 같습니다. 이런 문제들은 그냥 "출제자의 의도를 대충 짐작해서 풀어라"인 채로 놔두는 것이 문제의 보존 측면이나 비슷한 문제들에서의 혼란 등의 면에서 더 합리적이라고 생각합니다.

wapas 5년 전 2
문제 출처에 적힌 실제 대회 문제 의도는 삽입 정렬이지만, 여기서는 우선순위 큐 문제로 알려져 있습니다.
데이터 범위만 보아도 최악의 경우 T * M^2 = 약 10^11 이어서 많은 사람들이 우선순위 큐로 풀고 있는 것 같습니다.
그러나 실제 대회 데이터가 빈약하여 삽입 정렬 O(T * M^2) 풀이와 우선순위 큐 O(T * MlogM) 풀이 둘 다 풀리는 이상한 문제가 되었습니다.
-
삽입 정렬 풀이를 막으려면 아래 코드로 생성되는 데이터를 추가해주세요.
아래 코드는 100MB 크기의 입력 데이터 3개를 생성하는데,
대회 문제들 중에는 테스트 케이스에서 최악의 케이스를 꽉 채워넣는 것이 의도된 바가 아닌 경우가 많다는 게시글의 내용을 보았습니다.
(수의 범위가 -10000 ~ 10000 이어도 50MB 크기의 입력 데이터를 생성합니다)
따라서 입출력을 받는 과정에서만 시간을 많이 잡아 먹을 것으로 예상되는데, 이 데이터가 추가된다면 제한 시간 조정이 필요할 것 같습니다.
-
[1] 데이터와 데이터 범위를 수정하여 삽입 정렬이 정해인 문제로 변경할 것 인지
[2] 데이터를 추가하고 (필요하다면) 제한 시간을 늘려 우선 순위 큐가 정해인 문제로 유지할 것 인지
둘 중 하나의 조치가 필요해보입니다.