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

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

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

누가 버스기사야?

문제로 돌아가기

해설

각 계정 vvv가 kvk_vkv​번 스테이지까지 클리어했다고 하자. 가능한 범위는 0≤kv≤M0\leq k_v\leq M0≤kv​≤M이며, ppp번 스테이지의 클리어 여부는 kv≥pk_v\geq pkv​≥p인지로 결정된다.

계정 하나의 진도는 여러 값을 가질 수 있다. 대신 각 요청에서 어느 계정이 멘토인지를 논리 변수로 표현한다. iii번 요청 (ai,bi,pi)(a_i,b_i,p_i)(ai​,bi​,p에 대해 가 참이면 번 계정이 멘토이고, 거짓이면 번 계정이 멘토라고 정한다. 그러면 각 요청에서 정확히 한 계정만 해당 스테이지를 클리어했다는 조건은 변수의 정의만으로 만족한다.

계정 vvv가 iii번 요청에 등장할 때, 그 요청의 스테이지를 클리어했다는 명제를 Lv,iL_{v,i}Lv,i​로 나타내자. v=aiv=a_iv=이면 이고, 이면 이다.

같은 계정이 등장하는 두 요청 i,ji,ji,j를 생각하자.

  • pi<pjp_i<p_jpi​<pj​이면 Lv,j⇒Lv,iL_{v,j}\Rightarrow L_{v,i}L이어야 한다. 뒤의 스테이지를 클리어했다면 앞의 스테이지도 클리어했기 때문이다.

이 조건은 모두 두 리터럴로 이루어진 절로 나타낼 수 있다. 함의 A⇒BA\Rightarrow BA⇒B는 ¬A∨B\neg A\lor B¬A∨B와 같으며, 함의 그래프에 A→BA\to BA→B와 그 대우인 ¬B→¬A\neg B\to\neg A¬B를 함께 추가한다. 같은 스테이지의 동치는 양방향 함의 두 개로 표현한다.

모든 요청 쌍을 비교하면 시간이 오래 걸린다. 각 계정의 등장 정보를 스테이지 번호순으로 정렬하고, 정렬된 순서에서 이웃한 두 등장 정보 사이의 조건만 추가하자. 같은 스테이지의 정보는 동치 관계로 이어지고, 더 큰 스테이지에서 더 작은 스테이지로 함의가 이어진다. 함의의 추이성에 의해 떨어져 있는 모든 요청 쌍의 조건도 만족한다.

정답 코드는 각 요청에서 두 개의 등장 정보 (계정 번호,스테이지 번호,리터럴)(\text{계정 번호},\text{스테이지 번호},\text{리터럴})(계정 번호,스테이지 번호,리터럴)를 만들고, 총 2Q2Q2Q개의 정보를 한꺼번에 정렬한다. 정렬 기준은 계정 번호, 스테이지 번호, 리터럴 번호 순이다. 계정 번호가 같은 이웃한 정보만 연결한다. 같은 스테이지의 정보는 한 방향만 연결해서는 안 된다.

이제 만들어진 2-SAT 식의 만족 가능성을 강한 연결 요소로 판정한다. 어떤 변수와 그 부정이 같은 강한 연결 요소에 속하면 답은 NO이고, 그렇지 않으면 YES이다.

정당성

실제 클리어 상태가 모든 요청을 만족한다면, 각 요청에서 실제 멘토인 계정을 골라 xix_ixi​의 값을 정할 수 있다. 한 계정의 클리어 상태는 앞에서부터 연속한 구간이므로, 추가한 모든 함의와 동치 조건도 만족한다. 따라서 실제 설정이 존재하면 2-SAT 식을 만족시킬 수 있다.

반대로 2-SAT 식을 만족하는 변수 값이 있다고 하자. 각 계정의 등장 정보를 스테이지 번호순으로 나열하면, 클리어했다는 명제는 참인 구간 뒤에 거짓인 구간이 오는 형태이고, 같은 스테이지에서는 값이 같다. 계정 vvv에 대해 참인 등장 정보가 있으면 그 스테이지 번호의 최댓값을 kvk_vkv​로 정하고, 없으면 kv=0k_v=0kv​=으로 정한다. 요청에 등장하지 않는 계정도 으로 정한다.

이때 0≤kv≤M0\leq k_v\leq M0≤kv​≤M이다. 참인 등장 정보의 스테이지는 kvk_vkv​ 이하이고, 거짓인 등장 정보의 스테이지는 보다 크다. 따라서 번부터 번까지를 클리어한 상태는 모든 등장 정보의 참과 거짓을 그대로 실현한다. 각 요청에서는 변수의 정의에 의해 정확히 한 계정만 해당 스테이지를 클리어했으므로 모든 요청에서 매칭이 가능하다.

두 방향이 모두 성립하므로 2-SAT의 판정 결과가 정답이다.

복잡도

정렬할 등장 정보는 2Q2Q2Q개이고, 논리 변수는 QQQ개이다. 각 이웃한 정보 쌍에서 상수 개의 간선을 추가하므로 함의 그래프의 정점 수와 간선 수는 모두 O(Q)O(Q)O(Q)이다. 전체 시간 복잡도는 O(Qlog⁡Q)O(Q\log Q)O(QlogQ), 공간 복잡도는 O(Q)이다. 정답 코드는 깊은 그래프에서도 호출 스택이 넘치지 않도록 두 번의 깊이 우선 탐색을 모두 반복문으로 수행한다.

Solution written by GPT6

i
​
)
xix_ixi​
aia_iai​
bib_ibi​
ai​
Lv,i=xiL_{v,i}=x_iLv,i​=xi​
v=biv=b_iv=bi​
Lv,i=¬xiL_{v,i}=\neg x_iLv,i​=¬xi​
v,j
​
⇒
Lv,i​
  • pi=pjp_i=p_jpi​=pj​이면 Lv,iL_{v,i}Lv,i​와 Lv,jL_{v,j}Lv,j​의 참과 거짓이 같아야 한다.
  • →
    ¬A
    0
    kv=0k_v=0kv​=0
    kvk_v
    kv​
    111
    kvk_vkv​
    O(Q)
    O(Q)