BOJ 20656 지구종말 (03-21)

11 10

1 2 3

1 2 4

1 2 5

1 2 6

1 3 6

1 4 6

1 5 6

1 3 4

1 3 5

2 3 11
해당 테스트케이스는 NIE이다

N 230, M 24580 부근의 케이스가 존재한다

 

가능한 state의 수는 $2^{N}$개이다

 

M의 원소마다 가지는 |F|는 간단한 형태의 생성함수 꼴로 구할 수 있다 

 

21일

 

주어지는 리스트는 $a<b<c$를 만족하므로 다음과 같은 케이스를 생각할 수 있다

1 9 7 1 2 5 5 8 9 5 6 7 2 3 5 1 3 5 1 4 6 1 5 7 TAK

1 9 7 1 2 5 5 8 9 5 6 7 2 3 5 1 3 5 1 4 6 1 4 7 NIE

inital state 다음의 모든 state가 불가능하다면 당연히 NIE이며 연결되어 있더라도 어느 순간 cut이 존재할 수 있다

리스트에 적힌 생존자는 모두 3명임이 보장되므로 cut이 존재한다면 left bank 혹은 right bank이 사이즈가 3인 경우이다

state가 비트로 표현되므로 state와 ~state는 symmetry group이지만 boat의 위치 또한 영향을 받는다