운이 좋아서 1등을 하게 된 Astein입니다. 굽신굽신 _ _);;
900점짜리를 풀다가 삽질을 많이했는데... 챌을 많이 주워먹었네요 [...]

Easy (250 pts.)

• 문제 설명 당신은 이상한 마을에 방문하였다. 이 마을에는 현재 몬스터 M마리와 토끼 B마리가 살고 있다. 이 마을에서 토끼 두 마리가 서로 만나면 아무일도 일어나지 않는다. 하지만 토끼가 몬스터와 만나면 몬스터는 토끼를 잡아먹는다. 만약 몬스터 두 마리가 서로 만나면 싸우다가 둘 다 죽어버린다. 당신이 몬스터를 만나면 몬스터는 당신을 잡아먹어버린다. 하지만 당신을 몬스터를 해칠 수 없다. 또한 토끼는 당신을 해치지 못하지만, 당신은 토끼를 만나면 죽일수도, 살려둘 수도 있다. 이 마을의 거주자(당신과 토끼와 몬스터)들은 셋 이상이 동시에 만나는 경우는 없다고 가정한다. 또한 임의의 두 거주자가 마주칠 확률은 동일하다고 가정한다. 당신이 이 마을에서 죽지 않고 살아나갈 최대 확률을 구하시오. (M, B는 각각 0 이상 1000 이하이다.) [spoiler="더 보기..."]
• 문제 해법 동적 계획법으로 해결할 수 있는 문제입니다만, 문제의 트릭을 빨리 파악하신다면 좀 더 간단한 방법으로도 풀 수 있는 문제였습니다. 이 문제에서의 핵심 포인트는 "토끼는 대세에 영향을 미치지 못한다"라는 점입니다. 토끼는 아무리 많아도 괴물과 당신을 해칠 수 없습니다. (물론 서로 해칠수도 없지만요) 당신이 토끼를 만나서 토끼를 죽이던 죽이지 않던 당신이 살아남는 확률은 monster에만 영향을 받는다는 점입니다. 우선 M이 0인 경우 살아남을 확률은 1.0이라는 것을 알 수 있습니다. 또한 M이 1인 경우 당신은 살아남지 못한다(확률 = 0.0)는 것을 알 수 있습니다. M이 1보다 큰 경우, 임의로 두 유닛을 골랐을 때, 몬스터만 두 마리 골라질 확률을 구해봅시다. 당신과 M마리의 몬스터를 선택하는 경우의 수는 (M + 1) * M / 2가 됩니다. 여기에서 몬스터만 두 마리 골라지는 경우의 수는 M * (M - 1) / 2가 되지요. 몬스터와 당신이 선택되는 경우의 수는 M 가지가 되는 것이고요. table(i)를 i마리의 몬스터가 있을 때 당신이 살아남을 확률 이라고 정의합시다. 그러면 당신이 살아남을 확률 table(i)는 아래와 같습니다. table(i) = P{choose 2 monsters} * table(i - 2) + P{choose 1 monster and you} * 0.0 [/spoiler] 좀 더 정리하면 table(i) = (M - 1) / (M + 1) * table(i - 2) 가 되겠네요. 위의 점화식을 사용하면 쉽게 답을 구할 수 있습니다. 또한 위의 식을 풀어서 간단하게 나타내면 아래의 소스처럼 표현이 가능하지요. ~~~ cpp

struct MonstersAndBunnies {
double survivalProbability(int M, int B) {
if (M % 2 == 0) return 1.0 / (M + 1);
return 0.0;
}
};

물론 위의 방식대로 구현하지 않고, 2차원 동적 계획법으로도 풀 수 있습니다. (하지만 소스가 좀 더 길어지겠지요.)
 p.s) 제가 이 문제에서 챌린지로 275점을 획득하였는데, 확률 계산을 하는 과정에서 B가 영향을 주는 소스코드들에 {998, 999}라는 데이터를 넣어주었습니다 :)





 Medium (600 pts.)
* 문제 설명
 어떤 상자 안에 n개의 원소가 들어 있다. 각각의 원소는 0 이상의 정수이다. bag 안에 들어있는 원소의 순서는 중요하지 않다.
 A에서 0개 이상의 원소를 제거해서 B를 만들 수 있는 경우, "A는 B의 sub-bag"이라고 한다. 또한 bag의 무게는 bag에 들어있는 원소들의 합을 의미한다.
- example - 
 (1, 2, 1, 3, 1)인 bag과 (3, 1, 1, 1, 2)인 bag은 같은 상태이다. 하지만 (1, 2, 3, 3)인 bag은 다르다.
 (1, 2)와 (3, 1, 1)은 (1, 2, 1, 3, 1)의 sub-bag이지만, (1, 2, 2)는 sub-bag이 아니다.
 (1, 2, 1, 3, 1)인 bag의 weight는 8이다.
 무게가 소수(prime-number)인 sub-bag의 경우의 수를 구하시오.
[spoiler="더 보기..."]* 문제 해법
 knapsack 문제로 바꿔서 생각할 수 있습니다. 하지만 같은 원소가 여러 개 있는 경우를 잘 고려해야 겠지요.
 table[i]은 "무게가 i인 bag의 경우의 수"라고 정의합니다.
 그러면 table[i]는 무게가 a인 원소가 k개 있다면, table[i]는 table[i - a] + table[i - 2a] + ... + table[i - ka]의 합으로 나타낼 수 있지요.
 위의 점화식을 소스코드로 바꾸면 아래와 같습니다.
