참고용으로 경로를 추가한 뒤 input1에 대한 Closed TSP 해를 구한 결과를 첨부합니다.
이상의 내용은 각 테스트 케이스에 대해 $\mathtt{ops} \leq 2 \cdot 10^7$ 을 만족하는 해를 구성하는 것은 현실적으로 어려우며, 실제로 불가능할 가능성이 높다는 추측을 담고 있습니다. 다만 Open TSP의 lower bound가 실제로 $2 \cdot 10^7$ 을 초과함을 확인한 것은 아니므로, 모든 테스트 케이스에 대해 $\mathtt{ops} \leq 2 \cdot 10^7$ 을 만족하는 해가 존재할 가능성을 완전히 배제할 수는 없습니다. 이 점 참고 바랍니다.

jinhan814 1년 전 15
해당 문제는 쿼리 순서를 적절히 조정하여 총 연산량($\mathtt{ops}$)을 줄이는 방식으로 채점이 진행되며, 10개의 tc에 대해 tc별로 다음과 같은 방식으로 점수가 부여됩니다.
$$\mathtt{score} = \min \left( 6, 6 \cdot \frac{2 \cdot 10^7}{\mathtt{ops}} \right)$$
현재 문제의 채점 기준은 각 tc 별 $\mathtt{score}$의 합이 $60$이어야 ac를 받도록 설정되어있기에 모든 tc에 대해 $\mathtt{score} = 6 \Leftrightarrow \mathtt{ops} \leq 2 \cdot 10^7$을 받는 풀이를 구성해야 합니다. 그러나 제공되는 채점용 입력 데이터(input0, input1)를 분석한 결과, $\mathtt{ops} \leq 2 \cdot 10^7$을 만족하는 쿼리 순서를 구성하는 것이 거의 불가능함을 확인했습니다. 구체적으로는 다음과 같은 사실을 확인했습니다.
본 문제는 $[1, 10^5] \times [1, 10^5]$ 범위의 $10^5$개의 정수 좌표 점의 Open L1 TSP(모든 점을 포함하는 path)를 구하는 문제입니다. 대부분의 TSP Solver는 Closed TSP(모든 점을 포함하는 cycle)를 구해주기에 우선 Closed TSP의 해를 확인했습니다.
Closed TSP와 Open TSP의 차이는 시작점과 끝점을 연결하는 간선의 유무이며, 문제 조건 상 간선의 가중치는 $199\,998$을 넘지 않기에 구한 하한에 $199\,998$를 빼면 Open TSP의 하한을 얻을 수 있습니다. 이는 input1 기준 $19\,924\,200$으로 매우 tight합니다. 또한 시작점과 끝점을 연결하는 간선을 삭제해 실제로 $199\,998$에 준하는 개선을 보이긴 어렵다고 생각됩니다. 이와 관련해, $(1, 1) \rightarrow (10^5, 1) \rightarrow (10^5, 10^5)$ 경로를 강제해 Closed TSP를 구한 뒤 해당 경로를 지워서 Open TSP를 구한 결과는 다음과 같습니다.
이는 단순히 가중치가 가장 큰 간선을 삭제하는 방법보다 $2\,000 \sim 4\,000$ 정도 개선된 값이지만, 마찬가지로 $2 \cdot 10^7$ 이하 해를 구하긴 어렵다고 생각합니다. input0, input1 뿐만 아니라 로컬에서 생성한 랜덤 데이터와 다른 테스트 데이터도 같은 경향을 보였습니다.
이러한 사실을 고려할 때, 본 문제는 만점을 의도한 문제라기보다는, 제한된 시간 내에 휴리스틱으로 가능한 한 많은 점수를 획득하도록 설계된 문제로 보입니다. 실제로 충분한 계산 시간을 확보하더라도 $60$점을 달성하는 것이 매우 어렵거나 불가능에 가깝고, $1$초 제한 내에서는 사실상 달성 불가능한 수준입니다.
이에 채점 기준을 누적 점수가 59점 이상이면 "맞았습니다"로 변경하는 걸 제안드립니다. 유사한 유형의 문제인 814 - 2, 814 - 3, 3-SAT 2 역시 이와 같은 채점 기준을 가지고 있으며, 해당 점수는 로컬에서 충분한 계산 시간을 이용하면 재현 가능하기 때문에 위와 같이 조건을 완화하면 충분히 챌린징하면서 현실적으로 해결할 수 있는 문제가 될 거라 생각합니다.