모처럼 에디토리얼을 쓰는 아스탱입니다 -ㅁ- (그동안 성적이 안좋아서 ㅠㅠ)

• Easy (250 pts)

  • 문제설명 혼자서도 할 수 있는 카드게임이 있습니다. 처음에는 몇 개의 덱에 카드들이 놓여져 있습니다. 그 후 각 덱에서 한 장씩의 카드를 선택하여 새로운 덱에 위치시킵니다. 이 카드놀이는 몇번 이상 반복하면 똑같은 상태가 유지되어 매우 지루하다는 사실을 깨닫게 됩니다. 초기 상태가 주어졌을 때, 임의의 step X와 step X+S의 카드가 같은 최소한의 S를 구하시오. (즉, 같은 상태가 반복될 때, 그 주기를 구하라는 문제입니다.) [spoiler="풀이보러가기"]
  • 문제풀이 카드가 최대 50장으로 제한되어 있으므로 경우의 수가 얼마 없습니다 :D (실제로 계산해보진 않았지만..) 따라서 Brute-Force하게 일일이 해도 풀리는 문제이지요. 일단 {3,1,3}과 {1,3,3}이 같은 상태이므로 (예제 참조) 결국에는 어떤 상태가 입력으로 주어질 때, 이를 소트해도 같은 상태라는 것을 알 수 있습니다. 이렇게 소트하는 이유는 중복체크를 보다 편하게 하기 위해서이지요. 저는 중복체크를 map을 이용하여 해결하였습니다. 이런 류의 문제에서는, key값을 vector 으로 하면 사용하기가 편하거든요. (물론 데이터가 크다면 속도...문제를 유의해야 합니다.) ~~~ cpp

#define all(x) (x).begin(),(x).end()
map, int> mheap;
struct SolitaireSimulation {
int periodLength(vector heaps) {
sort(all(heaps));
mheap[heaps] = 0;
int now = 0;
while (true)
{
now++;
vector nheap;
nheap.push_back(heaps.size());
for (int i = 0; i < heaps.size(); ++i)
if (heaps[i] > 1) nheap.push_back(heaps[i] - 1);
sort(all(nheap));
heaps = nheap;
if (mheap.count(heaps) > 0)
return now - mheap[heaps];
mheap[heaps] = now;
}
return -1;
}
};

[/spoiler]



 - Medium (500 pts)

  * 문제설명
  빨간 카드 R장과 검은 카드 B장이 임의로 섞여 있습니다. 카드를 한 장 뽑았는데, 빨간카드가 나오면 1$를 받게 되고, 검은카드가 나오면 1$를 잃게됩니다. 게임을 계속하거나 그만두는 것은 당신의 의지에 달려 있습니다. 당신이 최선을 다해 게임을 진행할 때, 최대 얼마만큼의 수익을 올릴 수 있는지 구하는 프로그램을 작성하세요.
[spoiler="풀이보러가기"]  * 문제풀이
  전형적인 Dynamic Programming 문제입니다. table[i][j]를 빨간카드가 i장, 검은카드가 j장 있을때의 최대 기대값이라고 정의합시다. 그러면 점화식은 아래와 같이 나오게 됩니다.
  table[i][j] = i / (i + j) * (1 + table[i - 1][j])    /// 빨간 카드가 나올 확률 * 빨간 카드가 나왔을 때의 기대값
                   + j / (i + j) * (table[i][j - 1] - 1)    /// 검은 카드가 나올 확률 * 검은 카드가 나왔을 때의 기대값
  단, table[i][j]는 최소 0이상이 됩니다. 만약 0보다 작게된다면 게임을 그만두는것이 최선의 방법이니까요.
  문제에서 약간 tricky[?]한 점은 array size입니다. 보통 이런 경우에는 2 * 5000 배열을 잡거나 5000짜리 1차원 배열을 두개 잡아서 shift하는 방식을 자주 사용합니다. 현재 상태의 값을 구하기 위해서는 바로 이전 상태의 값만 알아도 되거든요. 사실 1차원 배열 하나만 가지고도 이 문제를 풀 수 있긴 합니다 :D. 저는 2 x 5000 배열을 잡아서 상호참조하는 방법을 사용하였습니다. 
~~~ cpp

double table[2][5001]; 
struct RedIsGood { 
   double getProfit(int R, int B) { 
      memset(table, 0, sizeof(table));
      for (int i = 1; i <= R; ++i) 
      { 
         int a = i & 1, b = 1 - a; 
         table[a][0] = i; 
         for (int j = 1; j <= B; ++j) 
         { 
            table[a][j] = 0.0; 
            double p = (i * 1.0 / (i + j)) * (table[b][j] + 1) + (j * 1.0 / (i + j)) * (table[a][j - 1] - 1); 
            table[a][j] >?= p; 
         } 
      } 
      return table[R & 1][B]; 
   } 
}; 

