RUN@KAIST 8/6 방학 연습 풀이

1. The Postman

경로에 대한 조건이 없을 때 이 문제는 방향 그래프에서 오일러 회로를 찾는 잘 알려진 문제이다. 오일러 회로는 모든 정점의 indegree와 outdegree가 같으며, 연결되어 있는 그래프라면 항상 존재한다. 이 문제의 그래프가 그러함을 가정하자 (그렇지 않다면 NIE).

오일러 회로는 다음과 같은 재귀 함수 Rec(v) 로 선형 시간에 찾을 수 있다. 오일러 회로에 대해서는 복습을 위해 알고리즘만 간략히 적어두고 설명하지는 않겠다. 

* 정점 v에서 나가는 에지 e를 아무거나 찾고 제거 (사용한 에지들의 인덱스를 전역 변수 등에다 마킹해 놓고, vector에서 pop_back() 하면서 에지를 지워주자) 

* e의 반대편 끝점이 w라면, Rec(w) 호출 

* Rec(w)가 종료되면 때 w를 리스트의 맨 앞에 넣음

이 문제에서는 그냥 오일러 회로를 찾는 것이 아니라, 어떠한 경로를 부분 경로로 포함하고 있는 오일러 회로를 찾아야 한다. 경로가 E1 -> E2 -> E3 -> E4 와 같은 에지들의 체인이라면, 우리는 E1 - E2 - E3 - E4 전체를 "녹여서", 대신 E1의 시작점에서 E4의 끝점을 잇는 다른 에지를 생각해 볼 수 있다. E3 -> E4 -> E5 -> E6같은 식으로 이어야 하는 경로들이 겹친다면, E1 - E2 - E3 - E4 - E5 - E6 전체에 대해서 이를 녹여줘야 할 것이다. 이런 식으로 에지를 녹여주는 것은 그래프의 연결성에는 영향을 줄 수 있지만, indegree와 outdegree에는 아무 영향을 주지 않는다. 고로 녹여준 이후의 그래프는 일반적인 알고리즘으로 오일러 경로를 구하기만 하면 된다.

에지를 "녹여주는" 개념이 아직 모호하고 복잡한데, E1 - E2 - E3 - E4 전체를 녹인다고 생각할 필요가 없이, E1 - E2를 녹이고, E2 - E3을 녹이고, E3 - E4를 녹인다고 따로 따로 생각해 주면 경로가 겹치는 등의 문제에 대해서 고민할 필요 없이 절차를 단순화시킬 수 있다. 이렇게 되었을 때 최종적으로 우리가 고려해야 할 것은 다음과 같은 두 가지 뿐이다.

* E_i 에지를 사용하기 직전에 E_{i-1} 에지를 사용해야 한다 

* E_i 에지를 사용한 직후에 E_{i+1} 에지를 사용해야 한다

이러한 조건을 저장하기 위해서, 각각의 에지에 대해서 prev[], next[] 와 같은 테이블을 가지고, 에지 E를 사용하기 직전 / 직후에 사용해야 하는 에지들을 관리한다. 그렇게 사용해야 하는 에지들이 두 개 이상이면 모순이니 NIE를 찍어줘야 한다. 

1번 정점에서 처음 시작하는 에지를 E라고 하면, E를 사용하기 직전에 사용해야 하는 에지 (prev[E]) 는 없어야 한다. 그렇지 않다면, E를 시작으로 해서 오일러 회로를 찾아보자. 오일러 투어를 돌릴 때 정점 기준이 아니라 간선 기준으로 돌리는 것이 편하다. 만약에 해당 간선 다음에 무조건 사용해야 하는 간선이 존재한다면, 해당 간선을 사용하고, 그러한 것이 없다면 일반적인 오일러 회로처럼 끝점에 연결된 간선들을 제거하면서 해결한다. 

최종적으로 오일러 회로 알고리즘이 모든 에지를 방문했다는 것은 그래프가 연결되었다는 것을 뜻한다. 그렇지 않다면 NIE를 찍고, 그렇다면 찾아낸 오일러 회로가 올바르니 그것을 찍으면 된다. 

2. Conspiracy

준비중

3. 일차원 세포 자동차

7월 20일 연습 Cellular Automaton 문제의 열화판이다. (해당 문제 풀이) 문제 자체에 어떠한 것을 구해야 하는지는 나와 있고, 이를 시간 안에 구하는 것이 목표이다. 

D[i][j][k] = (S(0, j)가 S(i, k)에 몇 배 곱해져서 더해지는가) 와 같은 동적 계획법 상태를 생각해보면 O(T * N^3) 에 문제를 해결할 수 있지만, i번 상태에서 i+1번 상태로 가는 것만이 아니라 i번 상태에서 2*i번 상태로 가는 전이까지 생각해 주면 이는 O(lgT * N^3)으로 줄일 수 있다. 자세한 것은 7월 20일 풀이의 앞 세 문단에 나와있으니 긴 설명을 생략한다.

여담으로, Cellular Automaton의 O(lgM * N^3) 해법이 그렇듯이, 이 해법도 행렬의 지수승으로 생각할 수 있다. 기본적으로 위 동적 계획법의 계산은 A[i][i] = B, A[i-1][i] = A, A[i+1][i] = C가 저장되어 있는 행렬의 T승을 취하는 것과 동일하다. 어떠한 수의 N제곱을 lgN에 계산하는 것과 똑같은 방식으로 행렬의 T제곱을 lgT에 계산하면 그게 결국 D[T][*][*]를 계산한 것과 동일하기 때문에 문제를 해결할 수 있다.

4. 잘못된 계산

f(0) ... f(d+2) 까지 수가 주어졌을 때, 틀린 것이 없다고 가정하고, 이것을 d차 이하의 다항식으로 표현할 수 있는가? 를 판별하는 문제를 풀어보자. 나코더 2016 모의고사에 나온 큐브러버가 이와 매우 비슷한 문제이다.

f1(x) = f(x+1) - f(x) 라고 하자. f(0) ... f(d+2) 가 d차 이하 다항식인 것과, f1(0) ... f1(d+1)이 (d-1)차 이하 다항식인 것은 필요충분 관계임을 알 수 있다. 이를 계속하면, fd(0), fd(1), fd(2)가 0차 (상수) 함수여야 하고, 최종적으로 f_{d+1}(0) = f_{d+1}(1) = 0 인 것과 f(0) ... f(d+2)가 d차 이하 다항식인 것이 필요충분이라는 결론이 나온다. 

여기서 중요한 사실을 찾아야 하는데, f_{d+1}(0)은 f(0) - f(1) * (d+1) + f(2) * (d+1)C2 - f(3) * (d+1)C3 + .... + (-1)^(d+1) * f(d+1) * (d+1)C(d+1) 과 같은 식으로 표현이 된다. 만약에 틀린 수를 x라고 가정한다면, x != d+2일 때 f(x)에 정정해야 할 옳은 값이 유일하게 결정된다는 것을 뜻한다. 

고로, x = 0 -> d+1까지 가능한 모든 경우를 다 따진 후, 단순 수식 계산으로 정정해야 할 값을 찾아주면, 똑같은 계산을 다시 반복해서 f_{d+1}(0) = f_{d+1}(1) = 0 인지 판별하면, x가 정정해야 할 수인지 아닌지를 알 수 있다. 이 중 가능한 경우가 없다면 답은 d+2이다. 오차가 심하게 나니 long double을 사용하고 epsilon 값을 여유롭게 설정하자. (문제 제한이 관대해서 epsilon만 크게 주면 문제 될 일은 거의 없다.)