다시 레드 찾아온 Being입니다...ㅋㅋ

변태 Petr 혼자 하드를 풀었습니다. 서브밋한 용자는 한 명 더 있긴 한데.. 썰렸군요..ㅠㅠ 가장 기억에 남는 건 Savior라는 레드 녀석이 하드부터 여는 모습이었습니다. 결국 Unopened/Unopened/Compiled로 레이팅을 160 깎아먹고 옐로로 떨어졌습니다. 애도를..ㅠㅠ

Easy (250 pts.)

• 문제 설명 나무막대기들이 n개 있습니다. 얘네를 팔고 싶은데 각각의 길이는 다 다릅니다. 그런데, 완전히 똑같은 길이의 막대기들만 팔 수 있다고 합니다. 그래서 적당히 막대기를 길이를 맞춰 잘라 팔아야 합니다. 막대기를 1회 자르는 데 드는 비용과 단위길이당 막대기의 판매 가격이 주어질 때 최대 이익은? # 1 <= n <= 50 # 1 <= 길이 <= 10^4 # 1 <= 단위길이당 가격 <= 10^3 # 1 <= 자르는 데 드는 비용 <= 10^3 [spoiler="풀이 보기"]팔기 위해서는 모두 똑같은 길이로 만들어야 한다고 하니, 어떤 길이로 팔 지 loop를 통해 정해 봅시다. 그 이후, n개의 막대들을 돌면서 그 길이로 만들기 위해서는 어떻게 cutting해야 하는지를 생각해보면 됩니다. 이 때 자를 수 있는 만큼 최대한 자르는 것이 언제나 유리합니다. 길이 i만큼을 얻기 위해 한 번 잘랐을 때 어차피 이익을 얻는다면, 즉 i * (단위길이당 가격) > (자르는 데 드는 비용) 이라면 최대한 자르는 것이 유리하지요. 자르는 횟수의 경우 (길이 - 1) / i 가 됩니다. 길이가 딱 맞아 떨어지는 경우는 한 번을 공짜로 얻을 수 있겠죠. 최대한 모든 막대를 자른 후 이익을 얻을 수 있는 경우에 대해 모두 누적해서 최대값을 구하면 됩니다. 챌린지 포인트: 그다지 tricky하지 않은 문제이다 보니 딱히 포인트는 없습니다.
  • 막대기의 길이에 대한 루프의 범위
  • 길이에 맞춰 막대를 잘랐을 때의 기대 이익이 음수인 경우를 잘라내지 않은 경우 => {1, 1, 1, 1, ...., 2}, 1000, 1[/spoiler]

Medium (500 pts.)

• 문제 설명 R*C 모양의 격자판이 있습니다. 격자판 중간중간에는 장애물이 있습니다. 장애물로 채워져있지 않은 빈 칸은 반드시 타일로 덮어야 하는데, 타일의 모양은 1*k 또는 k*1밖에 없습니다. 타일의 수를 최소화하고 싶은데, 타일은 겹쳐서는 안 됩니다. 필요한 최소 타일의 수는? # 1 <= R, C <= 10 [spoiler="풀이 보기"]한 행을 잡고 격자를 설치한다고 칩시다. 행의 각각의 칸은 행방향 격자 혹은 열방향 격자로 채워져야 하겠죠. 채우는 방법은 대략 2^C 정도가 있을 것입니다. 그 이전 행을 2^C 가지 중 한 가지 방법으로 채웠다고 칩시다. 이번 행 또한 2^C 가지 모양 중 하나로 채울 것입니다. 만일 그 모양들 가운데 붙어있는 두 칸이 모두 열방향 격자를 사용하기로 설정되어 있다면, 다음 행에서는 새로 격자를 사용할 필요 없이 전의 열에서 사용되었던 격자를 사용할 수 있을 것입니다. 결국 이전 행에서의 모든 상태에 대한 필요 격자 수를 알고 있다면 다음 행에서의 모든 상태에 대한 격자의 수를 구할 수 있죠. 따라서 이 문제는 DP처럼 안 보일 지 몰라도 DP가 맞습니다. 각 행에 대해서 2^C가지 상태에 대한 모든 최적값을 저장하면 됩니다. 이런 유형의 전형적인 문제로 CEOI 에 나왔던 http://acm.pku.edu.cn/JudgeOnline/problem?id=1038 가 있습니다. 이런 유형의 문제들의 특징이라면, 한 쪽 격자의 길이에 exponential한 영향을 받기 때문에 한 쪽 변은 매우 짧고 다른 한 쪽 변이 길지요. 챌린지 포인트:
• Divide & Conquer - 행 또는 열을 잡고 쪼개서 각각의 최적을 구한 후 더하는 방법 "#.########", "#.#.......", "#.########", "#.######.#", "#.######.#", "#.######.#", "#.######.#", "########.#", ".......#.#", "########.#" 처럼 꼬여있는 모양으로는 오답을 냅니다.
• Backtracking - 여기에는 각종 커팅(time cut, 한 칸의 주위에 네 칸이 막혀있는 경우 예외처리 등등)이 있을 수 있습니다. case-by-case attack이 필요하지만 위험하므로 커팅이 있는 경우 시도하지 않는 편이 좋을 것 같습니다. ".#.#.#.#.#", "#.#.#.#.#.", ".#..#.#..#", "#..#.#.##.", ".##..#...#", "#...#..##.", ".##.#.#..#", "#..#.#..#.", ".#.#.#.#.#", "#.#.#.#.#."
• Bipartite Matching - 각 칸에 대해서 최대한 뻗어나갈 수 있는 행방향과 열방향 타일들을 매칭함으로써 최대한 매칭하는 것 같습니다. 이 경우 확인은 안 해봤지만-_-;; "#.#", "...", "#.#" 같은 경우가 문제가 생긴다고 합니다. [/spoiler]

