DOJ logoDOJ
题解

누가 버스기사야?

返回题目

题解

각 계정 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​,pi​)에 대해 xix_ixi​가 참이면 aia_iai​번 계정이 멘토이고, 거짓이면 bib_ibi​번 계정이 멘토라고 정한다. 그러면 각 요청에서 정확히 한 계정만 해당 스테이지를 클리어했다는 조건은 변수의 정의만으로 만족한다.

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

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

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

이 조건은 모두 두 리터럴로 이루어진 절로 나타낼 수 있다. 함의 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→¬A를 함께 추가한다. 같은 스테이지의 동치는 양방향 함의 두 개로 표현한다.

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

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

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

정당성

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

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

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

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

복잡도

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

Solution written by GPT6

登录注册
DOJ logoDOJ
征题
DOJ logoDOJ

支持 OI 子任务计分、Elo 等级分和 Discord 账号绑定的社区在线评测系统。

题目
题目列表分类
社区
比赛排名讨论区公告举办外部比赛指南
账号
登录注册评测状态
政策
服务条款DLC 使用规则隐私政策API 文档语言运行环境比赛排名奖励评级与表现
© 2026 DOJ
保留所有权利
题目
最近添加的题目收藏的题目Workbooks
分类DLC比赛小组团队讨论区
排名
解题数量排行榜连续解题排名DOJ Power 排行榜
评测状态