JOI Spring Camp 2016 풀이

JOI Spring Camp 2016 풀이

Available on AtCoder.

Day 1

Matryoshka

지름 Ri, 높이 Hi인 마트료시카 안에는 지름과 높이가 둘 다 작은 마트료시카를 최대 한 개 넣을 수 있다. 그리고 이것이 중첩이 가능하다. 다른 마트료시카에 들어가지 않는 마트료시카를 바깥 마트료시카라고 하자.

어떠한 마트료시카들의 집합이 있을 때, 여기서의 바깥 마트료시카의 최소 갯수를 구하는 방법에 대해 생각해보자. 잘 생각해보면, 바깥 마트료시카의 갯수가 많아지는 이유는 마트료시카들이 같은 마트료시카에 들어가지 못해서이다. 즉, 마트료시카 중 몇 개를 선택하여 그 집합을 S라고 할 때, S에 속하는 마트료시카들이 모두 서로 포함할 수 없다면, 이들은 모두 서로 다른 바깥 마트료시카에 들어가야 할 것이기 때문에, 바깥 마트료시카의 갯수는 반드시 |S|보다 크거나 같아야 할 것이다.

그런데, 바깥 마트료시카의 갯수는 사실은 정확히 max{|S|}이다. Dilworth's Theorem이 그것이다. 즉, 어떤 마트료시카들을 감싸는 데에 필요한 바깥 마트료시카의 수는, 서로 포함할 수 없는 마트료시카들의 최대 수와 같다. 마트료시카들이 서로 포함하지 않으려면, Ri가 증가하는 순으로 정렬했을 때, Hi는 증가할 수 없기 때문에 항상 감소할 것이다. 즉 그러한 집합 S는 마트료시카들의 긴 chain으로 생각할 수 있다. 마트료시카들을 (Ri, Hi)로 생각하여 평면 상의 점으로 나타내면, 어떤 마트료시카에 대해 왼쪽 윗 점이 (Ri, Hi)이고 너비와 높이가 무한한 직사각형의 점들로 이어질 수 있고, 그중 길이가 가장 긴 것으로 이어지면 될 것이다.

따라서 점들을 x좌표 순으로 정렬하고 오른쪽에서 왼쪽으로 sweeping을 하면서, y축 방향의 트리 자료구조를 사용하여 DP를 할 수 있다. 쿼리 또한 평면 상의 직사각형으로 나타날 것인데, 잘 생각해보면 그 직사각형의 점들 중 DP값이 가장 큰 것을 찾으면 된다. 따라서 쿼리마다 online으로 2차원 평면 상의 직사각형에 대한 range maximum이 가능한 자료구조를 사용할 수도 있다. 혹은 쿼리를 점들과 함께 정렬한 후 sweeping할 때 동시에 처리해주면 1차원 자료구조로도 풀 수 있다.

Memory 2

하나의 카드 i를 고정시키고, 나머지의 모든 카드 j를 훑어보며 각각 Flip(i, j)를 호출한다고 생각해보자. 이 때, 홀수 번 등장하는 값이 딱 하나 있을 것이고, 나머지 값들은 모두 정확히 한 쌍으로 등장할 것이다. 한 쌍으로 등장하는 값들은 $P$의 순서에서 $A_{i}$보다 앞쪽에 있는 아이들일 것이고, 그 값은 각각의 카드에 쓰여 있는 값과 같을 것이다. 그리고 홀수 번 등장한 값이 $A_{i}$일 것이다. 이렇게 $N^{2}$번의 호출을 하면 Subtask 1을 풀 수 있다.

홀수 번 등장한 값들 중에는 $A_{i}$도 있겠지만 그보다 $P$의 순서가 큰 값들도 있을 것이다. 그것들의 카드 번호가 각각 무엇인지도 알아야 할 것이다. 그럼 거기서도 또 기준을 잡고 나머지를 다 해보면? 그런데 처음에 잡은 $A_{i}$가 $P$의 순서에서 가장 작은 값이었다면, 원소가 하나밖에 안 줄어들고, 새로운 원소를 잡아서 나머지 원소들을 모두 Flip()해보아야 한다. 즉 이러한 방향으로는 $O(N^{2})$에서 벗어나기 힘들다. 그런데 이 방향으로 생각을 하다 보면 최종적으로는 $P$의 순서가 가장 큰 값을 찾는 것이 중요해진다. 그 방법을 고민해보자.

