PS 이야기

온라인 아카이브 링크 A. The Mountain of Gold? 0번 도시에서 시작하고 시공간을 이동할 수 있는 수단들이 주어졌을 때, 0번 도시의 과거로 돌아올 수 있는지 판별하는 문제다. 일반적으로 $O(NM)$ 시간복잡도의 Bellman-ford 알고리즘은 전체 그래프에서 음수 싸이클이 있는지 판별할 때 쓰인다. 이 문제에서는 0번 도시와 강하게 연결된 연결 요소(0번 도시에서 $x$로 갈 수 있고, $x$에서 0번 도시로 올 수도 있는 $x$들의 집합)에서 음수 싸이클이 있는지 Bellman-ford로 $O(NM)$만에 확인해주면 된다. #include #include #include using namespace std; typedef vector arr; int T, N, M; int D[10..

Grundy Number는 게임 문제에서 많이 사용되는 방법 중 하나다. Grundy Number는 게임 상황을 Nim Game으로 변환 시켜주는 과정이라고 볼 수 있다. 어떤 상황 $S$에 대한 Grundy Number를 구하는 방법은 아래와 같다. 상황 $S$에서 다음 상황들 중 하나를 $S'$라고 하자. $G(S) = \min(v) $ ($v \not\in \{G(S')\}$) 즉, 상황 $S$의 Grundy Number $G(S)$는 상황 $S$의 다음 상황들 $S'$의 Grundy Number $G(S')$들 중 존재하지 않는 가장 작은 수다. 각 상황들을 Grundy Number로 표현했을 때, 필승법의 여부는 Nim Game과 마찬가지로 구하면 된다. Grundy Number로 표현된 각 상..