CCC14 Stage 2 - Werewolf

http://wcipeg.com/problem/ccc14s2p3

문제에서 주어지는 명령들을 CNF 형태로 해석해보자, 1 -> 늑대인간, 0 -> 시민이다.

D a b => a -> b
A a b => a -> ~b

CNF 형태가 유용한 점 중 하나는 그래프 이론적인 해석이 가능하다는 것이다. (예를 들어 2-SAT은 도달 가능성 == clause의 모순 여부라는 점을 활용한다.) 여기서 특히 주목할 점은 문제의 조건 대로라면 이렇게 주어진 명령을 그래프화 했을 때 트리 (사실은 포레스트) 형태의 모습이 생긴다는 것이다.

여기서는 늑대인간의 수가 K개인 경우의 수를 묻기 때문에, 이제 조건을 만족하는 경우의 수를 셀 때 트리 DP를 사용하면 된다.

트리 DP를 사용한다 하면 당장 rough하게 떠오르는 식은 dp[pos][k] = 현재 위치, K개의 늑대인간와 같은 점화식일 것이다. 하지만 곤란한 것이 서브트리에 대해서 합쳐나갈 때 지수적인 시간이 소요된다. 이에 대해서 여러 가지 해결 방법이 있지만 가장 간단한 것은 서브트리에 대해서 나누는 방법이다. graph[pos][sub]를 볼때 dp[pos][sub][k] -> Sum(dp[pos][sub+1][i] * dp[pos->sub][0][k - i]) 라는 식을 사용하면 두 개의 서브트리에 대해서만 보면 되고 코딩도 깔끔하다. 이런 식으로 하면 에지수 * N^2 라 O(N^3)에 문제를 해결할 수 있다.

비슷한 문제인 https://www.acmicpc.net/problem/2197 나 https://www.acmicpc.net/problem/1805 역시 고민해볼만함.

cpp : https://gist.github.com/koosaga/74e019fd681a8713987a