qnffidfhqht   10달 전

안녕하세요. 질문 게시판에서 검색해 보았으나 같은 내용의 글/반례를 찾지 못해 문의드립니다.

문제 설명에는 보물 가치 TiT_iTi​에 대해 별도의 “서로 다름” 조건이 없고(중복 가능해 보임),
또 “항상 정답이 존재하는 입력만 주어진다”고 되어 있습니다.

그런데 중복이 허용되는 경우, UCPC 원문(Programs 초등학교)에서 알려진 구성 방식(정렬 후 역순으로 리더 변화면 큰 값 / 유지면 작은 값 선택 등)과 같은 유형의 구성은 일반적으로 성립하지 않는 것으로 보입니다.

아래 입력은 문제 조건을 만족하며(정답이 존재), 실제로 정답 예시가 있습니다.

반례 (정답 존재)

입력:

1
3
3 3 4
1 1 2

가능한 정답 출력 예:

4 1
3 2
3 2

(누적합을 계산해 보면 리더가 1 → 1 → 2가 되며, 중간 동점도 없습니다.)

따라서,

  • TiT_iTi​가 항상 서로 다른 값이라는 조건이 누락된 것인지, 또는

  • 중복이 허용되는 것이 맞다면 “항상 정답 존재”를 보장하는 추가 제약/데이터 조건이 따로 있는지

확인 부탁드립니다. 필요하다면 조건 보완/데이터 점검 및 리저지도 요청드립니다.

감사합니다.

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