오늘 아침 11시에 있었던 매치.. 역시.. 이번에도 고전했다.. ㅠ_ㅠ 이번에도 두문제를 풀기는했는데.. rating은 오히려 떨어졌다.. 헐.. 이제는 두문제를 풀어도 못올라가는것인가.. ㅠ_ㅠ;; Div2에 참여했던 한국사람들은 다들 선전했다.. 와.. 다들 대단..~! 내가 거의 최하위권.. ;; 이번셋은 별로 tricky하지 않고 떡밥도 별로 없어서 챌린지도 많지 않았다.. 문제를 얼마나 빨리 푸느냐에 따라서 대체로 승부가 갈렸다..

흠.. 중간에 내 개인 코딩서버가 맛탱이가 가는바람에.. 문제풀던 도중 다른 서버로 갈아타는 불상사가.. ㅠ_ㅠ 덕분에 코딩시간이 좀더 길어졌다.. ㅠ

근데 dma_timer_expiry (??) 는 또 뭔 에러지.. 드디어 나의 서버가 맛탱이가 갔구나.. ㅠ_ㅠ

방 8등 전체 161등


사용자 삽입 이미지
250점 resubmit..  500점은 문제이해하는데 오래걸리고.. ㅠ_ㅠ;;

사용자 삽입 이미지
두문제 풀고도 떨어지다니.. 젱장..



[250] Prank
input으로 apparentGain 이 주어지고.. x^2 - y^2 = apparentGain 을 만족하는 양의정수 x를 구하기..

y를 1에서부터 다 돌렸다.. upper bound를 어디에 두어야할지 몰라서 대충 50000이라고 했는데.. 다풀고나서 한참 후에 왠지 불안해서 1000000으로 고치고 resubmit 했다.. 흠.. 나중에 테스트를 해보니 y가 50000이 넘는 경우가 없는것같다.. 젠장.. 괜히 resubmit했다.. ㅠ_ㅠ

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 #include <cmath>
      7 using namespace std;
      8
      9 class Prank{
     10 public:
     11
     12 vector<int> realWeight(int g)
     13 {
     14     long long prev, cur, temp;
     15     vector<int> res;
     16     for (prev = 1; prev <= 1000000; prev++) {
     17         temp = g+prev*prev;
     18         cur = (long long)sqrt((double)temp);
     19         if (cur*cur == temp) {
     20 printf("prev = %lld, cur = %lld..\n", prev, cur);
     21             res.push_back(cur);
     22         }
     23     }
     24 printf("\n");
     25     return res;
     26 }
     27
     28 };




[500] Library
도서관에 document들이 있는데 이 document를 접근할 수 있는 group과 document가 있는 room에 접근할 수 있는 권한이 주어진다.. 사용자의 group 권한과 room 권한이 주어질때 접근할 수 있는 document의 개수 구하기..

문제를 이해하는데 오래걸린 문제.. 각 document에 대해서 사용자가 가지고있는 group권한, room 권한인지를 체크한다.. 나같은경우 set을 이용하여 비교하였고.. linear search를 해도 된다.. 매우 쉬운문제..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <map>
  7 #include <set>
  8 using namespace std;
  9
 10 class Library {
 11 public:
 12
 13 int documentAccess(vector <string> records, vector<string> userGroups, vector<string> roomRights)
 14 {
 15     int i;
 16     char buf[10000], doc[100], group[100], room[100];
 17     set<string> g, r, res;
 18     for (i = 0; i < userGroups.size(); i++) {
 19         g.insert(userGroups[i]);
 20     }
 21     for (i = 0; i < roomRights.size(); i++) {
 22         r.insert(roomRights[i]);
 23     }
 24     for (i = 0; i < records.size(); i++) {
 25         strcpy(buf, records[i].c_str());
 26         sscanf(buf, "%s%s%s", doc, room, group);
 27         if (r.find(room) == r.end())
 28             continue;
 29         if (g.find(group) == g.end())
 30             continue;
 31         res.insert(doc);
 32     }
 33     return res.size();
 34 }
 35
 36 };