$P$의 순서에 있어 '크다'라는 것은, 어떤 두 원소만 가지고는 알 수가 없다. 그들의 Flip()값은 딱히 도움이 되지 않는다. 크기를 비교하려면 적어도 세 개의 원소를 사용해야 한다. 세 개의 원소간에 모두 Flip()을 호출하여 결과를 알고 있다면, 다른 원소들보다 $P$의 순서가 확실히 낮은 원소를, 만약 존재한다면 찾을 수 있다. 그런데 만약에 셋 중 두 개는 $P$가 가장 큰 원소이고, 나머지 하나는 두 번째로 큰 원소라면? 이 경우에는 셋 간의 크기 관계를 알 수가 없다. 만약에 네 개 이상의 원소가 있다면, 그중에는 항상 순서가 확실히 낮은 원소가 있다.

즉 원소들을 쭉 훑으며 $P$가 큰 것들을 유지하고 있다면, 유지하고 있는 집합의 크기는 항상 3 이하라는 결론을 내릴 수 있다. 새로운 원소를 보았을 때, 원래 집합의 모든 원소와 Flip()을 호출하여 크기 관계를 판단하고, 최댓값이 될 수 없는 원소는 없애버리자. 모든 원소를 훑고 나면, 두 번째로 큰 원소는 분명히 두 번 나왔을 것이고, 그러면 가장 큰 원소보다는 확실히 $P$에서 작기 때문에 없어졌을 것이다. 즉 마지막에 남아있는 두 개의 원소는 분명 $(N-1)$이 쓰여있다.

이 과정을 구현하면서, $P_{i}=i$인 점(이러면 세 개 짜리 집합에서도 P가 가장 작은 것을 찾아 없앨 수 있다!)과 호출 횟수가 약간 더 넉넉한 점을 이용하여 편하게 코딩을 하면 Subtask 2를 풀 수 있다. 조금 더 신경써서 구현하면 Subtask 3을 풀 수 있다.

Solitaire

우선 모든 칸들을 채우는 것이 불가능한 경우에 대해 고민해보자. 1행 혹은 3행의 비어있는 칸들은, 반드시 좌우의 칸이 채워져 있는 상태가 되고 난 후 채워야 한다. 즉 양옆의 칸이 채워지는 것에 의존하고 있는 셈이다. 그런데 만약 그 칸이 1열 혹은 $N$열이라면, 양쪽의 칸이 모두 채워지는 것은 영영 불가능하다. 그렇지 않더라도, 만약에 그 칸도 나에게 의존하고 있다면? 의존관계의 loop가 생겨 영영 불가능하다. 즉 네 귀퉁이의 칸들 중 하나라도 비어있거나, 좌우로 2개 이상 연속한 빈칸이 있는 경우에는 불가능하고, 나머지 경우는 항상 가능하다.

이제부터 비어있는 칸에 집중하자. 비어있는 칸을 '점' 등으로 지칭할 것이다. 비어있는 칸을 채움에 있어, 그 칸에 영향을 주는 것들은 상하좌우의 칸들이다. 빈칸을 통해 상하좌우로 연결되어 있지 않은 칸들은 서로 아무런 상관이 없다는 것이다. 즉 빈칸들이 상하좌우로 붙어있는 덩어리들이 있을 텐데, 그 덩어리들 각각에 대해서 답을 구한 다음에 잘 합칠 수 있다.

