목록위상정렬 (2)
블로그 옮겼습니다
http://codeforces.com/contest/787/problem/C 이 문제는 게임 dp 문제인데 Nim 게임과 같은 게임 dp 문제와 다른점이 하나 있다. Nim 게임에서는 보통 두 플레이어가 매 턴 마다 돌을 한개 이상씩 가져가기 때문에 돌이 점점 줄어들고, 그렇기 때문에 돌의 개수와 현재 차례인 플레이어, 이 두가지로 하나의 상태를 정의할 때 그래프로 표현해 보면 노드 A에서 노드 B로 가는 경로가 여러개가 있을 수는 있지만 한번 방문한 노드는 다시 방문되어지지 않는다 (즉, 사이클이 없다) 하지만 이 게임에서는 monster 가 움직일 칸 수를 번갈아서 결정하다 보면 게임 판이 원의 형태로 되어있기 때문에 현재 차례인 플레이어와 현재 monster의 위치가 다시 같은 상태가 돌아올 수도..
http://codeforces.com/contest/681/problem/D 간단하게 문제를 설명하자면, N개의 사람이있고 M개의 연결관계가 주어진다그리고 하나의 컴포넌트는 트리구조를 이룬다. (여러개의 컴포넌트로 이루어질 수도 있음)N명의 사람들 각각은 선물을 주고 싶은 사람이 한사람 씩 있는데 이 한 사람은 무조건 자기 자신이거나 자신의 조상이어야 한다. 또, 우리는 어떤 list를 작성해야하는데각 N명의 사람들은 list의 맨왼쪽에 있는 명단부터 차례대로 봐가면서 무조건 가장 처음으로 등장하는 조상에게 선물을 줘야한다. 그리고 만약 list를 끝까지 다 봤는데도 자신의 조상이 나오지 않는다면 아무에게도 선물을 주지 못하고 집에간다. 문제는 N명의 사람모두가 자기가 선물을 주고 싶은 사람에게 선물을..