각 계정 가 번 스테이지까지 클리어했다고 하자. 가능한 범위는 이며, 번 스테이지의 클리어 여부는 인지로 결정된다.
계정 하나의 진도는 여러 값을 가질 수 있다. 대신 각 요청에서 어느 계정이 멘토인지를 논리 변수로 표현한다. 번 요청 에 대해 가 참이면 번 계정이 멘토이고, 거짓이면 번 계정이 멘토라고 정한다. 그러면 각 요청에서 정확히 한 계정만 해당 스테이지를 클리어했다는 조건은 변수의 정의만으로 만족한다.
계정 가 번 요청에 등장할 때, 그 요청의 스테이지를 클리어했다는 명제를 로 나타내자. 이면 이고, 이면 이다.
같은 계정이 등장하는 두 요청 를 생각하자.
이 조건은 모두 두 리터럴로 이루어진 절로 나타낼 수 있다. 함의 는 와 같으며, 함의 그래프에 와 그 대우인 를 함께 추가한다. 같은 스테이지의 동치는 양방향 함의 두 개로 표현한다.
모든 요청 쌍을 비교하면 시간이 오래 걸린다. 각 계정의 등장 정보를 스테이지 번호순으로 정렬하고, 정렬된 순서에서 이웃한 두 등장 정보 사이의 조건만 추가하자. 같은 스테이지의 정보는 동치 관계로 이어지고, 더 큰 스테이지에서 더 작은 스테이지로 함의가 이어진다. 함의의 추이성에 의해 떨어져 있는 모든 요청 쌍의 조건도 만족한다.
정답 코드는 각 요청에서 두 개의 등장 정보 를 만들고, 총 개의 정보를 한꺼번에 정렬한다. 정렬 기준은 계정 번호, 스테이지 번호, 리터럴 번호 순이다. 계정 번호가 같은 이웃한 정보만 연결한다. 같은 스테이지의 정보는 한 방향만 연결해서는 안 된다.
이제 만들어진 2-SAT 식의 만족 가능성을 강한 연결 요소로 판정한다. 어떤 변수와 그 부정이 같은 강한 연결 요소에 속하면 답은 NO이고, 그렇지 않으면 YES이다.
정당성
실제 클리어 상태가 모든 요청을 만족한다면, 각 요청에서 실제 멘토인 계정을 골라 의 값을 정할 수 있다. 한 계정의 클리어 상태는 앞에서부터 연속한 구간이므로, 추가한 모든 함의와 동치 조건도 만족한다. 따라서 실제 설정이 존재하면 2-SAT 식을 만족시킬 수 있다.
반대로 2-SAT 식을 만족하는 변수 값이 있다고 하자. 각 계정의 등장 정보를 스테이지 번호순으로 나열하면, 클리어했다는 명제는 참인 구간 뒤에 거짓인 구간이 오는 형태이고, 같은 스테이지에서는 값이 같다. 계정 에 대해 참인 등장 정보가 있으면 그 스테이지 번호의 최댓값을 로 정하고, 없으면 으로 정한다. 요청에 등장하지 않는 계정도 으로 정한다.
이때 이다. 참인 등장 정보의 스테이지는 이하이고, 거짓인 등장 정보의 스테이지는 보다 크다. 따라서 번부터 번까지를 클리어한 상태는 모든 등장 정보의 참과 거짓을 그대로 실현한다. 각 요청에서는 변수의 정의에 의해 정확히 한 계정만 해당 스테이지를 클리어했으므로 모든 요청에서 매칭이 가능하다.
두 방향이 모두 성립하므로 2-SAT의 판정 결과가 정답이다.
복잡도
정렬할 등장 정보는 개이고, 논리 변수는 개이다. 각 이웃한 정보 쌍에서 상수 개의 간선을 추가하므로 함의 그래프의 정점 수와 간선 수는 모두 이다. 전체 시간 복잡도는 , 공간 복잡도는 이다. 정답 코드는 깊은 그래프에서도 호출 스택이 넘치지 않도록 두 번의 깊이 우선 탐색을 모두 반복문으로 수행한다.
Solution written by GPT6