안녕하세요. Astein입니다.
오랜만에 에디토리얼을 쓰는거라 익숙하지가 않네요 ;ㅁ;
TCO'08 Round 3는 3월 2일 새벽 3시에 열렸습니다. 늦은 시간에도 #icpc 채널에서 응원해 주셨던 많은 분들께 감사의 말씀을..
(그리고..... 지못미 JM ㅜㅜ)
간단히 결과만 쓰면 Astein 7등, ryuwonha 9등, lewha0 52등, ainu7 114등으로 이렇게 네 명이 Round 4에 진출하게 되었습니다.

Easy (250 pts.)

• 문제 설명 당신은 친구와 케이크를 나누어 먹으려고 합니다. 만약 전체 케익의 절반을 당신이 먹고, 남은 양의 절반은 친구가 먹는다고 합시다. 이러한 과정을 반복한다면 당신이 먹는 양을 계산할 수 있습니다. You Him ------ ------ 1/2 + 1/4 + 1/8 + 1/16 + 1/32 + 1/64 + 1/128 + 1/256 + ... 위의 과정을 반복하면 당신은 전체 케이크의 2/3만큼을, 당신의 친구는 1/3만큼을 먹게 됩니다. 하지만 위의 패턴이 아니라 다른 패턴으로 먹을 수도 있고, 다른 패턴으로 먹게 된다면 먹을 수 있는 비율이 달라지게 됩니다. "you, him, you"의 패턴으로 케이크를 분할한다면 당신은 전체 케이크의 5/7만큼을, 당신의 친구는 2/7만큼을 먹게 되니까요. You Him You ----- ------ ----- 1/2 + 1/4 + 1/8 + 1/16 + 1/32 + 1/64 + ... 첫번째 열과 세번째 열의 값의 합은 두번째 열의 값의 5/2배가 됩니다. 따라서 당신이 먹은 양은 친구가 먹은 양의 5/2배가 되기 때문에 위에서 계산한 결과만큼 먹게 되는 것이죠. 어떤 분수 a/b가 주어졌을 때 제일 간단한 패턴을 찾는 프로그램을 작성하는 것이 문제입니다. "You" 패턴은 *로, "Him" 패턴은 -로 표시합니다. 만약 길이 60이하의 패턴으로 만드는 것이 불가능하다면 impossible을 리턴하면 됩니다. a와 b는 2^63-1 이하의 수이고, 서로소입니다. [spoiler="더 보기..."]
• 문제 해법 패턴의 길이가 k라고 가정을 해 봅시다. 첫 번째에 가져가는 사람은 1/2만큼을 가져가고 두 번째에 가져가는 사람은 1/4만큼을 가져가고 ... k번째에 가져가는 사람은 1/(2^k)만큼을 가져갑니다. 거꾸로 생각을 해 보면 k번째에 가져가는 사람이 1만큼 가져간다고 했을 때, k-1번째에 가져가는 사람은 (상대적으로) 2만큼 가져가고, k-2번째 가져가는 사람은 4만큼, ..., 첫번째에 가져가는 사람은 2^(k-1)만큼을 가져가게 됩니다. 이를 분수로 나타내면 분모는 (2^k) - 1이 되지요. 즉 기약분수 a/b에서 b가 (2^k) - 1의 약수라면, 길이 k인 패턴으로 표현할 수 있다는 것이 됩니다. 입력받은 수 a/b를 분모가 (2^k) - 1인 꼴에 맞도록 일정한 수를 곱해줍니다. 그러면 a' / (2^k - 1) 꼴의 분수를 찾을 수 있지요. 여기서 a'을 이진수로 바꿔서 매핑하면 답을 구할 수 있습니다. 마지막자리는 1, 그 앞자리는 2, ..., 의 식으로 표현되어 있기 때문이지요. 저는 처음에 길이가 60 이상인 경우 impossible이라는 말을 확인하지 못해서 resubmit을 하게 되었네요. 덕분에 챌린지도 3개나 성공하긴 했지만요. :) 만약 문제를 풀다가 resubmit한 경우라면 다른 사람도 같은 실수를 할 수 있다고 생각하고 챌린지 페이즈때 미리 준비하는 것도 하나의 팁이 될 수 있겠네요. ~~~ cpp