~~~[/spoiler]



 - Hard (1000 pts)

  * 문제설명
  Change-O-Matic은 돈을 바꿔주는 기계입니다. 이 기계는 수표나 동전을 넣으면, 그것보다 작은 단위의 동전들로 바꿔줍니다. (물론 수수료는 없기 때문에 처음에 넣은 돈과 같은 돈을 줍니다.)
  Change-O-Matic이 동전을 바꿔주는 규칙은 아래와 같습니다. 우선 이 기계에는 아주 많은 동전이 쌓여있습니다. 내부적으로 동전을 찍어내는 시스템이 있기 때문에 절대로 동전이 부족한 상황은 없다고 가정할 수 있습니다.[의역] 이 기계에 세팅되어 있는 동전은 int[] outputValue로 주어집니다. 항상 1원짜리 동전은 outputValue에 포함됩니다. 우리의 최종목표는 inputValue의 돈을 1원짜리 동전을 바꾸는 것입니다.
  당신은 1원보다 큰 동전(혹은 수표)를 이 기계에 넣으려고 합니다. 이 기계의 AI는 어떤 동전(혹은 수표)가 들어왔을 때, "최소한의 동전의 개수를 돌려주는" 일을 하고 있습니다. 만약에 동전의 개수가 같다면 "lexicographically maximal "을 선호합니다. 즉 큰 가치를 가지는 동전을 최대한 돌려줍니다. 100+11+9보다는 100+12+8이 더 maximal하다고 볼 수 있지요. 아래는 문제에 정의된 lexicographically large의 definition입니다.
[spoiler="더 보기..."]Let A=(a1,...,aN) and B=(b1,...,bN) be two different but equally large sets of coins, with a1 >= a2 >= ... >= aN and b1 >= b2 >= ... >= bN. Let x be the smallest index such that ax != bx. If ax > bx, we say that the set A is lexicographically larger than the set B.
[/spoiler]
   동전은 최대 50가지의 종류로 이루어져 있으며, 처음에 당신이 가지고 있는 수표는 2원부터 10^15원 사이의 금액입니다.
[spoiler="풀이보러가기"]
  * 문제풀이
  우선 작은 문제에서부터 해결하도록 하지요. 수표의 범위가 100만 이하일 때를 풀어봅시다. (저는 대회때는 101만으로 잡았지만요.)
~~~ cpp

///  table[i] => i원짜리 수표를 기계에 넣었을 때, 리턴하는 최소 동전 수. 
      for (int i = 0; i <= 1010000; ++i) table[i] = i; 
      for (int i = 1; i < n; ++i) 
      { 
         for (int j = outputValues[i]; j <= 1010000; ++j) 
         { 
            table[j] <?= table[j - outputValues[i]] + 1; 
         } 
      }

기본 상태는 1원짜리 동전만 return하는 것이기 때문에 table[i] = i로 세팅을 해 줍니다. 그 다음부터 outputValues[i]원짜리를 사용해서 더 적은 동전을 사용할 수 있는지 확인하여 갱신합니다. {참고로 a <?= b는 a = min(a, b)와 같은 연산입니다. } 또한 초기에 outputValues값에서 inputValue이상의 동전들을 배제하면, 올바른 답을 구할 수 있지요. (배제하지 않는다면 대참사가 발생합니다 ㅠㅠ 예제가 안나올꺼에요 :D)
그러면 이제 이 테이블을 가지고 작은 inputValue에 대해 답을 역추적해보도록 하겠습니다. 예제데이터인 {1, 5, 10}, inputValue = 21을 가지고 설명하겠습니다.
1) 1원짜리 동전이 있다면? 변환할 필요가 없습니다.
2) 5원짜리 동전이 있다면, 우리는 거스름돈으로 {1}만을 리턴한다는 사실을 알 수 있죠. 따라서 1번의 변환이 필요합니다.
3) 10원짜리 동전이 있을 때, {1, 5}의 거스름돈을 사용합니다. table[9]와 table[5] 중 작은쪽을 택하게 되겠지요. 만약 두 값이 같다면, 우리는 lexicographically larger 조건에 의해 5의 동전을 사용하고, table[5]를 참조하게 됩니다. 10원짜리 동전을 바꾸면 {5개, 1개}로 변환이 될 것이고, 1원짜리는 0번, 5원짜리는 1번 변환해야 하므로 총 2번의 변환이 필요하게 됩니다. { 10원->5원x1+1원x5 -> 1원x10 }
4) 21원짜리 수표가 있을 때, {1, 5, 10}의 거스름돈을 사용할 수 있습니다. 위에서와 같이 table[20], table[16], table[11]을 볼 수 있습니다. 셋을 비교했을 때 제일 좋은 경우는 table[11]이 되고, 이를 반복하면 21원짜리 수표를 넣었을 때 {1개, 0개, 2개}를 리턴합니다. 21원짜리 수표를 넣으면 5번의 변환이 필요하게 되겠네요.
일단 inputValue가 작은때는 위의 step으로 진행합니다. 말은 길게 썼지만 결론만 간단히 말하면, bottom-up 방식이랄까요.. 작은돈부터 차례대로 계산해 나가는 방식이죠.
inputValue가 큰 경우에는 아래의 소스코드에서 사용했듯이 100만 이하가 될때(제 소스에선 100만5천이지만요) 까지는 제일 큰 동전을 변환한다고 두었습니다. 자세한 증명은 코드 밑에 첨부합니다. :$ 제가 이 값을 100만이라고 가정한 이유는, {1, 999, 1000}이고 997002의 데이터가 입력으로 주어진다면, 첫 턴에 999*998로 바꿔주는 것이 1000*997 + 1*2보다 적은 동전을 주기 때문이지요.