합친다는게 무슨 말일까? 쉽게 생각해서, 두 개의 덩어리가 있다고 하자. 한 덩어리에는 A개, 다른 덩어리에서는 B개의 칸이 있다고 하자. 그러면 최종적으로 두 덩어리를 모두 채우는 방법은, 총 (A+B)개의 칸을 채워야 할 것이다. 그중에는 앞쪽 덩어리의 칸들을 채우는 것이 있고, 뒤쪽 덩어리의 칸들을 채우는 것이 있을 것이다. 그런데 앞쪽 덩어리의 칸들을 채우는 것들끼리는 순서관계가 있고, 뒤쪽도 마찬가지이지만, 서로 어떤 순서로 오는가는 상관이 없다. 즉 앞쪽 덩어리의 칸들을 채우는 것을 배정하는 방법이 $\binom {A+B} {A}$가지가 있고, 나머지는 자연히 B개의 칸들로 채워진다. 그리고 각각의 방법에 대해서 앞쪽 덩어리 내부적으로 나올 수 있는 방법의 수와 뒤쪽의 방법의 수만큼의 방법이 있으므로 이 값들을 곱하면 된다. 일반화해보면, 각각 크기가 $c_{1}, c_{2}, \cdots, c_{k}$인 $k$개의 덩어리가 있을 때, 이들을 배치하는 방법의 수는 $\binom{c_{1}+\cdots+c_{k}}{c_{1}} \cdot \binom{c_{2}+\cdots+c_{k}}{c_{2}} \cdots \binom{c_{k}}{c_{k}}$가지이다. 여기에 각각의 덩어리 내부에서 나오는 방법의 수를 곱해주면 최종적인 답이 된다.

한 덩어리 내부의 경우의 수는 어떻게 구할까? 덩어리 중에, 2행에 점이 없는 덩어리는 반드시 1행 혹은 3행에서 가로로 연속해 있어야 하고, 처음에 체크해줬다면 이러한 덩어리는 분명 딱 한 개의 점만 포함하고 있을 것이다. 이런 것들은 무시하고, 2행에 점이 있는 덩어리들을 생각해보자. 이 덩어리들은 또다시 생각해보면, l열부터 r열까지의 모든 열에 대해서 2행에 점이 있고, 나머지 열에는 점이 하나도 없을 것이다. 그리고 l열부터 r열까지의 열들 중 1행과 3행에 군데군데 점들이 박혀있을 것이다. 1행과 3행의 빈 칸은 양쪽이 반드시 채워져 있을 것이므로 아무 때나 채울 수 있어야 한다. 2행의 빈칸은 연속한 빈칸으로, 여기서 순서의 의존 관계가 생길 것이다. 채우는 순서 등을 고려하다 보면 여러 가지 복잡한 생각이 들기 때문에, DP의 아이디어를 믿고 l열부터 차근차근 가보자.

DP를 하려면 부분문제가 정의되어야 할 것이기 때문에, 점들이 k열까지만 있다고 보고, (k-1)열까지 있는 점들을 배열하는 방법의 수에 잘 끼워넣어 생각해보자. (k-1)열까지의 점들을 valid하게 배치하는 어떤 방법이 나열되어있다고 해보자. 그 길이는 거기까지의 덩어리의 크기일 것이다(열의 갯수가 아니다!). 이제 여기에 k열의 점들(2행에는 반드시 점이 있고, 입력 데이터에 따라 1행이나 3행 혹은 둘 다에 점이 있을 것이다)을 각각 원하는 위치에 끼워넣을 것이다. 지금 우리가 하는 DP는, k열의 위아래의 점이 모두 채워져서 k열의 2행에 점을 채우는 것도 세어줄 수 있어야 하지만, (k-1)열과 (k+1)열의 2행의 점들을 채운 후 k열의 점을 채우는 방법도 세어줄 수 있어야 한다는 것이다. 그 때는 k열이 양쪽의 열에 '의존'하므로 '의존'이라는 단어를 쓰도록 하겠다.

