vi 모처럼 대박 났다..
500 이 보이는것처럼 그닥 쉬운문제는 아니었고..
250 도 나름 tricky 해서 fail 한 사람이 많았다..~
방 3등 전체 210등..  그리고 다시 yellow

근데.. 이번 SRM 이 511 인 덕분에 500점짜리가 FiveHundredEleven 이라는 문제가 나왔는데..
511 = 이진수 111111111 라는 점을 이용한 문제였다.. 이런 기가막힌 문제는 어떻게 만들어내는건지..





Level1 - Zoo

rabbit 과 cat 이 있고 같은 종 중에서 서로 자신의 키가 몇번째로 큰지에 대한 결과가 있다..
어떤게 rabbit 이고 어떤게 cat 인지 구분할 수 있는 경우의 수

일단 동물이 두가지 종류밖에 없으므로 같은 숫자가 3 이상 나오면 잘못된 경우이다..
작은 수부터 중간에 빼먹는 수 없이 차례로 2 개씩 나오다가 그다음 1개씩 나오다가 그 이후에는 0 만 나와야 한다..
즉, {0, 0, 1, 1, 2, 2, 3, 4, 5, ...} 뭐 이딴식으로 나와야 함..
sample I/O 가 부실해서 많은 사람이 fail 했다..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7 //#define min(x, y) ((x) > (y) ? (y) : (x))
  8 //#define max(x, y) ((x) > (y) ? (x) : (y))
  9 //#define INF 999999999
 10 //#define EPS 1e-14
 11
 12 class Zoo {
 13 public:
 14
 15 long long theCount(vector <int> ans)
 16 {
 17     int n;
 18     int i, fl;
 19     int cnt1, cnt2;
 20     int cnt[50];
 21     long long res;
 22     n = ans.size();
 23     memset(cnt, 0, sizeof(cnt));
 24     for (i = 0; i < n; i++) {
 25         cnt[ans[i]]++;
 26     }
 27     if (cnt[0] == 0) {
 28         return 0;
 29     }
 30     fl = 2;
 31     for (i = 0; i <= 40; i++) {
 32         if (cnt[i] == 2) {
 33             if (fl != 2)
 34                 return 0;
 35         }
 36         else if (cnt[i] == 1) {
 37             if (fl == 1 || fl == 2) ;
 38             else
 39                 return 0;
 40             fl = 1;
 41         }
 42         else if (cnt[i] == 0) {
 43             fl = 0;
 44         }
 45         else {
 46             return 0;
 47         }
 48     }
 49     cnt1 = cnt2 = 0;
 50     for (i = 0; i <= 40; i++) {
 51         if (cnt[i] == 2)
 52             cnt2++;
 53         else if (cnt[i] == 1)
 54             cnt1++;
 55     }
 56     res = 1;
 57     for (i = 0; i < cnt2; i++) {
 58         res *= 2;
 59     }
 60     if (cnt1)
 61         res *= 2;
 62     return res;
 63 }
 64
 65 };



Level2 - FiveHundredEleven

한사람씩 카드 한장을 뽑아 거기에 있는 수를 bitwise or 할때 마지막으로 511 을 만드는사람이 지는 게임..

game theory + memoization 으로 쉽게 풀 수 있을것 같다..
어떤 순서로 card 를 뽑느냐에 따라서 결과가 달라지므로..
상태공간은 2^n 이 된다..!!

그러나 어떤 순으로 조합하든 결국 memory 는 0~511 중에 하나가 된다는것을 감안하면
상태공간을 dramatic 하게 줄일 수 있는 방안이 있다..

자세한 내용은 코드에..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7 //#define min(x, y) ((x) > (y) ? (y) : (x))
  8 //#define max(x, y) ((x) > (y) ? (x) : (y))
  9 //#define INF 999999999
 10 //#define EPS 1e-14
 11
 12 int n;
 13 int memo[55][512];
 14 vector<int> num;
 15
 16 int is_win(int u, int mask)
 17 {
 18     int res;
 19     int i, cnt;
 20     if (mask == 511)
 21         return 1;
 22     if (u == n)
 23         return 0;
 24     if (memo[u][mask] != -1)
 25         return memo[u][mask];
 26     cnt = 0;
 27     for (i = 0; i < n; i++) {
 28         if ((mask & num[i]) == num[i])
 29             cnt++;
 30     }
 31     if (cnt > u) {
 32         res = is_win(u+1, mask);
 33         if (res == 0)
 34             return memo[u][mask] = 1;
 35     }
 36     for (i = 0; i < n; i++) {
 37         if ((mask & num[i]) != num[i]) {
 38             res = is_win(u+1, mask | num[i]);
 39             if (res == 0)
 40                 return memo[u][mask] = 1;
 41         }
 42     }
 43     return memo[u][mask] = 0;
 44 }
 45
 46 class FiveHundredEleven {
 47 public:
 48
 49 string theWinner(vector <int> cards)
 50 {
 51     int res;
 52     num = cards;
 53     n = cards.size();
 54     memset(memo, -1, sizeof(memo));
 55     res = is_win(0, 0);
 56     if (res)
 57         return "Fox Ciel";
 58     return "Toastman";
 59 }
 60
 61 };



Level3 - GameOfLifeDivOne


to be updated..




'Problem Solving > TopCoder logs' 카테고리의 다른 글

TCO13 Round 1C 생명연장 매치  (0) 2013.03.10
TCO12 R1A - 606등 -_-;;  (0) 2012.04.01
SRM 529  (0) 2012.01.15
SRM 521  (0) 2011.10.24
TCO11 R1 - 탈락  (0) 2011.06.23
SRM 509 !!  (0) 2011.06.09
SRM 507 - 나이스!  (0) 2011.05.30
TCO11 Qual2  (0) 2011.05.20
TCO11 Qual1  (2) 2011.05.15
SRM 504 - unrated event  (0) 2011.04.27

to Top