탈락의 아쉬움을 달래고자 오랜만에 에디토리얼을 씁니다. 한국인은 전원 탈락이네요 허허.. 형식 정리하기 귀찮아 그냥 쓰겠습니다.
A.
문제: X개의 상자로 구성된 소코반 게임을 합니다. 소코반 게임은 격자 위의 여러 상자를 시작 위치에서 목표 위치들로 움직이는 게임입니다.상자를 움직일 때 움직이는 방향이 비어있어야 하고, 그 반대 방향은 사람이 상자를 밀어야 하므로 비어있어야 합니다. 상자를 움직이는 사람은 텔레포트할 수 있어서, 사람의 현재 위치는 고려하지 않아도 됩니다. 이 소코반 게임의 모든 순간은 두 상태로 나뉘어지는데, 위험하지 않은 순간과 위험한 순간이라 합시다. 위험하지 않은 순간에서 상자를 밀어서 X개의 상자들이 서로에 대해 연결되지 않은 상태가 되면 위험한 순간이 되며, 위험한 순간에서 상자를 밀어 다시 위험한 순간이 되어서는 안 됩니다. 주어진 상자의 위치와 벽 등으로부터 최소 이동 회수를 구하는 것이 문제입니다.
풀이: 소코반은 전통적으로 단순한 상태공간 탐색보다 좋은 풀이를 생각하기 어렵습니다. 그 사실에 비추어 조금 더 생각해보면, 위험하지 않은 상태의 모양은 X = 5 에 대해서는 펜토미노일 것입니다. 이 펜토미노들의 회전변환과 평행이동을 모두 고려해도 상태공간의 크기는 얼마 되지 않으며, 위험한 상태에 대해서 고려해도 끽해야 상수배 정도의 상태공간을 가집니다. 고로, set이나 map과 같은 자료구조를 이용하여 valid한 상태공간만을 탐색하면 금방 답을 구할 수 있습니다.
B.
문제: N개의 문자열로 구성된 집합 S가 있고, 이 문자열을 중복을 고려하지 않고 M개 선택하여 쭉 늘어놓습니다. 4차 이하의 26변수에 대한 다항식이 주어집니다. 각 변수는 늘어놓은 문자열에서 각 알파벳이 등장하는 횟수입니다. 모든 가능한 문자열 선택 방법에 대해 계산된 다항식의 값의 합을 구하는 것이 문제입니다.
풀이: 다항식의 어떤 단항 하나를 생각해 봅시다. 예를 들어 a^3 b라 합시다. 다른 형태의 단항에 대해서도 다를 것이 없습니다. 모든 조합에 대한 합을 구해야 하므로,
\sumx_1 \n S} \sum{x_2 \in S} .. \sum{x_M \in S} (a(x_1) + a(x_2) + ... + a(x_M))^3 (b(x_1) + b(x_2) + .. + b(x_M))
과 같이 나타낼 수 있습니다. a(v)는 문자열 v에서 a의 등장 횟수입니다.
보통 sigma 식을 정리하듯 이 식에서, a(x_M), b(x_M)을 제외한 나머지를 상수로 놓고 생각해 봅시다. 즉, A = a(x_1) + a(x_2) + .. + a(xM-1), B = b(x_1) + ... 이라 합시다.
\sumx_1 \n S} \sum{x_2 \in S} .. \sum{x_M \in S} (A + a(x_M))^3 (B + b(x_M))
위 식을 전개해 봅시다.
\sumx_1 \n S} \sum{x_2 \in S} .. \sum{x_M \in S} (A^3 B + 3 A^2 a(x_M) B + 3 A a(x_M)^2 B + ... + a(x_M)^3 b(x_M) )
대충 형태가 보입니다. 이것들을 각각 나누면
\sumx_1 \n S} \sum{x_2 \in S} .. \sum{x_M \in S} (A^3 B)
\sumx_1 \n S} \sum{x_2 \in S} .. \sum{x_M \in S} (3 A a(x_M)^2 B)
...
\sumx_1 \n S} \sum{x_2 \in S} .. \sum{x_M \in S} (a(x_M)^3 b(x_M))
각 항에서 A, B는 가장 안쪽 sigma에 대해 상수입니다. 꺼냅시다.
\sumx_1 \n S} \sum{x_2 \in S} .. (A^3 B) * \sum{x_M \in S} (1)
\sumx_1 \n S} \sum{x_2 \in S} .. (3 A^2 B) * \sum{x_M \in S} (a(x_M))+ ... + \sumx_1 \n S} \sum{x_2 \in S} .. \sum{x_M \in S} (a(x_M)^3 b(x_M))
여기서 중요한 사실은,
\sumx_1 \n S} \sum{x_2 \in S} .. (A^3 B)
와 같은 항을 잘 생각해보면 a^3 b 라는 다항식에 대해 M-1개의 문자열에 대한 문제를 푸는 것과 같습니다! 따라서 S(x, m)을 다항식 x에 대한 M = m인 경우의 문제의 답이라 하면
S(a^3 b, m) = S(a^3 b, m - 1) * \sum{x_M \in S} (1)+ S(a^2 b, m - 1) * \sum{x_M \in S} (a(x_M))+ ...
과 같은 형태로써, 점화식이 됩니다. 이는 간단히 memoization 등을 통해 구현하면 되고, 전개하는 루틴은 각 패턴에 대해 하드코딩할 필요가 전혀 없고 2^4 경우에 대해 각각 선택하면 되므로, bit pattern에 대응시키면 됩니다.
C.
문제: N명의 선수가 여러 줄로 늘어서 단체사진을 찍는데, 각 선수의 줄의 맨 왼쪽에서의 위치를 x라 하고 앞에서부터 줄의 번호를 y라 합시다. 모든 선수의 x 좌표는 서로 다릅니다. 이 때, 각 선수에 대해 자신과 같은 줄에서 오른쪽으로 가장 가까운 사람, 자신 윗 줄에서 오른쪽으로 가장 가까운 사람, 자신 아랫 줄에서 오른쪽으로 가장 가까운 사람과는 다른 색의 옷을 입어야 합니다. 최소 몇 가지의 옷 색상이 필요합니까?
풀이: 그래프로 모델링하고 최소 채색 수를 구하는 문제가 됩니다. 일반적인 형태의 그래프라면 매우 어려운 문제겠지만, 문제의 성질을 뜯어보면 이 그래프는 triangulated graph임을 알 수 있습니다. (모든 길이 4 이상의 cycle은 chord를 가짐)
일단 triangulated graph이므로, 그러한 삼각형이 존재하면 최소 3개의 색상이 필요합니다. 간선이 하나도 없다면 1색상, 사이클이 없다면 2색상임은 자명합니다. 조금 더 생각해보면 평면그래프이므로 4색 정리에 의해 4색이면 충분하다는 것을 확인할 수 있습니다.
그러면 3색인지 4색인지 확인하기만 하면 되는데, 3색일 경우 삼각형 두 개가 인접하면 한 쪽 삼각형의 색상이 결정되면 나머지 한 쪽 삼각형은 변을 공유하므로 나머지 한 점의 색상이 확정된다는 사실을 알 수 있습니다. 삼각형들의 인접관계에 대한 그래프를 생각하면, 이 삼각형들의 인접관계 그래프가 odd cycle을 포함하지 않는다면 삼각형들은 두 종류로 분류할 수 있습니다. 이 삼각형 중 어떤 것을 하나 칠하기만 하면, 나머지 삼각형들의 색상이 모조리 결정됩니다. 만약 odd cycle을 가진다면? 이 경우는 3색으로 채색 불가능합니다.
그러면 가장 작은 odd cycle을 생각할 수 있고 (큰 odd cycle이 있다면, 부분으로 작은 odd cycle을 포함할 것) 이 odd cycle은 반드시 원래 그래프에서 어떤 한 정점을 둘러싼 삼각형들이 됩니다. 따라서, 어떤 한 정점이 홀수개의 삼각형들로 둘러싸여 있다면 4색으로 채색해야 합니다.
먼저 삼각형들로 둘러쌓여질 필요충분조건은, 현재 점을 #라 했을 때
** # * *
위치에 해당하는 곳에 반드시 다른 점(선수)가 있어야 합니다. 이들 중 하나라도 없다면 둘러쌓이지 않게 됩니다.
이후 여기에 삼각형들이 추가되려면,
! ** # * ! *
이 곳에 존재하는 점들의 개수만큼 삼각형이 생성됩니다. 따라서, 이 곳에 존재하는 점의 개수가 홀수인지 짝수인지만 판별하면 됩니다.
그러면 점들을 x좌표에 대해 큰 좌표부터 작은 좌표로 sweep하면서 자신의 오른쪽, 오른쪽 위, 오른쪽 아래 간선을 이을 수 있으며, 동시에 각각의 점에 대해 자신의 6방향으로 간선의 개수를 셀 수 있습니다. 그리고 각 점들을 inspect하기만 하면 됩니다. 삼각형이 존재하는지의 여부는 이 정보로 간단히 판별할 수 있습니다.
D.
문제: 안 읽어서 모릅니다. 헤헤^^;
후기
마음을 편하게 먹고 대회를 했었더랬죠. C번을 (좀 멀리 돌아가는 풀이긴 합니다만) 찾았다고 생각하고 5번을 제출했는데 틀려서, 에잉.. 뭐 오늘 장사 여기서 접자 이런 마인드였습니다. 그리고 남은 시간을 그냥 딴짓하면서 보냈는데, 오늘 연습 세션에 들어가 보니 조금만 고치니까 두 데이터 셋 모두 Correct가 뜨더군요. 고치는 게 어렵지는 않아 맞았더라면 48점으로 진출이라 아쉽긴 한데, 뭐 그냥저냥 제 잘못이라 그러려니 하고 있습니다 : ( 서울대회에서는 이번처럼 긴장하지는 않으면서 끝까지 좀 aggressive하게 풀면 좋은 결과가 있지 않을까 싶습니다.
Being
탈락의 아쉬움을 달래고자 오랜만에 에디토리얼을 씁니다. 한국인은 전원 탈락이네요 허허.. 형식 정리하기 귀찮아 그냥 쓰겠습니다.
A.
문제: X개의 상자로 구성된 소코반 게임을 합니다. 소코반 게임은 격자 위의 여러 상자를 시작 위치에서 목표 위치들로 움직이는 게임입니다.상자를 움직일 때 움직이는 방향이 비어있어야 하고, 그 반대 방향은 사람이 상자를 밀어야 하므로 비어있어야 합니다. 상자를 움직이는 사람은 텔레포트할 수 있어서, 사람의 현재 위치는 고려하지 않아도 됩니다. 이 소코반 게임의 모든 순간은 두 상태로 나뉘어지는데, 위험하지 않은 순간과 위험한 순간이라 합시다. 위험하지 않은 순간에서 상자를 밀어서 X개의 상자들이 서로에 대해 연결되지 않은 상태가 되면 위험한 순간이 되며, 위험한 순간에서 상자를 밀어 다시 위험한 순간이 되어서는 안 됩니다. 주어진 상자의 위치와 벽 등으로부터 최소 이동 회수를 구하는 것이 문제입니다.
풀이: 소코반은 전통적으로 단순한 상태공간 탐색보다 좋은 풀이를 생각하기 어렵습니다. 그 사실에 비추어 조금 더 생각해보면, 위험하지 않은 상태의 모양은 X = 5 에 대해서는 펜토미노일 것입니다. 이 펜토미노들의 회전변환과 평행이동을 모두 고려해도 상태공간의 크기는 얼마 되지 않으며, 위험한 상태에 대해서 고려해도 끽해야 상수배 정도의 상태공간을 가집니다. 고로, set이나 map과 같은 자료구조를 이용하여 valid한 상태공간만을 탐색하면 금방 답을 구할 수 있습니다.
B.
문제: N개의 문자열로 구성된 집합 S가 있고, 이 문자열을 중복을 고려하지 않고 M개 선택하여 쭉 늘어놓습니다. 4차 이하의 26변수에 대한 다항식이 주어집니다. 각 변수는 늘어놓은 문자열에서 각 알파벳이 등장하는 횟수입니다. 모든 가능한 문자열 선택 방법에 대해 계산된 다항식의 값의 합을 구하는 것이 문제입니다.
풀이: 다항식의 어떤 단항 하나를 생각해 봅시다. 예를 들어 a^3 b라 합시다. 다른 형태의 단항에 대해서도 다를 것이 없습니다. 모든 조합에 대한 합을 구해야 하므로,
\sumx_1 \n S} \sum{x_2 \in S} .. \sum{x_M \in S} (a(x_1) + a(x_2) + ... + a(x_M))^3 (b(x_1) + b(x_2) + .. + b(x_M))
과 같이 나타낼 수 있습니다. a(v)는 문자열 v에서 a의 등장 횟수입니다.
보통 sigma 식을 정리하듯 이 식에서, a(x_M), b(x_M)을 제외한 나머지를 상수로 놓고 생각해 봅시다. 즉, A = a(x_1) + a(x_2) + .. + a(xM-1), B = b(x_1) + ... 이라 합시다.
\sumx_1 \n S} \sum{x_2 \in S} .. \sum{x_M \in S} (A + a(x_M))^3 (B + b(x_M))
위 식을 전개해 봅시다.
\sumx_1 \n S} \sum{x_2 \in S} .. \sum{x_M \in S} (A^3 B + 3 A^2 a(x_M) B + 3 A a(x_M)^2 B + ... + a(x_M)^3 b(x_M) )
대충 형태가 보입니다. 이것들을 각각 나누면
\sumx_1 \n S} \sum{x_2 \in S} .. \sum{x_M \in S} (A^3 B)
후기
마음을 편하게 먹고 대회를 했었더랬죠. C번을 (좀 멀리 돌아가는 풀이긴 합니다만) 찾았다고 생각하고 5번을 제출했는데 틀려서, 에잉.. 뭐 오늘 장사 여기서 접자 이런 마인드였습니다. 그리고 남은 시간을 그냥 딴짓하면서 보냈는데, 오늘 연습 세션에 들어가 보니 조금만 고치니까 두 데이터 셋 모두 Correct가 뜨더군요. 고치는 게 어렵지는 않아 맞았더라면 48점으로 진출이라 아쉽긴 한데, 뭐 그냥저냥 제 잘못이라 그러려니 하고 있습니다 : ( 서울대회에서는 이번처럼 긴장하지는 않으면서 끝까지 좀 aggressive하게 풀면 좋은 결과가 있지 않을까 싶습니다.
14년 전