안녕하세요, Partition of Unity란 이름으로 참가했던 유키 입니다. 어쩌다보니 이렇게 에디토리얼을 쓰게 됐는데, 조금씩 쓰면서 차차 수정하도록 하겠습니다.
A. Bridge Bidding

어찌 보면 이번 셋에서 가장 쉬운 문제 중에 하나겠습니다만, 아무래도 문제가 길다보니 시도 회수가 적지 않았나 싶습니다. 간단히 문제를 설명하자면, 손에 든 브릿지 패가 주어졌을 때 어떻게 Bid할 것인지를 판단하는 것입니다. 혹 마이티에 익숙하시다면 어떤 조건으로 출마할지를 결정해주는 프로그램이랄 수 있겠네요.
문제에 아홉 가지 조건이 나와 있는데, 앞의 조건부터 차례로 체크해보면서 하면 됩니다. 특별히 주의할 게 있다면 두 종류의 무늬에서 같은 개수의 카드가 있을 수 있다는 것입니다. 예를 들어 4번 조건에서 6-x-x-x 라고 되어 있는데, 이것이 6-6-x-x 일 수도 있으므로 두 개의 무늬를 모두 확인해야 합니다.
B. Basket of Gold Coins

가장 많은 팀이 풀었던 문제였습니다. 질량이 w인 진짜 동전과, w-d인 가짜 동전들이 담겨있는 주머니가 있습니다. 어느 주머니에 가짜 동전이 들어있는지를 찾아내기 위해, N개의 주머니에서 차례로 1, 2, 3, ..., N-1, 0 개의 동전을 꺼내서 질량을 잽니다. 이렇게 잰 질량이 주어졌을 때, 몇 번 주머니에 가짜 동전들이 들어있는지 파악하는 문제입니다.
저는 쉽게 하기 위해서 1번 주머니부터 차례로 각 주머니가 가짜 주머니라고 가정해본 뒤, 그 때의 질량과 입력으로 주어진 질량을 비교했습니다. 일치하는 경우가 없다면 N번 주머니(동전을 0개 꺼낸)가 답이 되고요. 식을 세워서 정리해보면 한 줄의 코드로도 풀 수 있는 문제이기도 합니다 :)
C. Toothpick Arithmetic

어떤 자연수를 표시할 때, 그 자연수만큼의 이쑤시개를 사용할 수 있습니다. 예를 들어 3은 |||으로, 5는 |||||로 표시하는 식으로요. 이쑤시개 두 개를 겹치게 잘 두면 곱하기(x)와 더하기(+)도 표현할 수 있고요. 이 때, 주어진 N을 표시하기 위한 최소 개수의 이쑤시개 수를 구하는 문제입니다. 예를 들어 35는 |||||||x|||||로 표시할 수 있습니다. 이 때 7+5+2(곱하기를 표시하기 위한), 즉 14개의 이쑤시개가 필요합니다.
연산의 순서를 생각해보면, 먼저 곱셈만을 이용하여 몇 개의 수들을 표시하고, 그 수들을 더하는 식으로 수를 표현할 수 있습니다. 예를 들어 a*b+c는 곱셈만을 이용하여 a*b, c를 표현한 후 이 둘을 더하는 식으로 표시할 수 있는 것이지요. 따라서 곱셈만을 이용하여 어떤 수를 표시하는 최소 개수의 이쑤시개를 구하고, 이들의 합으로 어떤 수를 표시하는 최소 개수의 이쑤시개를 구하면 됩니다. 구하는 방법은 DP를 쓸 수 있고요.
D[n]을 n을 곱셈만으로 표시할 때 필요한 최소 개수의 이쑤시개라고 하겠습니다. n개의 이쑤시개를 세워두는 경우를 생각해보면 D[n]=n으로 초기값을 둡니다. 그리고 n의 약수 q를 하나씩 살펴봅니다. n=p*q라고 할 때, D[n] = min(D[n], D[p] + D[q] + 2)가 됩니다. 곱셈만을 이용하여 p, q를 각각 표현한 뒤, 이 사이에 두 개의 이쑤시개를 사용하여 x(곱하기) 기호를 두는 것이지요.
E[n]을 n을 곱들의 합으로 표시할 때 필요한 최소 개수의 이쑤시개라고 하겠습니다. 그러면 E[n]은 우선 D[n]으로 둘 수 있을거고.. 실제로 덧셈을 하는 경우를 생각해보면 E[n] = min(E[n], E[n-i] + D[i] + 2)가 되겠네요(1 <= i < n). 이는 i를 곱셈만으로 표현하고, 나머지 n-i는 곱셈의 합으로 표현한 뒤, 이 사이에 두 개의 이쑤시개를 사용하여 + 기호를 두는 것입니다.
가장 어려운 부분은 표현식을 직접 구하는 역추적 부분이 아닐까 싶은데.. 이는 D[n]의 최소값을 주는 p를 저장해두고, E[n]의 최소값을 주는 i를 저장해두는 식으로 해결할 수 있습니다. 이 부분은 직접 생각해 보시거나, 추후 첨부될 소스를 참고하세요 :D
D. Human Knots

