BOJ 20689 - Forbidden Card

BOJ 20689 - Forbidden Card

최대 $2N$번의 턴이 진행된다.

forbidden card $X$가 없다고 가정하고 시행했을 때, 지는 사람을 기록한다. 이를 $L$ 이라 하자.

이전 과정에서 $1 \sim M$의 카드가 언제 처음으로 사용되는지 $0 \sim 2N-1$ 중에 하나로 기록한다.

$i \coloneqq 1 \to M$ 으로 순회하며 $i$가 한 번도 안쓰였다면 $L$이 진다.

그렇지 않다면 재귀적인 호출을 이용한다.

$f(t, x)=t$ 번째 턴에 $x$가 사용 불가능이 되었을 때 지는 사람이라고 하자.

$i$가 $j~(0 \le j < 2N)$ 번 째 턴에 사용되었다면 그걸 사용한 사람은 $p=j ~\%~ N$ 이다.

$p$가 카드를 $2$번 째 카드로 사용했다면 이 카드가 사용 불가능이 되면 $p$가 지게된다.

$p$가 이 카드를 $1$ 번째로 사용했다면, 이 카드가 사용 불가능이 되면

• $p$의 두 번째 카드가 아직 사용 안되었다면 $L$이 진다.
• $p$의 두 번째 카드가 사용되었고 $j$ 보다 이른 순서에 사용되었다면 $p$가 진다.
• $p$의 두 번째 카드가 사용되었고, $j$보다 뒤의 순서라면 $f(p\text{의 두 번째 카드를 쓴 턴}, p \text{의 두 번째 카드})$ 가 진다.

재귀적으로 호출해주는 과정을 보면 싸이클이 없는 유향그래프란것을 알 수 있고 따라서 $2N$개의 DP를 처리하면 $O(N+M)$에 문제를 해결할 수 있다.