• k열이 주변의 열에 의존하는 방법을 세어줄 때는, k열의 2행보다 먼저 이전에 (k-1)열의 2행의 점의 뒤쪽에 k열의 2행의 점이 들어가도록 강제해야 한다.
• 만약 지금 보고 있는 (k-1)열까지 채우는 방법에서, (k-1)열의 2행의 점을 채울 때도, 'k열의 점이 알아서 내 앞에 들어와서 나보다 먼저 채워주겠지?'라고 생각하고 채웠다면, 또다시 의존관계의 loop가 생긴다. 즉 k열 2행의 점을 (k-1) 및 (k+1)번째 열의 2행의 점들에 의존하도록 채운다면, 그 때의 (k-1)열은 의존하도록 채운 것이 아니어야 하고, (k+1)열에서는 이 방법들은 k열이 자신에게 의존하고 있음을 알 수 있어야 한다.
• 의존하는 점을 채우는 과정에서, 앞 열의 2행의 점을 채운 위치가 어디인가가 중요해진다.
• 의존하지 않도록 채우는 것은 어떤 것인가를 고민해보면, 반드시 위와 아래의 점들을 모두 채운 뒤에 현재의 점을 채워야 한다.
• 또한, (k-1)열이 k열에 의존하게 채웠다면, k열의 점은 반드시 의존하지 않는 방법으로 채워야 한다.

위의 것들을 고려해보면 DP식을 다음과 같이 정의하는 것을 생각해볼 수 있다.

dp[i][j][k]=i번째 열이 속하는 덩어리에서, i번째 열까지의 덩어리를 채웠고, i열 2행이 j번째로 채워졌으며, i열 2행의 점이 주변 점들에 의존하는지의 여부가 k(0 혹은 1)가 되도록 채우는 방법의 수

뭔가 굉장히 어려운데, 점화 과정을 고민해보자. 항상 dp[i-1]에서 dp[i]로 점화식이 진행될 것이다. i열의 빈칸의 갯수를 cc, i-1열까지의 현재 덩어리의 빈칸의 갯수를 cnt라고 하자.

dp[i][j][0]에 dp[i-1][k][0]이 합해지는 것을 생각해보자. 0번을 보고 있으므로, i열은 주변에 의존하지 않는다. 즉 i열 2행의 앞에 i열 1행과 3행이 존재해야 한다. 또한 i-1열도 i열에 의존하지 않으므로, i열 2행이 어디에 들어가든, k가 몇이든 상관이 없으나, i열 2행이 j번째에 들어가기로 정해놓은 상태이다. 그러면 이제 i열까지 보면 총 (cnt+cc)개의 빈칸을 채우는 순서를 생각해야 하는데, 그중 j번째가 i열 2행이고, 앞쪽에 (cc-1)개의 점이 자유로운 순서와 위치로 지정되며, 나머지 칸들에 dp[i-1][k][0]을 채울 수 있다. 그러면 다음과 같을 것이다.

$dp[i][j][0] += \sum dp[i-1][1 \cdots cnt][0] \cdot (cc-1)! \cdot \binom{j-1}{cc-1}$

dp[i][j][0]에 dp[i-1][k][1]이 합해지는 것을 생각해보자. 앞 열이 내게 의존하고 있기 때문에, (cnt+cc)개의 순서에서 고민해보면 이전에 k번째 점이었던 것은 j보다 오른쪽에 있어야 한다. 또한 j의 앞에는 반드시 (cc-1)개의 빈칸이 존재하기 때문에, 기존의 k는 뒤쪽으로 cc개만큼 밀려나서, (k+cc)의 위치에 있다. 그러면 j<k+cc인 k들이 가능하므로, 가능한 k들의 범위가 나온다. 앞쪽에 (cc-1)개의 점이 자유로운 위치와 순서로 지정되기 때문에, 위와 비슷하게 다음 식이 나온다.

$dp[i][j][0] += \sum dp[i-1][j-cc+1 \cdots cnt][1] \cdot (cc-1)! \cdot \binom{j-1}{cc-1}$

