언급하신 범위가 대회에서 사용된 테스트케이스를 바탕으로 설정하신 건가요? 사용된 테스트셋이 작다고 케이스를 추가하는 게 아니라 범위를 줄이는 것은 문제 의도에 맞지 않다고 생각합니다.

또한 O(M^2) 보다 효율적으로 푸는 풀이가 없다고 하셨는데, 저를 포함해 푸신 분들의 코드를 본 결과 더 효율적인 풀이가 있다고 생각합니다.

출제자가 아무런 생각 없이 늘려 놓은 제한은 잘못된 제한이며, 수정되어야 마땅하다고 생각합니다. 출제자가 실제로 저런 범위에서 문제를 푸는 것을 의도했다면 대회에서도 그에 걸맞는 데이터가 사용되었어야 합니다. 심지어 대회에서 제공한 공식 풀이 역시 O(M^2) 커팅입니다.

더 효율적인 풀이가 있다고 하셨는데 시간복잡도상으로 O(M^2)보다 나은 풀이, 즉 O(M) 또는 O(M log M) 등의 시간복잡도가 보장되는 풀이가 있다면 설명해 주시면 감사하겠습니다.

각 구간의 합이 k라고 가정했을 때, 이를 확인하는 방법은 O(M)으로 쉽게 구현할 수 있습니다.

그렇다면 k를 고르는게 중요하며 k를 고르는 과정은 다음과 같습니다.

첫번째 원소를 포함하는 구간이 반드시 존재하므로 k의 선택지를 1~i 합으로 줄일 수 있습니다.

그러나 그렇게 줄인 선택지 중에서도 모든 구간에서 합이 k로 동일하므로 k는 모든 원소의 합을 S라 하였을 때, S의 약수이어야 함을 알 수 있습니다.

이는 1~i까지 합을 구해 k를 선택하더라도 k가 S의 약수가 아니면 확인할 필요가 없다는 것을 의미하며 따라서 최대 "S의 약수 개수" 만큼에 대해서만 탐색이 이루어지게 됩니다.

결국 O(M(S의 약수 개수)) 로 풀이가 가능합니다.

이 세트(greater new york regional contest)가 그냥 이전부터 잘못된 제한 조건/틀린 조건/틀린 지문 등으로 말이 많은 세트입니다.. ㅠㅠ

공식 솔루션 코드가 M^2이고, 데이터도 이러한 시간복잡도 내에 들어가는 데이터만 있는 것으로 보아 뉴욕 리저널이 또 뉴욕 리저널 했다고 보는 게 맞을 것 같아요.

보통은 지문에 맞춰 데이터를 추가하는 것이 옳으나, 이 문제의 경우엔 데이터에 맞춰 지문을 수정하는 것이 나아 보입니다.

그 풀이를 포함해서 O(M^2) 커팅으로 표현했습니다. 1억 이하에서 가장 약수가 많은 수(73513440)는 768개의 약수를 갖고 있고, O(768M)은 여전히 1초에 1000개의 테스트 케이스를 처리하기에 충분하지 않습니다.

간단한 데이터를 하나 만들어 봤습니다. 이 데이터의 각 테스트 케이스는 대부분 10000으로 이루어져 있고 총합은 75600000이며, 데이터의 크기는 약 50MB입니다. 7560의 약수의 개수는 64개이므로 제시하신 풀이는 약 O(64M)이 되는데, 제가 로컬 환경에서 해당 풀이를 작성하고 실행했을 때 1.5초 정도가 걸립니다. 이런 데이터가 추가되기를 원하시는 건가요?

아 저도 그부분을 방금 확인했습니다. doju님 말씀대로 1억 이하의 수 중 약수의 개수가 최대 768임을 감안해 범위를 줄이는게 옳다고 생각합니다.

그러나 개인적인 생각으로 O(768TM) 풀이가 존재하는 것이며 때문에 O(TM^2) 으로 통과되지 않는 선에서 범위를 줄이는 것은 어떨까라는 생각이 듭니다.

약수 커팅이 강력한 아이디어라는 점에는 동의하며, 약수 커팅을 하지 않은 풀이를 막는 것이 의도라면 아래 데이터(P = 50) 정도면 충분해 보입니다.