int table[1010001]; 
vector <vector <long long> > info; 
long long turn[55]; 
vector <long long> getSolution(long long v, vector<int> elem) 
{ 
   vector <long long> ret(elem.size(), 0); 
   if (v > 1010000) 
   { 
      long long t = (v - 1005000) / elem.back(); 
      ret[elem.size() - 1] = t; 
      v -= t * elem.back(); 
   } 
   while (v) 
   { 
      int remain = 9999999; 
      int p = -1; 
      for (int i = 0; i < elem.size(); ++i) 
      { 
         if (v >= elem[i] && remain >= table[v - elem[i]]) 
         { 
            remain = table[v - elem[i]]; 
            p = i; 
         } 
      } 
      ret[p]++; 
      v -= elem[p]; 
   } 
   return ret; 
} 
struct ChangeOMatic { 
   long long howManyRounds(vector <int> _outputValues, long long inputValue) { 
      // 필요없는 원소들은 지운다.
      vector <int> outputValues; 
      for (int i = 0; i < _outputValues.size(); ++i) 
      { 
         if (_outputValues[i] < inputValue) 
            outputValues.push_back(_outputValues[i]); 
      } 
      int n = outputValues.size(); 
      info.assign(n, vector <long long> (n, 0)); 
      for (int i = 0; i <= 1010000; ++i) table[i] = i; 
      for (int i = 1; i < n; ++i) 
      { 
         for (int j = outputValues[i]; j <= 1010000; ++j) 
         { 
            table[j] <?= table[j - outputValues[i]] + 1; 
         } 
      } 
      vector <long long> elem; 
      info[0][0] = 1; turn[0] = 0; 
      for (int i = 1; i < n; ++i) 
      { 
         elem.pb(outputValues[i - 1]); 
         info[i] = getSolution(outputValues[i], elem); 
         turn[i] = 1; 
         for (int j = 0; j < info.size(); ++j) 
         { 
            turn[i] += info[i][j] * turn[j]; 
         } 
      } 
      elem.pb(outputValues.back()); 
      vector <long long> ret = getSolution(inputValue, elem); 
      long long rr = 1; 
      for (int j = 0; j < ret.size(); ++j) 
         rr += ret[j] * turn[j]; 
      return rr; 
   } 
}; 

[ Hard - 왜 100만까지는 제일 큰 동전을 사용하면 되는지 증명하기 ]
Let M = outputValues.back() // 제일 큰 동전 이라고 정의하면
A[i][j] : i * M + j 원을 i+1개의 동전만을 사용하여 만들 수 있는가? 로 정의할 수 있습니다. ( 0 <= j < M )
그리고 위의 A는 2차원이므로, 이를 1차원으로 변환한 Set S[i]를 정의합니다. S[i] : { A[i][j] = TRUE를 만족하는 모든 j 의 set }
집합 S를 잘 살펴보면, S[0] = outputValues 라는 것을 알 수 있습니다. 또한 S[0] ⊆ S[1] ⊆ S[2] ⊆ S[3] ... 이라는 것도 찾을 수 있지요. S[i - 1] ⊆ S[i] 가 되는 이유는, (i-1) * M + j원을 i개의 동전으로 만들었다면, 여기에서 M원짜리 동전을 사용하면 i*M+j원을 (i+1)개의 동전으로 만들 수 있기 때문입니다.
즉 | S[0] | = outputValues.size() 가 되고, | S[0] | ≤ | S[1] | ≤| S[2] | 이며, | S[x] | 의 최대값은 M이기 때문에, 결국에는 x <= M 이전에 수렴한다는 사실을 알 수 있습니다. S[x]에서 수렴했다는 말은, "S[x+1] -> S[x]로 가기 위해서는 M원짜리 동전을 사용하면 된다." 를 의미합니다. 즉 100만 이상의 경우에는 항상 M을 사용해도 최적해가 나온다는 뜻이 됩니다.
[/spoiler]