dp[i][j][1]에 dp[i-1][k][0]이 합해지는 것을 생각해보자. 내가 앞쪽 열에도 의존을 하고 있기 때문에, (cnt+cc)개의 순서에서 고민해보면 이전에 k번째 점이었던 것은 j보다 왼쪽에 있어야 한다. 만약 i열의 점들 중 j의 앞쪽에 t개의 점을 배치한다고 하면, j의 뒤쪽에는 (cc-1-t)개의 점이 있어야 하며 그 값은 0이 아니어야 한다. 그리고, j의 왼쪽에는 총 j-1-t개의 빈칸이 남는데, 이중 k가 반드시 있어야 하므로, 가능한 k의 범위는 1 이상 j-1-t 이하이다. 이렇게 앞쪽에서 t개의 점들을 선택하는 방법과, 뒤쪽에서 점들을 선택하는 방법, 그리고 이 (cc-1)개의 점들이 들어가는 순서에 따라서 다음과 같은 식이 나온다.

$dp[i][j][1] += \sum dp[i-1][1 \cdots j-1-t][0] \cdot (cc-1)! \cdot \binom{j-1}{t} \cdot \binom{cnt+cc-j}{cc-t-1}$

모든 t에 대해서 반복문을 돌려줄 수 있다. 어차피 t는 2 이하이기 때문이다. 그러면 모든 점화식이 상수 시간이고, 점화식의 축의 크기를 살펴보면 $N \cdot N \cdot 2$이기 때문에, 덩어리 별로 제곱의 시간이 들고, 덩어리의 총합이 $3N$ 이하이므로 모든 덩어리에 대하여 계산해도 $O(N^{2})$의 시간이 걸린다.

위의 세 개의 식 모두 가운데 축에 대한 prefix sum을 필요로 하는데, 이것을 각각의 DP 값을 순차적으로 구하면서 동시에 채워나가면 추가적인 시간 소요 없이 가능하다.

첫 열의 DP값을 잘 설정해준 후 이 과정을 진행하여 각 덩어리의 마지막 열에 대한 DP를 구했다면, 현재 덩어리의 답은 마지막 열의 DP값의 합일 것이다. 즉 현재 덩어리의 답은 $\sum dp[r][1 \cdots cnt][0 \cdots 1]$이다. 사실 이 부분이 비직관적이라 의문이 생길 수 있다. 마지막 열에서도 의존을 해버리면 안 되지 않는가? 경우를 나눠서 코딩해도 되지만, 이 경우에는 그러지 않아도 된다. 왜일까? 마지막 열의 오른쪽이 이미 채워져 있는 칸이라면, 의존을 하는 것이 확실히 가능하다. 따라서 이 식은 옳다. 마지막 열의 오른쪽이 오른쪽 끝 벽이라면, 처음의 조건에 의해 이 위와 아래는 무조건 차있을 것이고, 그러면 앞에서의 t가 존재할 수가 없으므로 dp[r][k][1]의 값은 항상 0이다. 따라서 상관이 없어서 옳다. (...) 이것은 꼭 필요한 내용은 아니고 나도 처음에는 조건을 판단해서 더하도록 짰었다.

아무튼 이렇게 덩어리 별 값을 구한 다음에 앞에서 설명한 대로 합하면 된다. 조심할 게 있는데, 열은 2,000개이지만 빈칸은 6,000개 가량이므로, 이항계수 테이블의 크기나 DP 테이블의 가운데 축 크기를 6,000 정도로 잡아야 한다.

Day 2

Employment

제일 오른쪽에 평가치가 0인 후보자가 있다고 하자. (나머지 모든 평가치는 1 이상이다.) 그러면 합격 커트라인이 B일 때 그룹의 수는, i번째 후보자의 평가치가 B 이상이고, i+1번째 후보자의 평가치가 B 미만인 i의 갯수와 같다. 그룹이 잘리는 위치가 모두 그 위치이기 때문이다. 그러면 역으로, i번째 후보자의 평가치 미만, i+1번째 후보자의 평가치 이상인 모든 B에 대해서, (i, i+1)의 쌍은 그 커트라인에 대해 그룹의 수를 하나 올려준다. 이것을 구간에 대한 갱신으로 생각할 수가 있으며, 커트라인 축의 세그먼트 트리를 만들어서 구간에 값을 더하고 빼면 된다. 참고로 각각의 커트라인에 대해서 값을 물어볼 때는 특정 원소의 값만 알면 되기 때문에, 구간 쿼리를 굳이 propagate해줄 필요가 없다.