long long a, b;
struct ZenoDivision {
string cycle(string _a, string _b) {
sscanf(_a.c_str(), "%Ld", &a);
sscanf(_b.c_str(), "%Ld", &b);
long long up, down = 0;
for (int i = 0; i < 63; ++i) {
down = down + down + 1;
if (down % b == 0) {
up = (down / b) * a;
string S = "";
for (int j = 0; j < i + 1; ++j) {
if (up & (1LL << j)) S = '*' + S; else S = '-' + S;
}
if (S.size() > 60) break;
return S;
}
}
return "impossible";
}
};

[/spoiler]


Medium (500 pts.)
* 문제 설명
  BattleDice는 N개의 면을 가진 주사위로 하는 2인용 게임입니다. 두 명의 플레이어가 주사위를 굴리고, 더 높은 숫자가 나온 사람이 이기는 게임입니다. 만약 같은 숫자가 나오는 경우에는 승부가 날 때까지 계속 반복합니다. A와 B는 처음에 3 개의 주사위를 가지고 게임을 시작합니다. B가 먼저 3개의 주사위 중에 하나를 선택하고, A는 남은 2개의 주사위 중 하나를 선택합니다.
  A와 B는 2개의 주사위밖에 없습니다. 그래서 세 번째 주사위는 A가 자신이 이길 확률을 최대한 높이기 위해서 직접 만들기로 하였습니다. 이렇게 만든 3개의 주사위를 가지고 A와 B는 플레이합니다. 물론 B는 자신이 이길 수 있는 최선을 방법으로 플레이한다고 가정합니다.
  1부터 range범위의 숫자가 적혀 있는 주사위가 입력으로 주어집니다. 두 개의 주사위는 모두 N면체 주사위입니다. 또한 이 두 개의 주사위는 모든 면에 같은 숫자가 적혀 있는 경우는 없다고 가정합니다. 하지만 A가 만드는 세 번째 주사위의 경우에는 모든 면의 숫자가 같을 수도 있습니다.
  A와 B 둘 다 최선을 다하는 경우 A가 이길 확률을 최대한 크게 만들려고 합니다. 같은 경우가 둘 이상 있는 경우, lexicographically-first한 방법을 구하려고 합니다.
  예를 들어, range = 6이고, die1 = {2, 2, 5}, die2 = {2, 3, 3}인 경우가 있다고 합시다. A는 die3 = {1, 3, 4}인 주사위를 선택하였습니다.
  만약 B가 die1을 선택하였다면 A는 die2를 선택하는 것이 최선의 방법입니다. 이 경우 A가 이길 확률은 4/7가 됩니다. B가 die2를 선택하였다면 A는 4/7의 확률로 이길 수 있는 die3을 택할 것입니다. 또한 B가 die3을 골랐다면 A는 die1을 골라서 자신의 이길 확률을 5/9로 만들겠지요. A와 B 모두 제일 좋은 방법으로 플레이할 것이기 때문에 B는 die1이나 die2를 택할 것이고, A는 4/7의 확률로 이기게 될 것임을 짐작할 수 있습니다. 물론 A가 {1, 4, 4}의 주사위를 만들어도 확률은 같지만, 사전순으로 {1, 3, 4}가 먼저 나오기 때문에 이 것은 올바른 답이 아닙니다.
  각각의 주사위는 2 ~ 10개의 면을 가지고 있고, 주사위에 써 있는 숫자의 범위인 range는 2 ~ 15 범위의 숫자입니다. 
