이 글은 정해를 설명하는 글이라기보다는, 현재 BOJ 데이터가 어떤 성격인 것 같은지에 대한 추측입니다. 숨은 데이터를 직접 본 것은 아니므로 틀릴 수 있습니다.

처음에는 UCPC 공식 해설 방식으로 풀었습니다. 보물 가치를 정렬하고, 최종 승리 팀을 기준으로 팀을 번갈아 배정한 뒤, 시간을 거꾸로 보면서 리더가 바뀐 순간에는 큰 값을, 리더가 유지되는 순간에는 작은 값을 배치하는 방식입니다.

그런데 이 방식은 25퍼센트 근처에서 오답이 났습니다.

제가 보기에는 원인이 Ti 중복입니다.

현재 BOJ 조건에는 Ti가 서로 다르다는 말이 없습니다. 오히려 N은 10000까지 가능하고 Ti는 1000까지라서, 명세 그대로라면 중복이 자연스럽게 발생합니다. 문제에는 “시작 시점을 제외했을 때 두 팀의 보물 가치 총합이 같은 경우는 없고, 항상 정답이 존재한다”고 되어 있습니다.

문제는 공식 해설식 구성은 중복값이 있을 때 누적합 0을 만들 수 있다는 점입니다.

예를 들어 다음 입력을 생각할 수 있습니다.

1

2

1 1

1 1

공식식으로 두 1을 서로 다른 팀에 주면 두 번째 순간에 1 대 1 동점이 됩니다. 문제 조건상 이 출력은 틀립니다.

하지만 정답은 존재합니다.

1 1

1 1

즉, “정답이 존재한다”와 “공식 해설식 구성이 항상 통한다”는 같은 말이 아닙니다.

제가 통과한 코드는 공식 풀이만 사용하지 않았습니다. 먼저 공식 후보를 만들고, 직접 검증해서 통과하면 출력했습니다. 검증은 사용한 보물 멀티셋이 입력과 같은지, 매 순간 리더가 맞는지, 누적합이 0이 되는 순간이 없는지를 모두 확인했습니다.

공식 후보가 실패하면 중복값을 따로 처리했습니다. 핵심 아이디어는 같은 값 두 개를 같은 리더 구간 안에서 중립쌍처럼 쓰는 것입니다.

예를 들어 현재 1팀이 앞서고 있는 구간에서 값 v 두 개를

v 1

v 2

순서로 넣으면 첫 번째 순간에는 1팀의 리드가 커지고, 두 번째 순간에는 점수 차이가 원래대로 돌아옵니다. 중간에도 동점이 되지 않는다면 이 두 보물은 리더 기록을 바꾸지 않는 filler처럼 사용할 수 있습니다.

그래서 제 코드는 값 개수 중 짝수로 남는 부분을 이런 중립쌍으로 묶고, 각 리더 연속 구간에는 실제로 리더 변화를 만드는 데 필요한 최소한의 핵심 보물만 남기는 방식으로 문제를 압축했습니다. 압축된 작은 문제는 공식 방식이나 그리디로 풀고, 이후 중립쌍을 다시 끼워 넣었습니다.

이 방식이 정해라는 뜻은 아닙니다. 제 코드는 여러 후보를 만드는 휴리스틱이고, 후보가 실제 조건을 만족하는지 검증한 뒤 출력하는 구조입니다. 모든 가능한 입력에 대해 반드시 답을 찾는다는 증명은 없습니다.

다만 이 코드가 통과했다는 점으로 미루어 보면, 현재 BOJ 데이터에는 다음과 같은 성격이 있는 것 같습니다.

Ti 중복이 실제로 들어 있는 것으로 보입니다. 공식 해설 방식만으로는 중복 때문에 동점이 생겨 실패할 수 있습니다.

스페셜 저지 자체가 특정 출력만 받는 것은 아닌 듯합니다. 제가 출력한 답은 공식 출력이 아니라 직접 구성한 다른 가능한 답이었고, 조건을 만족하면 통과했습니다.

데이터가 아주 강한 일반 중복 케이스까지 모두 요구하는 것 같지는 않습니다. 같은 값 두 개를 중립쌍으로 처리하고, 남은 핵심 문제를 푸는 정도로 통과되었습니다.

따라서 현재 문제 상태는 “스페셜 저지가 틀렸다”라기보다는 “공식 해설이 전제한 구성과 BOJ 명세가 허용하는 입력 범위가 어긋나 있다”에 가까운 것 같습니다.

만약 출제 의도가 공식 해설 방식이라면 Ti 중복에 대한 추가 조건이 필요해 보입니다. 다만 N이 10000이고 Ti가 1000 이하라서 “모든 Ti가 서로 다르다”는 조건은 그대로 붙일 수 없습니다. 반대로 중복을 허용하는 문제라면, 공식 해설의 구성은 중복값에서 불완전하다고 보는 게 맞을 것 같습니다.

정리하면, 제 추측은 이렇습니다.

현재 BOJ 데이터에는 공식 풀이를 깨는 중복값 케이스가 들어 있습니다. 하지만 항상 정답은 존재하도록 만들어져 있고, 같은 값 쌍을 리더 유지 구간에 중립쌍으로 끼워 넣는 방식으로 대부분 복구할 수 있습니다. 그래서 공식 풀이만으로는 오답이 나고, 중복쌍 처리를 넣은 구성 코드는 통과한 것으로 보입니다.

--
추가 확인

댓글에서 제안해 주신 대로 assert 제출을 해봤습니다.

Ti 중복이 없는지 확인하는 assert는 AssertionFailed가 났습니다. 따라서 hidden data에 Ti 중복이 존재합니다.

공식 해설식 구성 후보가 항상 verify를 통과하는지 확인하는 assert도 AssertionFailed가 났습니다. 따라서 공식 해설식 구성은 hidden data 전체에서 항상 유효하지 않습니다.

또한 공식 후보가 실패했지만 제 코드의 fallback이 verify를 통과한 경우를 assert했을 때도 AssertionFailed가 났습니다. 즉, 공식 후보로는 실패하지만 다른 유효한 답은 존재하는 hidden case가 실제로 있습니다.

마지막으로 Ti 중복이 있으면서 공식 후보가 실패하는 경우를 assert했을 때도 AssertionFailed가 났습니다. 따라서 공식 후보 실패 케이스 중 적어도 하나는 Ti 중복을 포함합니다.

숨은 입력을 직접 본 것은 아니므로 실패한 순간의 정확한 누적합까지는 알 수 없습니다. 하지만 officialCandidate는 입력 보물을 그대로 한 번씩 사용하므로 verify 실패 원인은 동점 발생 또는 리더 부호 불일치입니다. 공식 해설식 구성은 중복값에서 엄격한 부등식을 잃을 수 있으므로, 현재 hidden data에는 중복값 때문에 공식식 구성이 깨지는 케이스가 들어 있다고 보는 것이 가장 자연스럽습니다.