Sandwich

각각의 샌드위치 중 위쪽 것을 먼저 빼기 위해서 빼야 하는 최소 갯수를 구한다고 해보자. 그러면 위쪽 샌드위치는 (순서 관계 때문에) 빗변을 통해서 뺄 수 없기 때문에, 직각을 낀 두 변을 통해서 빼야 한다. 각각의 변에 맞닿은 샌드위치가 있다고 했을 때, 그 샌드위치는 역시 (순서 관계 때문에) 직각을 낀 변으로 뺄 수 없기 때문에, 빗변의 샌드위치가 빠져야 한다. 그런데 그러면 그 샌드위치는 어찌됐건 그 격자 칸의 샌드위치가 둘 다 빠져야 할 것이다. 그러면, 어차피 위쪽 샌드위치를 빼면 아래쪽을 필연적으로 빼게 된다. (위쪽이 필요해서 뺐더라도 어차피 아래쪽을 뺄 것이고, 아래쪽이 필요해서 뺐으면 이미 빠져 있지 않겠는가.) 그러면 간단하게, 어떤 격자 칸을 뺀다고 생각을 하면 편하다.

아무튼 격자 칸들에서 계속 의존관계를 퍼뜨려줄 수가 있다. 이렇게 의존관계를 퍼뜨려주는 것을 각 점마다 해주면, DFS 등으로 탐색하는 데에 $O(RC)$, 그것을 행해야 하는 정점이 $RC$개이므로 $O(R^{2}C^{2})$의 시간이 걸린다. 하지만 아직 만점을 받기 위해서는 차수가 하나 더 줄어야 한다.

어떤 격자 칸에서 위쪽 것을 먼저 빼기 위한 의존 관계의 화살표를 시작한다면, 그 칸이 Z이면 위쪽과 왼쪽, N이면 위쪽과 오른쪽으로 퍼진다. 여기서 항상 위쪽 격자 칸에 의존관계가 들어간다는 것을 알 수 있다. 즉 i행 j열의 칸에서 의존관계를 타고 탐색을 수행한 visit 배열이 있다면, (i+1)행 j열의 칸에서는 거기에 추가로 생긴 의존관계에 의해 그 visit 배열에 몇 개가 더 추가될 것이다. 그러면 visit배열을 그대로 유지한 상태에서 다음 행으로 진행하는 식으로, 새로운 열을 시작할 때마다 visit을 초기화하는 식으로 하면 더 효율적이라는 생각이 든다. 전체의 탐색은 여전히 $O(RC)$가 걸리지만, 이것을 누적적으로 하면 $O(R)$번만 수행하면 되므로 $O(R^{2}C)$의 시간이 걸린다.

각각의 점에 대한 최종적인 답은 위쪽 것을 먼저 빼거나 아래쪽 것을 먼저 빼거나의 둘 중 하나일 것이다. 아래쪽 것을 빼는 것도 똑같이 구한 뒤, 둘 중 minimum을 찍어주면 될 것이다. 둘 다 불가능하면 -1일 것이다.

Toilet

Day 3

Dungeon 2

이 문제에서 이상한 방식으로 답을 출력하기를 요구한 것은, Graph Homomorphism 문제가 NP-complete이기 때문이다. 그래프 형태로 답을 찍으면 grader는 NP-complete 문제를 풀어야 하는 것이다. (...) 그래서 이런 방법을 쓰는 것이지, 문제 푸는 것과는 관계가 없다는 것을 깨달아야 한다. 안 그러면 스스로 함정에 빠지게 된다.

