[codeforces] 1876C. Autosynthesis

문제 링크

길이가 $n$인 수열 $a$가 주어지고 동그라미 치지 않은 요소들만 모아놓은 수열 $p$와 동그라미 친 순서대로 요소의 인덱스를 나열한 수열 $r$이 있을 때, $p = r$이 되는 수열 $p$ (또는 $r$)을 출력하는 문제입니다. 한 원소를 여러번 동그라미 칠 수도 있습니다.

먼저 다음 lemma를 증명해 보겠습니다.

Lemma. $i$번째 요소를 동그라미 치지 않는다면 $a_{j} = i$인 모든 $a$의 요소들은 동그라미쳐야 한다. 반대로 $i$번째 요소를 동그라미 친다면 $a_{j} = i$인 $a$의 요소들 중 적어도 하나는 동그라미 치면 안된다.

proof) 증명은 간단합니다. 먼저 $i$번째 요소를 동그라미 치지 않았는데 $a_{j} = i$이면서 동그라미 치지않은 $j$가 존재한다고 하면 $i$는 수열 $p$에 포함됩니다. 하지만 $i$는 $r$에 포함되지 않습니다. 즉, 모순입니다.
이번에는 $i$번째 요소와 $a_{j} = i$인 $a$의 요소들을 동그라미 쳤다고 가정해 봅시다. 이렇게 되면 $i$는 $r$에 포함되지만 $p$에는 포함되지 않습니다. 즉, 모순입니다.
이것으로 lemma가 증명되었습니다.

해당 lemma를 어떻게 사용할 수 있을까요? 여기서부터는 문제에 올라와 있는 예제로 설명하겠습니다.
우선 명제 $i$를 "$a_{i}$는 동그라미 쳐져있다."로 정의하겠습니다.
그럼 3 4 2 2 3에서 아래와 같은 논리식들을 얻을 수 있습니다.

그리고 위 논리식들을 통해 아래와 같이 그래프로 모델링 할 수 있습니다.

위 그래프의 각 노드에 대해 설명하자면

• $i$ 또는 $\neg i$ 노드 : 각 명제를 나타내는 노드입니다. 해당 노드에 도달하는 논리값이 해당 명제의 논리값이 됩니다.
• True 노드 : True 값을 흘려보내는 노드입니다.
• not 노드 : 해당 노드를 지나가면 논리 값이 반전됩니다.
• and 노드 : 노드로 진입하는 모든 간선으로 부터 흘러 들어오는 논리 값의 and 값을 흘려 보냅니다. 한 간선에서 False가 흘러 들어오거나 진입하는 모든 간선으로부터 논리값을 받은 이후에 값을 흘려보냅니다.

해당 그래프를 DFS 비슷하게 탐색하면서 $i$ 노드에 어떤 논리값이 들어오는지를 구해주기만 하면 됩니다.
하지만 True 노드에서 시작하여 탐색을 하고 난 이후에도 거치지 못한 $i$ 노드가 있을 수 있습니다. 이 때는 아직 거치지 못한 노드 하나를 선택해서 그 노드에 True를 흘려보내주면 됩니다. 탐색 안한 노드가 없을 때 까지 이 과정을 반복합니다.
그리고 탐색 중간에 이미 탐색 한 $i$ 노드에 대하여 처음에 보낸 논리값과 다른 논리값을 보내는 시도를 할 수 있습니다. 이 때는 $i$명제의 논리값을 어떤것으로 정해도 문제가 생긴다는 의미이고 이 말은 즉슨 $i$번째 요소에 동그라미를 치는 안 치든 $p = r$이 되게 만들 수 없다는 것을 의미합니다. 그렇기 때문에 $-1$을 출력해 주면 됩니다.

모델링한 그래프의 정점과 간선의 갯수는 각각 $O(N)$개이므로 시간복잡도는 $O(N)$이 됩니다.

pseudo code는 다음과 같습니다.

N, a <- size of sequence, sequence
G <- modeling graph

success <- success or failure of "do dfs for G from True Node"

if success is False {
	print -1
    program finished
}

loop i from 1 to N {
	if i node does not visited {
    	success <- success or failure of "do dfs for G from i Node and value of i node is True"
        if success is False {
            print -1
            program finished
        }
    }
}

ans <- list of a[i] such that value of i node is False
print size of ans and ans