DOJ logoDOJ
문제
최근 추가된 문제들저장한 문제문제집
카테고리DLC대회그룹팀게시판
랭킹
문제 풀이 랭킹스트릭 랭킹DOJ Power 랭킹
현황
문제 제안로그인회원가입
DOJ logoDOJ

OI 서브태스크 채점, Elo 레이팅, Discord 계정 연동을 갖춘 커뮤니티 온라인 저지.

문제
문제 목록카테고리
커뮤니티
대회랭킹게시판공지사항외부 대회 개최이용 안내
계정
로그인회원가입채점 현황
정책
이용약관DLC 이용 규칙개인정보 처리방침API 사용 설명서언어별 채점 환경대회 순위 보상레이팅과 퍼포먼스
© 2026 DOJ
모든 권리 보유
해설

최솟값 제거

문제로 돌아가기

해설

지울 수 있는 원소 원소 xxx가 길이 222 이상의 구간에서 최솟값이라면, 그 구간 안에서 xxx와 바로 이웃한 원소 하나가 반드시 존재하고 xxx보다 크다. 반대로 바로 이웃한 원소가 xxx보다 크면 그 둘을 구간으로 골라 xxx를 지울 수 있다. 따라서 현재 왼쪽 또는 오른쪽 이웃 중 더 큰 원소가 존재하는 것이 삭제 가능 조건이다.

남길 위치의 순서 연산은 삭제만 하므로 AAA는 PPP의 부분 수열이어야 한다. 값 vvv의 원래 위치를 pos[v]\mathrm{pos}[v]pos[v]라 하면

pos[A1]<pos[A2]<⋯<pos[AM]\mathrm{pos}[A_1]<\mathrm{pos}[A_2]<\cdots<\mathrm{pos}[A_M]pos[A1​]<pos[A2​]

을 확인한다. 같은 값이 반복되는 경우도 이 검사로 거부된다.

삭제 구간의 조건 남길 원소들은 삭제되지 않으므로, 지울 원소들은 첫 남길 원소 왼쪽, 남길 원소 사이, 마지막 남길 원소 오른쪽의 구간들로 나뉜다. 각 구간은 다른 구간의 원소와 직접 이웃할 수 없다.

비어 있지 않은 삭제 구간의 최댓값을 ggg, 맞닿은 남길 원소 중 큰 값을 bbb라고 하자. 양끝 구간에는 맞닿는 남길 원소가 하나만 있다. 이 구간을 전부 지울 수 있는 필요충분조건은 g<bg<bg<b이다.

필요성: ggg를 지우는 순간 더 큰 이웃이 있어야 한다. 같은 구간 안에는 그런 원소가 없으므로 그 이웃은 남길 경계 원소이며, 따라서 b>gb>gb>g이다.

충분성: 구간의 원소를 작은 것부터 지운다. 두 개 이상 남아 있으면 가장 작은 원소는 같은 구간의 더 큰 원소 하나와 이웃하므로 지울 수 있다. 마지막으로 ggg만 남으면 b>gb>gb>g인 경계 원소와 이웃하므로 지울 수 있다. 빈 구간은 자동으로 조건을 만족한다.

구현 남길 원소를 순서대로 따라가며 그 앞의 삭제 구간 최댓값을 한 번씩 훑는다. 왼쪽에 남길 원소가 없으면 경계값을 000으로 두고, 구간이 비었을 때의 최댓값도 000으로 둔다. 모든 실제 값이 양수이므로 같은 비교식을 사용할 수 있다. 마지막 남길 원소 오른쪽도 따로 확인한다.

순서 조건과 모든 구간 조건을 만족하면 YES, 아니면 NO이다. 전역 최댓값 NNN은 절대로 삭제되지 않으므로 AAA에 없으면 반드시 NO가 된다. 이 사실만 확인하거나 부분 수열 여부만 확인하는 것으로는 충분하지 않다. 예를 들어 P=[6,1,5,2,3,4]P=[6,1,5,2,3,4]P=[6,1,5,2,3,4], 는 최댓값을 포함한 부분 수열이지만 의 양쪽 경계가 라서 불가능하다.

시간은 O(N+M)O(N+M)O(N+M), 공간은 O(N+M)O(N+M)O(N+M)이다. 위치, 원소, 구간 최댓값은 모두 200 000200\,000200000 이하이며 큰 정수 연산이 필요 없다.

서브태스크 1은 현재 남아 있는 위치들을 비트마스크로 나타내고 가능한 모든 연속 구간 연산을 BFS로 탐색한다. 상태 수는 2N2^N2N 이하이며, 각 상태에서 구간 최솟값을 점진적으로 유지하면 O(N2)O(N^2)O(N2)에 모든 연산을 열거한다. 시간은 O(2NN2)O(2^N N^2)O(2, 공간은 로 에서 충분하다. 서브태스크 2는 위 선형 검사를 사용한다.

Solution written by GPT6

<
⋯<
pos[AM​]
A=[6,1,2,3,4]A=[6,1,2,3,4]
A=[6,1,2,3,4]
555
1,21,21,2
N
N2
)
O(2N+N)O(2^N+N)O(2N+N)
N≤10N\leq10N≤10