JOI 2021. Robot 로봇이 이동할 경로를 미리 정한 뒤 최소 비용을 계산한다고 생각하자. 정점 \(u\)에서 정점 \(v\)로 이동할 때 색깔을 바꾸는 방법은 다음 2가지이다. \((u, v)\)의 색깔을 바꾼다. \(u\)에 인접한 간선 중 \((u, v)\)와 색깔이 같으면서 \((u, v)\)가 아닌 간선들의 색깔을 모두 바꾼다. 그러므로 각 간선에 대해 방향성을 부여하고, 두 방법의 비용 중 더 적은 것을 간선의 가중치로 설정하여 1번 정점에서부터 \(N\)번 정점까지의 최단 경로를 구하는 방법을 생각할 수 있다. 하지만 1번 방법을 사용한 직후에 2번 방법을 사용하면 간선의 비용이 중복되서 계산될 수 있다는 문제가 있다. 현재 1번 방법으로 원래 색깔이 \(c\)인 간선 \((u, v)..
PS 문제 풀이 [2021.8]
JAG Practice Contest 2020 D. Surround the Castle 성을 둘러싸는 것은 격자에서 상하좌우로 이동하며 사이클을 만드는 것으로 볼 수 있으므로, 성을 둘러싸는 최단 경로를 찾는 방식으로 접근합니다. 성을 둘러싸는 경로만을 생각해야 하는데, 이는 성에서 반직선을 하나 그어 그 선을 홀수 번 지나는 경로만을 생각하면 됩니다. (반직선을 그어 다각형 내부에 있는지 판별하는 것과 비슷한 방식) 그러므로 반직선을 홀수 번 지난 상태와 짝수 번 지난 상태를 구별하여 다익스트라를 돌리면 문제를 해결할 수 있습니다. 다익스트라의 시작점을 잡아야 하는데, \(R\)의 범위가 작으므로 성의 위쪽이나 아래쪽을 전부 해보면 됩니다. BOI 2021 A. A Difficult(y) Choice ..
Innopolis Open, Second elimination round, 2018-2019 D. Game of Wizards 일단 마지막에 남은 포션의 개수는 생각하지 않고 누가 이기는지만 구해봅시다. 상대의 포션을 없앨 때, 상대의 포션 중 가장 왼쪽에 있지 않은 포션을 없애는 것은 다음 상대의 턴에 영향을 주지 않으므로 나중에 없애도 됩니다. 그러므로 가장 왼쪽부터 몇 개의 포션을 없애는지만 생각합니다. 다음과 같은 DP 식을 정의합니다: (플레이어는 편의상 선공을 \(0\), 후공을 \(1\)이라 하겠습니다.) \(D[p][q][x][y][t]\) = 선공이 남은 포션의 개수가 \(p\), 후공이 남은 포션의 개수가 \(q\), 선공이 남은 마나가 \(x\), 후공이 남은 마나가 \(y\), 현재..
처음으로 블로그를 만들어 봤다. 무엇을 적어야할지 잘 모르겠어서 일단 재밌었던 문제의 풀이를 몇 개 적어봤다. PPC 2018 F. Edge Coloring 그래프가 트리일 경우를 생각해 봅시다. 트리의 리프에서부터 루트 아래까지 올라가며 부모 정점으로 가는 간선을 색칠할 때 리프일 경우, 무조건 색칠 리프도 루트도 아닐 경우, 자식으로 가는 간선 중 색칠된 간선이 짝수일 경우 색칠 이러한 방식으로 각 간선의 색칠 여부를 유일하게 결정할 수 있습니다. 색칠 후에 루트 정점의 차수는 짝수일 수도 홀수일 수도 있는데, 모든 정점의 차수 합은 항상 짝수이므로 \(n\)이 짝수일 때 루트 정점의 차수는 홀수가 됩니다. 그러므로 그래프가 트리일 때는 \(n\)이 짝수면 \(1\), 홀수면 \(0\)이 답이 됩니다..