#8202 Conspiracy

https://www.acmicpc.net/problem/8202

 

support와 conspiracy 두 개의 그룹으로 나누어야 한다.

support는 완전그래프고, conspiracy는 사이에는 간선이 없도록 해야 한다.

 

단상 1.

간선의 총 개수를 m이라고 하자.

그러면 support 그룹이 a명이면 sum_of_deg(support) = m + a * (a - 1) / 2 가 성립해야 한다.

혹시 이거만 성립한다면 충분한가?

X = (support간 간선), Y = (support-conspiracy), Z = (conspircacy간 간선)이라면, 위 식은 다음과 같다

-> X * 2 + Y = X + Y + Z + a * (a - 1) / 2 -> X = Z + a * (a - 1) / 2

-> 이때 X가 a * (a - 1) / 2를 넘을 수는 없으므로 저 식만 만족하면 끝이다.

 

단순한 dp로는 불가능하고 FFT도 좀 가능성이 있어보이긴 하는데...

x개를 모아서 합이 m + x * (x - 1) / 2가 되도록 하는 방법의 수를 하려면 복잡도가 최소 O(NMlgN)은 뜨겠는데..

adj[i] >= x - 1인 경우에만 포함될 수 있다는 것으로 계산을 줄일 수 있을까?

//2SAT에 의한 생각 전환

 

단상 2.

이거 2sat 느낌으로 되는게 아닌가?

-> u, v 사이에 간선이 있다면 (~u or ~v)

-> u, v 사이에 간선이 있다면 (u or v)

-> 근데 2SAT의 경우의 수를 세는 거는 일반적인 케이스에선 불가능하다고 알고있다.

//빠른 포기

 

단상 3.

어떤 답이 되는 분류가 있다고 가정하자.

그렇다면 여기에서 support는 숫자가 변화한다면 1명만 추가하거나, 1명만 제거할 수 있다.

-> 2명이 추가 가능하다면, 이 둘 사이에 간선이 있는 것이므로, 지금 상태에 모순

-> 2명이 제거 가능하다면, 이 둘 사이에 간선이 없는 것이므로, 지금 상태에 모순

따라서 한 state만 찾으면, 여기서 1명 제거, 1명 추가, 1명 빼고 + 1명 추가만 세보면 된다

-> 한 state를 찾는 것은 2sat로 하면 된다.

-> 이후는 걍 실제로 세보면 된다. a가 혼자 빠질 수 있는지, b가 혼자 더해질 수 있는지, a와 b가 동시에 움직이는지

추가적으로 conspiracy나 support는 빈 집단일 수 없기 때문에 이것의 예외처리를 해주어야 한다.

 

다른 풀이 1)

단상 1에서 이 생각을 미처하지 못하였다.

만일 크기가 X라면, support에 속한 애들은 deg가 X - 1보다 크거나 같고, 다른 애들은 X보다 작거나 같다.

-> 따라서 대충 보았을 때 deg[support] + 1 >= deg[conspiracy]가 성립한다.

-> 여기에 아까의 sum_of_deg 조건을 추가하면 어렵지 않게 찾을 수 있다.

 

다른 풀이 2)

3개의 점을 살펴보자.

만일 2개만 서로 연결되어 있다면, 나머지 1개는 무조건 conspiracy이다.

만일 1개만 모두에게 연결되어있다면, 그 점은 무조건 support이다.

이를 통해서 모든 삼각형을 보면 support, conspiracy로 몇 개가 확정되고, 남는 점들은 모두 연결되거나 모두 분리됨

-> 여기서부터는 내가 하듯이 1개 넘게 뭐가 안되기 때문에 casework를 하면 된다고 한다.