블로그 옮겼습니다

https://community.topcoder.com/stat?c=problem_statement&pm=11500 우선 문제는 흔히 알고있는 '사천성' 이라는 게임을 최소한의 턴 수로 클리어 하기 위해 필요한 턴 수의 기대값이다.그냥 그때 그때 최적의 선택을 할 때 클리어 하는 데 필요한 턴 수의 기대값이라고 생각하면 될 것 같다. 처음에 실수할 수 있는 것이 뭐냐면.. 실제로 게임을 할 때 뒤집혀 있는 두개의 칸을 선택하면 이 두개가 동시에 뒤집히는것이 아니라 하나씩 선택을 하는데, 하나를 선택하면 이것이 뒤집하고 이 정보를 바탕으로 더 최적의 선택을 할 수가 있기 때문에 답이 다르게 나온다는 사실이다. 문제에서 플레이어는 한번 뒤집었던 칸의 모양은 평생 기억한다고 되어있기 때문에 클리어 까지 필요한..

이 문제는 M개의 트리가 주어지고 각각의 트리에 대해 하나의 엣지를 선택하여 오른쪽 트리에게 주었을때(마지막 트리는 맨 처음 트리에게 준다.) 각 M개의 트리가 여전히 모두 트리가 되도록 간선을 선택하는 모든 경우의 수를 계산하는 문제이다. 우선 이 문제는 dp 로 풀 수가있다. 그래서 내가 처음 생각해낸 풀이는 dp[i][u][v] : i-1번째 트리에서 엣지 u-v 를 선택했고 i번째 트리부터 엣지들을 잘 선택했을때 M개의 트리가 여전히 트리인 경우의수 이렇게 하면 각각의 트리의 모든 엣지에 대해 없애보고 이전 트리에서 넘겨준 u-v 를 추가했을 때 여전히 트리가 된다면 선택하고 다음트리로 넘어가는 식으로 구현하면 되고 기저 케이스는 M번째 까지 왔을 때 0번째 트리에서 삭제한 엣지를 저장해 두었다가..

http://codeforces.com/contest/787/problem/C 이 문제는 게임 dp 문제인데 Nim 게임과 같은 게임 dp 문제와 다른점이 하나 있다. Nim 게임에서는 보통 두 플레이어가 매 턴 마다 돌을 한개 이상씩 가져가기 때문에 돌이 점점 줄어들고, 그렇기 때문에 돌의 개수와 현재 차례인 플레이어, 이 두가지로 하나의 상태를 정의할 때 그래프로 표현해 보면 노드 A에서 노드 B로 가는 경로가 여러개가 있을 수는 있지만 한번 방문한 노드는 다시 방문되어지지 않는다 (즉, 사이클이 없다) 하지만 이 게임에서는 monster 가 움직일 칸 수를 번갈아서 결정하다 보면 게임 판이 원의 형태로 되어있기 때문에 현재 차례인 플레이어와 현재 monster의 위치가 다시 같은 상태가 돌아올 수도..