그래프에서 DFS를 해보자. DFS를 하면서 정점들에 번호를 직접 매겨주자. 각각의 edge가 어떤 번호의 정점들을 잇는지를 알아내는 것이 가장 핵심일 것이다. DFS 중에 어떤 점을 만났을 때, 이 점은 세 가지 중 하나이다.

• 방문한 적이 없거나
• 현재 DFS stack에 들어있는 정점이거나(즉, back edge를 탔거나)
• DFS를 마쳤던 정점이거나(즉, back edge를 타고 내려갔거나)

쓸 수 있는 색깔의 수가 상태의 수와 정확히 같으므로, 그 정점에서 빠져나올 때 적절한 수를 적어주고 나오면, 위의 세 가지 상태 중 어떤 것인지를 알 수가 있다. 또한 방문한 적이 없는 점을 만나면 새로운 번호를 매겨주면 되기 때문에, 이 경우에는 번호를 확실히 알 수가 있다.

DFS stack에 있는 정점이 무엇인지 알기 위해서는 어떤 방법이 있을까? stack의 정점 하나하나와 비교해볼 수 있겠다. 즉 무엇인지 모르는 그 점에 이상한 색(DFS stack에 들어있다면 가지고 있지 않을 색)을 매기고 stack을 거꾸로 올라가며 그 이상한 색깔이 있는 점을 찾는다면, 정점을 찾을 수 있고, LastRoad() 등으로 간선의 번호도 모두 알 수 있다. 이렇게 하면 44점을 받을 수가 있다. 스택을 타고 올라가는 과정에서 Move()의 호출이 너무 많기 때문에 100점은 받을 수가 없다.

고민하다보면, 어떤 두 정점이 같은지를 확인하기가 매우 힘들기 때문에, stack에 있는 점을 DFS하는 도중에 바로 바로 알아내려고 하는 것은 무리가 있다. 그러면 DFS stack에 들어있거나 DFS를 마친 정점들을 만나더라도, 그런 적이 있다는 것만 저장해두고 그냥 넘어가보자. 그리고 다시 root로 돌아오자. 그러면 모든 edge에 대해서, 양 쪽에서 각각 갈 때와 올 때 한 번씩 사용하므로 총 $4M$ 번의 Move() 호출이 생긴다. 이제 우리는 어떤 정점에 back edge들이 있었는지, 간선 번호는 어떤 값들이었는지를 알고 있다. 이것을 가지고 무엇을 할 수 있을까?

일단 확실히 여러 점들에 대한 처리를 한 번에 할 수 있다는 장점이 있다. IOI 1995에 출제된 wire 문제에서도 비슷한 방법을 사용한 풀이가 가능했다. 해당 문제에 대한 풀이는 여기에 있다. (circuit이라는 제목으로 되어있다) 지금 우리는 모든 back edge마다, 아래에서 볼 때 반대편 정점의 번호가 궁금한 것이 아닌가? 그러면 그 '반대편 정점'을 다양한 그룹으로 나누면서 시도해볼 수가 있다. 조금 더 고민해보면 3진법을 사용한 이런 방법을 생각할 수 있다.

• 그 '반대편 정점'의 번호를 3진법으로 나타냈을 때, 밑에서 첫 번째 자리가 0인지, 1인지, 혹은 2인지를 한 번 DFS를 하면서 값을 계속 적어놓으며 확인하면, back edge를 타고 올라간 점의 Color()의 값을 보면 되므로 구할 수 있다.
• 두 번째 자리부터 다섯 번째 자리까지도 똑같은 방법을 사용할 수 있다.
• $3^{5}=243>N_{max}$이므로, 여섯 번째 자리부터는 볼 필요가 없다.

DFS 횟수가 다섯 번이고, 우리는 간선들의 구조를 거의 다 알고 있기 때문에, 간선을 한 쪽에서만 사용할 수 있고, 그러면 각각 $2M$번씩 Move()를 호출하게 된다. 그러면 전체 호출 횟수가 딱 $14M$번에 맞게 되어 100점을 받을 수 있다.