DOJ logoDOJ
Problems
Recently added problemsSaved problemsWorkbooks
CategoriesDLCContestsGroupsTeamsBoard
Ranking
Solved Problem RankingStreak rankingDOJ Power ranking
Status
Call for TasksLoginRegister
DOJ logoDOJ

Community online judge with OI-style subtask scoring, Elo ratings, and Discord account linking.

Problems
ProblemsCategories
Community
ContestsRankingBoardNoticesHost an external contestGuide
Account
LoginRegisterJudge Status
Policy
Terms of ServiceDLC RulesPrivacyAPI documentationLanguage runtimesContest rank rewardsRating and performance
© 2026 DOJ
All rights reserved
Editorial

누가 버스기사야?

Back to problem

Editorial

각 계정 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)