~~~ cpp

long long table[500001]; 
int bucket[10001]; 
int pprime[500001]; 
struct PrimeSums { 
  long long getCount(vector <int> bag) { 
    memset(pprime, 0, sizeof(pprime)); 
    for (long long i = 2; i <= 500000; ++i) { 
      if (pprime[i] == 0) { 
        for (long long j = i * i; j <= 500000; j += i)  
          pprime[j] = 1; 
      } 
    } 
    for (int i = 0; i < bag.size(); ++i)  
      bucket[bag[i]]++; 
    table[0] = 1; 
    int last = 0; 
    for (int i = 1; i <= 10000; ++i) { 
      if (bucket[i]) { 
        for (int j = last; j >= 0; --j) { 
          if (table[j] > 0) { 
            for (int k = 1; k <= bucket[i]; ++k)  
              table[j + k * i] += table[j]; 
          } 
        } 
        last += i * bucket[i]; 
      } 
    } 
    long long ret = 0; 
    for (int i = 2; i <= 500000; ++i)  
      if (pprime[i] == 0) ret += table[i]; 
    return ret * (bucket[0] + 1); 
  } 
};

[/spoiler]

Hard (900 pts.)

• 문제 설명 N이 두 자리 이상의 숫자일 때, magic(N)은 "인접한 digit의 차(0이상의 수)를 계산하여 차례대로 배열한 수"이다. 이 방법대로 진행하면 새로운 수를 얻을 수 있다. 앞에 0이 존재할 수 있는데, 존재한다면 앞의 0을 제외한 숫자가 된다. 예를 들어 magic(5913) = 482, magic(1198) = 081 = 81, magic(666) = 00 = 0이 된다. 어떤 숫자 N이 있으면 magic number를 반복하여 한 자리 수로 만들 수 있다. 여기에서 구한 한 자리 수를 N의 magic fingerprint라고 부른다. 5913 -> 482 -> 46 -> 2 이므로, 5913의 magic fingerprint는 2가 되는 것이다. magic fingerprint가 7이 되는 수는 매우 드물기 때문에, 이러한 수들을 lucky number라고 부른다. A이상 B이하의 수 중 lucky number가 몇 개 인지 구하는 프로그램을 작성하시오. A와 B는 1 이상 10^9 이하의 수이다. [spoiler="더 보기..."]* 문제 해법 제일 간단한 접근방법은 A부터 B까지 수의 magic fingerprint를 구해보는 것입니다. 하지만 이 경우 시간제한 (2s)을 초과하게 되지요. 그러면 발상을 거꾸로 하여 7에서부터 만들 수 있는 모든 magic fingerprint를 구하는 프로그램을 작성합시다. 7에서부터 만들 수 있는 두 자리 숫자는 07, 18, 29, 70, 81, 92가 있지요. 또한 세 자리 숫자는 07로부터, 18로부터, ..., 92로부터 만들어지는 숫자들이 되고요. [d1][d2][d3][d4]인 네 자리 숫자가 있다고 가정하면, 이 숫자로부터 만들어지는 다섯자리 숫자를 구하는 경우를 생각해 봅시다. 첫 digit가 1이라고 가정하면, 두 번째 자리의 수는 1 + d1이거나 1 - d1이 됩니다. 세 번째 자리의 수는 (두 번째 자리의 수) + d2이거나 (두 번째 자리의 수) - d2가 되고요. 같은 방법으로 네 자리의 숫자가 있고, 첫 digit가 고정되어 있으면 2^4가지의 수가 생깁니다. 하지만 각 자리는 음수가 될 수 없고, di가 0인 경우엔 더하나 빼나 같은 수이기 때문에 경우의 수는 확 줄어들게 됩니다. 자세한 내용은 아래 코드를 참조해 주시고, 궁금한 내용은 댓글로 남겨주시면 답변해 드리겠습니다 :-) ~~~ cpp

int ret = 0;
int A, B;
struct MagicFingerprint {
void go(vector num) {
if (num[0] != 0) {
int ss = 0;
for (int i = 0; i < sz(num); ++i)
ss = ss * 10 + num[i];
if ( A <= ss && ss <= B ) ret++;
}
if (sz(num) == 9) return;
vector next(sz(num) + 1, 0);
for (int i = 0; i < sz(num); ++i)

next[i + 1] = num[i];
go(next);
for (int i = 0; i <= 9; ++i) {
next[0] = i;
for (int j = 0; j < (1 << sz(num)); ++j) {
bool ispos = true;
for (int k = 0; k < sz(num); ++k) {
int bit = j & (1 << k);
if (bit) {
next[k + 1] = next[k] + num[k];
if (next[k + 1] > 9) {
ispos = false;
break;
}
} else {
next[k + 1] = next[k] - num[k];
if (num[k] == 0 || next[k + 1] < 0) {
ispos = false;
break;
}
}
}
if (ispos && next[0] != 0) go(next);
}
}
}
int countLuckyNumbers(int _A, int _B) {
A = _A, B = _B;
go(vector (1, 7));
return ret;
}
};

# 지정된 언어 [/spoiler]를 찾을 수 없습니다.
<div>[이 글은 과거 홈페이지에서 이전된 글입니다. <a href="http://algospot.andromeda-express.com/zbxe/editorial/45041">원문보기</a>]</div>