집나간 PS실력을 살리기 위해 앳코더 문제를 풀어보려고 한다. 일단 제일 어려운 것만...
(실제로는 저대로 안 썼습니다. 스샷 다시 찍기 귀찮아서)
이 스크립트가 제대로 작동하는 가장 옛날 라운드인 ARC035부터 돌기로 했다. (그전에는 _4 로 suffix를 붙인듯)
+ Grand Contest F를 추가했다. 진짜 다 풀 수 있을까 (...)
+ (2018.01.17 : 오랫동안 동결된 걸 보고 역시 현실성이 없다는 걸 깨달았습니다 (...) 문제를 쓰는 것 뿐만 아니라 제대로 된 풀이까지 써야 해서 더 부담이 됐던 것 같습니다. 번역이 안 된 ARC를 제외하고는 전부 리스트에서 삭제했습니다. 여기 있는 ARC 정도만 클리어하는 걸 목표로 하겠습니다. 여기 원래 적혀있던 ARC074D / ARC075D 풀이는 나중에 개별 글로 쓰겠습니다.)
문제 해석이 안 돼서 힘들었는데, 결국은 두 점이 주어졌을 때 이 두 점 간을 잇는 최단 거리의 경우의 수가 큰 쪽이 어디인지를 판별하는 문제이다. 큰 쪽의 답이 작은 쪽의 두배라는 이상한 조건이 붙어있다.
쿼리 형태로 빠르게 처리해야 하는데 설명하기 귀찮으니 일단 없다 치자. S - E를 잇는 경우의 수는 S - S+1 을 잇는 경우의 수 * S+1 - S+2를 잇는 경우의 수 * ... * E-1 - E를 잇는 경우의 수 니까, 곱을 계산해서 빠르게 비교하면 될 것이다. 각각의 경우의 수는 이항계수로 나오는데 사실 직접 계산해서 비교하기에는 너무 큰 값이다.
그래서 경우의 수에 로그를 취한 값을 계산하고, 로그가 큰 쪽을 판별하는 식으로 생각해보면, 그 이상한 조건이 결국은 eps = log(2) 였다는 것을 알 수 있다. eps가 크니까 대충 하면 된다. 이항 계수는 팩토리얼 / 팩토리얼 * 팩토리얼 이니까 lg(n!) 을 전처리 해놓으면 O(1)이고 곱셈은 합이 되니까 구간 합을 계산하면 된다. 쿼리 문제고 갱신이 들어온다는 점은, 구간 합 계산과 갱신을 BIT와 같은 자료 구조로 하면 된다. 노잼 문제.
또 쉬운 문제. 결국 각각의 간선은 parity를 바꿔주는 역할만을 한다는 것을 알 수 있다. 그래서 시작점과 끝점을 같은 parity로 도달할 수 있는지를 확인하면 된다.
각각의 정점을 홀수 i / 짝수 i 로 분할하자. 간선을 추가할 때 union find를 써서, 간선 코스트가 홀수면 홀수 - 짝수 / 짝수 - 홀수 를 묶어주고, 아니면 짝수 - 짝수 / 홀수 - 홀수 를 묶어준다. 이제 쿼리가 들어왔을 때 짝수 s와 짝수 e가 도달 가능하면 짝수 경로가 있는 것이다.
필요에 따라서 점화식을 설계하다 보면 풀리는 문제였다. 저게 잘 안 되서 옛날에 했을 때는 막혔는데 다시 하니까 잘 되더라.
답을 A_i라고 하면, 중간에 있는 큰 삼각형을 포함하지 않거나 (3A_i) 포함하는 형태로 부분문제가 정의된다. 포함하는 형태의 경우를 셀 때, 큰 삼각형의 꼭짓점을 다각형이 무조건 지날 것이기 때문에, 밑변이 닿아 있는 형태의 답인 B_i를 정의해보면 A_i = 3A_{i-1} + B_{i-1} ^ 3이 된다.
B_i를 정의할 때 역시 비슷한 식으로 부분 문제를 정의한다. 그러면 맨 위 꼭짓점의 작은 삼각형을 포함하며 밑변이 닿아 있는 형태의 답인 C_i를 정의해야 할 것이다. C_i를 정의하면 셋 간의 점화관계로 문제를 해결할 수 있다.
Player 1이 내는 답이 X 이상인지를 판별하는 문제를 풀어내면, 이진 탐색으로 답을 구할 수 있다. 고로 문제를 "Player 1이 X 이상의 정점에서 게임을 멈출 수 있는지"로 바꿔보자. 이 때 값이 X 이상인 정점을 1, 아닌 정점을 0이라고 하면, Player 1이 1 정점에 오거나 Player 2가 0 정점에 오면 게임이 끝나며, 시작 정점이 X 이상이면 자명하게 Player 1이 이긴다.
이제 시작 정점이 0이라고 가정하자. Player 1이 0 정점에 있는데, 다음 턴을 0 정점으로 주는 건 게임을 포기하는 것이나 다름 없다 (그런 실수를 하면 Player 2가 게임을 끝내 버리면 되니까). 이 논리는 Player 2에 대해서도 똑같고, 고로 0 -> 0 내지는 1 -> 1 정점을 잇는 에지들은 없는 에지라고 생각해도 된다. 또한, 0 정점은 Player 1만이 방문하고, 1 정점은 Player 2만이 방문한다는 것도 알 수 있다.
또한, 만약에 path가 무한히 반복되면, 10^9번째 (즉 짝수번째) 에서 Player 1은 0 정점에 서 있게 된다. 고로 사이클을 만나게 되면 Player 2가 이긴다. 이제 10^9라는 숫자도 필요없다. 여기까지 알면 사이클에 들어가면 (= N개 이상의 정점)을 방문하면 게임이 끝난다는 거니까 이걸로 DP를 돌려서 O(NMlgX) 에 문제를 해결할 수 있다. 30점의 점수를 얻을 수 있으며, 만점을 받으려면 변형된 문제를 선형 시간에 풀어야 한다.
SCC로 그래프를 묶어 보자. DAG 상에서 outdegree가 없는 컴포넌트에 들어가면, 만약 컴포넌트의 크기가 2 이상일 때 Player 2가 뺑뺑이를 항상 돌릴 수 있기 때문에 무조건 Player 2가 이긴다. 컴포넌트의 크기가 1이라면 상태에 따라서 승자가 결정된다. 어쨌든, 이 정점들에 대해서는 누가 승리하는지가 결정된다. 이 관찰을 outdegree가 있는 컴포넌트에 확장시켜야 한다.
위상 정렬 순서대로 각 SCC 컴포넌트를 처리하자. 현재 컴포넌트와 연결된 다른 컴포넌트들은 이미 처리를 했으니 승패가 확정되어 있다. 그 연결된 컴포넌트와 직접 연결된 일부 정점들은, 그 정보들을 사용해서 승패를 결정할 수도 있다. 이 정점들의 승패가 결정되면, 이는 또 다른 정점들의 승패를 결정할 수 있고... 이런 식으로 계속 승패 결과가 컴포넌트에 전파되게 된다.
이를 queue로 구현하면 몇개의 정점들은 승패 결과가 확정되게 된다. 하지만, 꼭 모든 정점들의 승패 결과가 이것으로 확정되는 것은 아닌데, 그 경우에는 이 정점들은 사이클에 들어갈 수 밖에 없게 되고, 고로 Player 2가 이긴다. 고로 컴포넌트의 모든 정점들을 위상정렬 역순으로 해결하면 모든 정점의 승패를 확인할 수 있어서 선형 시간에 결정 문제를 해결할 수 있다.
전파가 안 된 정점에서 Player 2가 이긴다는 점은 inductive하게 생각하면 이해할 수 있다. 처음 컴포넌트에서 승패를 아는 정점은 없다. 하지만 이 컴포넌트와 연결된 이미 처리된 컴포넌트들을 통해서, 연결된 정점의 승패를 몇 개 알 수 있게 된다. 승패가 확실한 정점을 찾았다는 것은, 이 정점을 컴포넌트 밖으로 빼도 승패 결과가 똑같다는 것을 뜻한다. 컴포넌트 밖으로 정점을 빼지 못하는 순간은, 연결된 정점에서 승패를 추론할 수 없다는 것이다. (큐가 비는 상황이다.) 이는 outdegree가 없는 컴포넌트의 상황으로 현재 컴포넌트를 변형했다는 것을 뜻하며, 이 상황에서 Player 2가 이기는 것을 우리는 알고 있다.
여기서 난 생각을 끝내고 SCC를 직접 구현했는데, 혜아는 SCC를 구현하지 않고 단순 위상 정렬로 풀었다. 단순 위상 정렬로 풀기 위해서는 다음과 같은 아이디어가 필요하다. outdegree가 0인 정점들은 승패를 확실히 추론할 수 있는데, 이 정점들만 queue에 넣고 승패를 체크한 후, 승패가 체크되지 않은 정점들은 모두 Player 2가 이긴다고 가정해도 무방하다는 점이다. proof left as an exercise..
dfs로 절선을 다 구해놓고, 절선이 아닌 간선으로 연결된 애들은 같은 컴포넌트로 묶어준다. (edge bcc) 이 경우에 절선을 에지로 하는 트리를 얻을 수 있다.
쿼리마다 세개의 정점이 들어오는데, 이 정점을 새로운 트리의 정점으로 매핑하자. 만약에 A - B를 잇는 path 안에 C 정점이 있으면 문제에 주어진 투어가 가능하고, 그렇지 않으면 안 되는 걸 관찰할 수 있다. path 안에 정점이 있다는 것은 dist(A, C) + dist(C, B) = dist(A, B) 와 필요충분이다. 고로 거리를 빠르게 구할 수 있으면 충분하고, 이는 LCA sparse table로 O(qlgn)에 알 수 있다.
이상한 문제. 일단 B - A가 적당히 작으면 루프를 돌리고, B - A가 크면 랜덤이니 답이 작을 가능성이 높다. 고로 X^i == Ans인 i가 존재하는 지를 빠르게 판별하고 적당히 다 돌려보는 방법을 시도해 보자. 이는 meet in the middle류의 방법으로 해결할 수 있는데, 먼저 버킷 문제 풀듯이 A와 B+1을 65536의 배수로 설정한 후, 집합 1 = {X^0, X^1 ... X^65535}, 집합 2 = {X^((A >>16) << 16), X^(((A + 1) >> 16) << 16) ... X^((B >> 16) << 16)} 로 하면, 양 집합에서 곱이 Ans인 답이 있는지를 판별하는 문제가 있다. B = Ans * A^(P-2) 니까, 집합 2를 쭉 돌면서 그러한 B가 존재하는 지를 이진 탐색으로 대충 찾으면 연산 100만번 언저리에서 이를 판별할 수 있다. 이걸 대충 짜서 넣으면 맞는다.
여담으로 저런 식으로 X^i == Ans 식을 해결하는 테크닉을 Baby step giant step algorithm이라고 한다.
2N개의 점이 매칭을 이루는 지 판별하는 문제를 먼저 풀어보자. 내 접근은 다른 사람들과 좀 다른 것 같았는데 나름대로 괜찮은 아이디어를 가지고 있는 것 같아서 기분이 좋았다.
핵심적인 아이디어는, 점을 간선으로 생각하는 것이다. 2N+1개의 X / Y좌표를 각각 이분 그래프의 양 정점으로 두고, (Xi, Yi) 점이 있을 때 Xi와 Yi를 간선으로 이어준다. 매칭을 이루는 것을 판별하기 때문에 직관적으로 봤을 때 이러한 접근은 문제를 복잡하게 만들 뿐이지만, 의외로 이를 통해서 매칭인지 아닌지를 꽤 쉽게 판별할 수 있다.
앞서 정의한 점 간의 매칭은 이제 간선 간의 길이 2의 경로로 볼 수 있다. 그 때 매칭이 있다는 것은, 각 컴포넌트에 홀수 degree의 정점이, X 사이드에 짝수개, Y 사이드에 짝수 개 있음을 뜻한다. 증명은 다음과 같다 :
* 모든 정점의 차수가 짝수일 때는 항상 답을 찾을 수 있다. X좌표 정점에서 연결된 정점 두개를 아무렇게나 묶으면 되니까.
* X 사이드에 짝수 개의 홀수 정점이 있다는 것은 Y 사이드에도 짝수 개의 홀수 정점이 있다는 것을 뜻한다. X 사이드에 2K개의 홀수 정점이 있다면, 2i번째 홀수 정점과 2i+1번째 홀수 정점을 잇는 경로를 아무렇게나 그려준다. 만약 이 경로들이 겹치지 않는다면 이 경로를 따라서 매칭을 시키면 나머지 경우는 모든 정점의 차수가 짝수가 된다. 겹친다면, xor을 하듯이 짝수 번 선택된 간선을 선택 안했다고 친다면, 겹치지 않는 경로로 성공적으로 환원시킬 수 있다. 비슷한 문제가 여기 있다.
* 이 외의 경우는 X 사이드에 홀수 개의 홀수 정점이 있다는 것을 뜻한다. 매칭은 같은 사이드만을 잇기 때문에, 각 사이드의 degree 합은 무조건 짝수여야 한다. 고로 답이 존재할 수 없다.
이는 간단한 O(N^2) 풀이로 환원되며, 이를 O(N)으로 줄이는 것 역시 어렵지 않다. 적당한 전처리를 한 후 해당 간선이 단절선인지 아닌지에 따라서 case를 나누면 해당 간선을 지웠을 때의 매칭이 존재하는 지를 O(1)에 판별할 수 있게끔 해준다. 이 부분에 대한 자세한 디테일은 생략한다. 고로 O(N)에 해결 가능