Hard (1000 pts.)

• 문제 설명 정사면체가 있습니다. 이 정사면체는 마치 루빅스 큐브처럼 각 변이 N등분되어서 회전이 가능합니다. 처음에 각 면은 각각 한 가지의 색으로 칠해져 있습니다. 이제 이 정사면체의 특정 부분을 돌리거나 정사면체 자체를 회전시킬 수 있을 겁니다. 일련의 동작이 주어졌을 때 그 동작들을 몇 번 연달아 수행해야 원래 상태가 될까요? # 1 <= N <= 50

[spoiler="풀이 보기"]일단 간단한 문제를 생각해 봅시다.
(1, 2, 3, ..., N)의 수열이 있습니다. 이 수열에 대해서 어떤 permutation을 적용합니다. 예를 들어-
(1, 2, 3, 4)에 permutation s=(2, 1, 4, 3)을 적용한다면, s(1) = 2, s(2) = 1, s(3) = 4, s(4) = 3 이렇게 될 겁니다.
이 경우 s^2(i) = s(s(i)) = i죠.
s^k(i) = i가 되는 최소의 k를 구하려면 어떻게 해야 할까요?
1 2 3 4
2 1 4 3
1이 2의 자리로 가고 2가 1의 자리로 옵니다. 즉, 1과 2가 원래 자리로 가려면 한 번의 변환마다 한 칸씩 자리를 이동하므로 그들이 이루는 cycle의 길이만큼의 이동이 필요합니다. 3과 4에 대해서도 마찬가지이죠.
따라서 이와 같이 cycle들을 묶어냈을 때 그들의 lcm이 최소 k가 됩니다.
1 2 3 4 5 6
5 3 1 6 2 4
의 경우 cycle이 (1 5 2 3) (4 6)과 같이 만들어지므로 모두가 제자리에 가려면 4회의 변환이 필요하죠.
이 문제는 결과적으로 4 n^2개의 원소들에 대한 permutation이 주어졌을 때 그 permutation에 대한 최소 k를 구하는 문제입니다.
진짜 문제는 그 permutation 자체를 구하는 게 너무 끔찍하다는 점입니다... 제 머릿속에선 도저히 2차원보다 높은 차원의 도형은 그려지지 않기 때문에 3차원 도형을 도저히 회전시킬 자신이 없더군요 ㅠㅠ
여튼 각 변환의 기본 operation들을 어떻게 하면 깔끔하게 번호를 매기고 변환을 만들어낼 것인가 하는 것이 문제입니다. 물론 여러 가지 방법이 있겠습니다만 제 방법을 소개하고 싶어도 이대로는 머리털이 남아나지 않을 것 같아서 그냥.. Petr가 상당히 깔끔한 방법으로 구현해 두었습니다..ㅠㅠ 그 소스 코드를 찬찬히 읽어보시는 걸 권합니다. (Petr's code) 아니면 연습방에 있는 한국 최강의 휴학생 병특 프로그래머(?) Astein옹의 코드를 보셔도..
챌린지 포인트: 푼 사람이 있어야 하던 말던 ㅠㅠ - Petr는 사람이 아닙니다 -
[/spoiler]