[1000] PowerGame
두개의 수가 주어지고.. 각각의 수에서 n^2 꼴의 수를 뺄 수 있다.. 뺄수 없으면 지는겨우.. 두 사람이 각각 최적의 전략(최대한 빨리이기거나 이길수없으면 최대한 늦게 지거나)으로 play할때 처음 시작하는 사람이 몇번만에 이길지.. 이길수없다면 몇번만에 지는지.. 구하는 문제..

그동안 게임이론에 관한 포스팅만 실컷 해놓고.. 정작 게임이론 문제가 나왔는데 못풀었다.. ㅠ_ㅠ
역시.. 게임은 어려워.. ㅠ_ㅠ;;;

아.. 드디어 해결..~! 다른사람 코드를 참조해서 풀었다.. 기본적인 nim game의 이론을 적용해서 풀고.. 몇번만에 이기는지(지는지)를 따로 기억해둔다.. 구현은 깔끔하게.. recursion + memorization으로..

참고자료:  Game Theory

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7 #define INF 99999999
  8 #define min(x, y) ((x) > (y) ? (y) : (x))
  9 #define max(x, y) ((x) > (y) ? (x) : (y))
 10
 11 char is_sq[10001];
 12 int state[10001];
 13 int cnt[10001];
 14
 15 int recur(int u)
 16 {
 17     int i;
 18     int temp, fl;
 19     int max1, min1;
 20
 21     if (state[u] != 0)
 22         return state[u];
 23     if (u == 0) {
 24         cnt[u] = 0;
 25         return -1;
 26     }
 27     if (is_sq[u]) {
 28         cnt[u] = 1;
 29         return 1;
 30     }
 31     min1 = INF;
 32     max1 = 0;
 33     fl = 0;
 34     for (i = 1; i*i <= u; i++) {
 35         temp = recur(u-i*i);
 36         if (temp == -1) {
 37             fl = 1;
 38             min1 = min(min1, cnt[u-i*i]+1);
 39         }
 40         else if (temp == 1) {
 41             max1 = max(max1, cnt[u-i*i]+1);
 42         }
 43     }
 44     if (fl) {
 45         cnt[u] = min1;
 46         return 1;
 47     }
 48     cnt[u] = max1;
 49     return -1;
 50 }
 51
 52 class PowerGame {
 53 public:
 54
 55 string winner(int size0, int size1)
 56 {
 57     int i;
 58     char ret[100];
 59     memset(is_sq, 0, sizeof(is_sq));
 60     for (i = 1; i <= 100; i++) {
 61         is_sq[i*i] = 1;
 62     }
 63     memset(state, 0, sizeof(state));
 64     for (i = 0; i <= 10000; i++) {
 65         state[i] = recur(i);
 66     }
 67
 68     if (cnt[size0] < cnt[size1]) {
 69         if (state[size0] == 1)
 70             sprintf(ret, "Alan will win after %d moves", cnt[size0]);
 71         else
 72             sprintf(ret, "Bob will win after %d moves", cnt[size0]);
 73     }
 74     else if (cnt[size0] > cnt[size1]) {
 75         if (state[size1] == 1)
 76             sprintf(ret, "Alan will win after %d moves", cnt[size1]);
 77         else
 78             sprintf(ret, "Bob will win after %d moves", cnt[size1]);
 79     }
 80     else {
 81         if (state[size0] == 1 && state[size1] == 1)
 82             sprintf(ret, "Alan will win after %d moves", cnt[size1]);
 83         else
 84             sprintf(ret, "Bob will win after %d moves", cnt[size1]);
 85     }
 86     return ret;
 87 }
 88
 89 };


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

TopCoder SRM 389 Div1  (0) 2008.01.25
TopCoder SRM 388 Div1  (2) 2008.01.16
TopCoder SRM 387 Div1  (4) 2008.01.10
TopCoder SRM 386 Div 2  (4) 2008.01.06
TopCoder SRM 385 Div2 (완료)  (4) 2007.12.30
TopCoder SRM 383 Div 2 (완료)  (0) 2007.12.14
TopCoder SRM382 DIV2  (2) 2007.12.13
TopCoder SRM381 DIV2 (완료)  (2) 2007.12.09
TopCoder SRM380 DIV2 (완료)  (0) 2007.12.08
TopCoder SRM 379 Div2 (완료)  (0) 2007.11.29

to Top