얼핏 보기에 굉장히 까다로워 보이는 문제입니다. 복잡해보이는 그림도 몇 개 있고.. 하지만 막상 뚜껑을 열어보면 그다지 어렵지 않은 그런 문제가 아니었나 싶습니다. 원주상에 1부터 n까지의 점들이 차례로 찍혀 있습니다. 그리고 n개의 선분들이 몇 개의 점들을 연결하고 있고요. 이 때 점들의 순서를 잘 재배열하여 겹치는 선분이 없는 n각형을 만들 수 있는지를 물어보는 문제입니다. 가능한 경우에는 재배열되는 점의 최소 개수를 구하고요.
우선 점들의 재배열 순서를 구합니다. 이는 입력을 하나의 그래프로 봤을 때, 전체를 아우르는 하나의 싸이클이 됩니다. 만약 n개의 점들이 길이 n짜리인 사이클을 만들지 못한다면 not solvable한 경우가 됩니다. 다음 단계로는 점들을 재배열하는데, 이는 예제로 설명하는게 쉬울 것 같습니다.
그림으로 주어진 예제에서는 (1 2 3 4 5 6)의 점들을 (1 5 2 3 6 4)로 만들어야 합니다. 이 때 필요한 최소 자리 이동 회수는 (KOI 기출 문제에도 있었던 것 같지만) n - (두 수열의 LCS의 길이) 가 됩니다. (1 2 ... n)과의 LCS의 길이는 longest increasing sequence의 길이이기도 하고요. 따라서 (1 5 2 3 6 4)의 LIS의 길이를 구하면 1-2-3-4의 4가 되고, 따라서 답은 2가 됩니다. 문제는 점들이 원주 상에 있기 때문에 회전이 가능하다는 것인데요, 따라서 (1 5 2 3 6 4)를 회전시킨 각각의 순열들에 대해서도 위의 과정을 반복해 봅니다. (5 2 3 6 4 1), (2 3 6 4 1 5), ... 등에 대해서도요. 또, 반대방향으로 배열하는 것도 가능하기 때문에 (1 4 6 3 2 5), (4 6 3 2 5 1), ... 등에 대해서도 해봅니다. 따라서 총 2N번 시도해보면 되겠습니다.
아마 이보다는 더 효율적인 방법이 있을 것 같은데 -_-a 알려주시면 수정하도록 하겠습니다 ^^
E. Permutation Recovery

To be updated
F. Marbles in Three Baskets

상태공간탐색. To be updated
G. Doors and Penguins

점들을 0~90도 회전시켜 보면서 가로축, 세로축에 평행한 선으로 나뉘는지 확인한다. To be updated
H. Knots

2^(n/2 - 1) * (n/2 - 1)! / (1부터 n/2개의 홀수들의 곱). To be updated
I. String Equations

To be updated