블로그 옮겼습니다

이 문제는 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의 위치가 다시 같은 상태가 돌아올 수도..

http://codeforces.com/contest/681/problem/D 간단하게 문제를 설명하자면, N개의 사람이있고 M개의 연결관계가 주어진다그리고 하나의 컴포넌트는 트리구조를 이룬다. (여러개의 컴포넌트로 이루어질 수도 있음)N명의 사람들 각각은 선물을 주고 싶은 사람이 한사람 씩 있는데 이 한 사람은 무조건 자기 자신이거나 자신의 조상이어야 한다. 또, 우리는 어떤 list를 작성해야하는데각 N명의 사람들은 list의 맨왼쪽에 있는 명단부터 차례대로 봐가면서 무조건 가장 처음으로 등장하는 조상에게 선물을 줘야한다. 그리고 만약 list를 끝까지 다 봤는데도 자신의 조상이 나오지 않는다면 아무에게도 선물을 주지 못하고 집에간다. 문제는 N명의 사람모두가 자기가 선물을 주고 싶은 사람에게 선물을..

그래프 + dp 이다. N

사실 원래의 풀이와 아주 큰 차이는 없다. 두번의 dfs를 돌리는 것까지는 똑같지만 변수가 하나 줄었고, 점화식이 좀 더 단순해 졌다. 우선 size(i) 는 i를 루트로 갖는 서브트리의 총 노드수라고 보면노드 i 부터 자손들까지의 거리의 총합 S(i)는,노드 i의 자식이 c1, c2, c3..... cn 이고, ck 와 연결된 간선의 가중치는 wk 일때size(c1)*w1 + size(c2)*w2 +....+size(cn)*wn +S(c1) + S(c2) + S(c3) +.....+S(cn) 이다.즉 각각의 간선에 대해 몇번 지남당하는지를 계산한다고 보면된다. 이렇게 각각의 간선에 대해 몇 개의 경로에 대해 지남 당하느냐로거리 의 총합을 구하는 경우가 많은 것같다. 트리상에 존재하는 모든 정점쌍간의 거..

우선 이 문제를 풀기 위해서 한가지 선행 지식이 필요하다. N개의 노드를 가진 트리에서 모든 정점 쌍의 거리의 합을 O(N)에 구할 수가 있는데 size(i) = i번 노드를 루트로 갖는 서브트리의 노드의 수. 로 정의하여 재귀적으로 모든 노드에 대해 구하면서 각 간선을 지나는 경로의 수를 dfs로 구하는것이다. 이 전, 전 포스트에 설명이 되어있다. 하지만 이 문제는 점프 거리 k 라는 입력이 주어져서 한번에 k개의 간선을 뛰어넘을 수가 있고, 단순히 모든 정점쌍 사이의 거리의 합이 아니라 모든 정점 쌍 사이의 경로를 가기위한 점프 횟수의 합을 요구한다. 그렇기 때문에 최대 점프거리 k가 3일때, 거리가 3인 경로는 3이 아니라 1이 더해져야하고 4인 경로는 4가 아니라 2가 더해져야하는 식이다. 여기..

이 문제는 N개의 노드를 가지고 간선에 가중치가 있는 트리에서 중앙 정점이라는 것을 찾아서 이 중앙 정점에서 다른 정점까지의 모든 거리의 합을 구하는 문제이다.중앙 정점의 정의는 어떤 한 점에서 다른 모든 정점까지의 거리의 합이 최소가 되는 점이다. 처음에 트리의 중심과 헷갈려서 트리의 중심으로 풀 뻔 했는데 잘 생각해 보면 트리의 중심은 어떤 한 점에서 다른 모든 정점까지의 거리의 최대값이 최소가 되는 점이기 때문에 확실히 다른 개념이다. 그렇다면 이 중앙 정점이라는 것은 어떻게 구할까? naive 하게는 각 N개의 정점에서부터 BFS나 DFS를돌려서 한 점에서 다른 모든 점까지의 거리의 합을 구하고 이 값을 바탕으로 최소값을 갱신해 나가는 O(N^2) 의 방법이 있을 것이다. 하지만 N이 10000 ..

naive 하게 모든 노드쌍간의 거리의 총합을 구한다고 하면 총 N개의 노드에 대해 DFS 혹은 BFS를 돌려서 O(N^2) 에 구하는 것이지만 N이 좀더 커지만 사용할 수가 없다.이 때 발상을 조금 전환해서 모든 가능한 경로상에 각각의 간선이 총 몇번이나 포함되는지를 세어주면 이 것의 총합이 우리가 구하고자 하는 답이 될 것이다.그렇다면 트리에서 루트 노드를 제외한 다른 모든 노드들은 하나의 부모가 있으므로 부모와 연결된 간선을 하나씩 가질 것이므로 루트를 제외한 하나의 노드는 각각 하나의 간선과 짝지어질 것이다. 그렇다면 루트 노드를 제외한 각각의 노드에 대해 자신의 부모와 연결된 간선을 지나는 모든 경로의 가지수를 계산하여 누적해 준다면 답이 될것인데 이것은 어떻게하냐면, size(i) 를 i번 노..

1c, a->c 가 연결 되어있다면 a->c 가 없어도 a에서 b를 통해 c로 갈 수 있기 때문에 a->c 는 필요 없는 간선이 된다. 아무튼 이런 쓸모없는 간선들을 찾아서 지워주는게 문제의 핵심인데, 문제는 어떻게 해야하느냐이다. 우선 확실한건 같은 SCC내에 있는 노드 K개가 있다면 이 들이 SCC를 이루기 위한 최소한의 간선 수는 K개 이다. 이 것은 자명하다. 그리고 다른 SCC간의 간선은 딱 하나만 필요하므로 정점 압축을 한뒤 플로이드로 불필요한 간선을 지울 수가 있다. u -> k 이고 k -> v이면 u -> v 는 필요없다는 식으로 지울수있다. 그리고 SCC를 묶지않고 처음부터 플로이드로만 불필요한 간선을 지우면 되지않을까해서 새로 짜봤는데 틀렸는데, 생각을 좀 해보면. 같은 SCC 내에 ..

https://oj.uz/problem/view/OJUZ11_rail 2