[spoiler="더 보기..."]
* 문제 해법
  대회 시작할때 너무 당황해서 250점 짜리를 열려고 했다가 손이 미끄러지는 바람에 500점 짜리 문제를 먼저 열었습니다. (결과적으로 보면 좋았지만요 -_- 250점 짜리 문제 resubmit은 1000점을 푼 이후에 했으니...) 
  die3는 최대 10개의 원소로 이루어진 set이고, range는 1부터 15사이의 숫자인 경우가 최악의 경우가 됩니다. 이게 모두 몇 가지나 되는지 세어보면 많을 것 같지만 의외로 1307504가지 밖에 되지 않습니다. (왼쪽의 숫자가 어떻게 나왔는지는 잘 생각해 보세요!)
  die3의 경우를 모두 search한 후 die1과 die2를 비교하여 확률을 계산하게 되면 2s라는 시간이 충분하지 않게 느껴질 수도 있습니다. 통과할 수 있을지는 직접 짜 보지 않아서 잘 모르겠네요 =ㅁ=;;
  die1 = {2, 2, 5}인 경우. 아래와 같은 테이블을 만들어 줍니다.
       1  2  3  4  5  6
W : 0  0  2  2  2  3
L :  3  1   1  1  0  0
[/spoiler]
  위의 테이블은, die3에 어떤 숫자가 포함되었을 때 몇 승 몇 패를 하게 될 것인가를 나타낸 테이블입니다. W는 Win, L은 Lose를 나타내지요. 그러면 die3에 i를 포함한다고 하였을 때, die1과의 상대전적, die2와의 상대전적을 O(1)만에 구할 수 있게 됩니다. 
  자세한 구현은 아래의 소스코드를 참조하시면 될 것 같습니다.
~~~ cpp

struct Frac {
    int up, down;
    Frac(int a = 0, int b = 1) : up(a), down(b) {}
    bool operator < (const Frac &a) const {
        return up * a.down < a.up * down;
    }
};
int w1[20], l1[20];
int w2[20], l2[20];
vector <int> a, ret;
int N, range;
Frac P12, P21, P13, P31, P23, P32;
Frac best;
struct BattleDice {
    void backtr(int k, int last, int W1, int L1, int W2, int L2) {
        if (k == N) {
            P13 = Frac(W1, W1 + L1);
            P31 = Frac(L1, W1 + L1);
            P23 = Frac(W2, W2 + L2);
            P32 = Frac(L2, W2 + L2);
            Frac now, choose;
            if (P12 < P13) now = P13; else now = P12;
            if (P21 < P23) choose = P23; else choose = P21;
            if (choose < now) now = choose;
            if (P31 < P32) choose = P32; else choose = P31;
            if (choose < now) now = choose;
            if (best < now) {
                best = now;
                ret = a;
            }
            return;
        }
        for (int i = last; i <= range; ++i) {
            a[k] = i;
            backtr(k + 1, i, W1 + w1[i], L1 + l1[i], W2 + w2[i], L2 + l2[i]);
        }
    }
    vector <int> die3(vector <int> die1, vector <int> die2, int _range) {
        range = _range;
        N = sz(die1);
        a.resize(N);
        for (int i = 0; i < N; ++i) {
            for (int j = die1[i] + 1; j <= range; ++j) w1[j]++;
            for (int j = die1[i] - 1; j >= 1; --j) l1[j]++;
            for (int j = die2[i] + 1; j <= range; ++j) w2[j]++;
            for (int j = die2[i] - 1; j >= 1; --j) l2[j]++;
        }
        int w = 0, l = 0;
        for (int i = 0; i < N; ++i) {
            w += w1[die2[i]];
            l += l1[die2[i]];
        }
        P12 = Frac(w, w + l);
        P21 = Frac(l, w + l);
        backtr(0, 1, 0, 0, 0, 0);
        return ret;
    }
};

Hard (1000 pts.)

• 문제 설명
  [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]