TopCoder TCO08 Qualification Round 1

Problem Solving/TopCoder logs 2008. 2. 6. 13:15

사용자 삽입 이미지
처음해보는 TCO.. 처음엔 좀 많이 긴장했는데.. 한문제만 풀자는 생각으로 침착하게 임했다.. 약간 아쉬움이 남긴 하지만.. 그럭저럭 무난했다.. 아침 11시에 열리는 매치라 좀 부담스러웠는데.. 밤을 샌 덕분에(?) 비교적 좋은 컨디션을 유지한것같다.. 이로써 TCO08 Qual Round는 얼떨결에가뿐하게 통과했다.. rating도 조금 상승하고..

이번 퀄 라운드1은 우승자가 한국인이다!!! 우아.. 나는 언제 우승해보나.. div2에서라도 한번 해보고싶다. ㅠ_ㅠ

이번 매치는 떡밥이 좀 많았는데도 불구하고 챌린지를 또 실패하고 말았다.. ㅠ_ㅠ;; 완벽한 먹이감을 하나 발견하긴했지만.. 다른놈이 먼저하고말았다.. 젠장!!! 다들 코딩만 빠른게아니라 챌도 빠르다.. ㅠ_ㅠ;;

흠.. 근데 이거 한문제씩만 풀어가지고는 한계가 있는데.. 빨리 실력을 쌓아서 두문제 이상풀던가.. 아니면 챌을 많이하던가.. 해야할텐데..;; 음.. 오늘도 600을 끈질기게 잡고 풀었으면 어땠을까 하는 생각이 든다.. 900 코딩하다 안드로메다 가고.. 막판 5분을 남기고 600점짜리 DP 솔루션이 번뜩 떠올랐는데.. 아쉬비..

방 7등 전체 253등 (대략 1100여명 참여)

사용자 삽입 이미지
250점 문제는 2번째로 빨리풀었군.. 그냥 내 나름대로 간단하게 생각해서 풀었는데 red및 yellow들도 다 잘 못풀고있어서 마지막 순간까지 내 솔루션을 의심할수밖에 없었다.. 음.. 근데 우리방에 딱 한명있는 저 red는 점수가 왜저렇지.. 600을 포기하고 900을 열었군..  -_-;;


[250] MonstersAndBunnies

마을에 M마리의 monster와 B마리의 bunny와 내가 산다.. bunny끼리 만날때는 아무일이없고.. monster끼리 만날때는 둘이 싸우다 죽는다.. monster는 bunny나 사람을 만나면 죽인다.. 모든 생물체는 한순간에 한쌍만 마주친다. 내가 죽지않으면서 죽을 위험이 없어질 확률을 구하는 문제..

아.. 첫문제부터 나의 취약분야중 하나인 확률이 나와서 당황..!!! 그래도 나름대로 해법을 잘 찾아낸것 같다..

1) 우선 이 문제에서 bunny는 결과에 영향을 주지 않는다.. 그냥 무시!!
2) monster개수가 홀수이면 결국 하나는 살아남기때문에 답은 0
3) (monster끼리 만날 경우의수) / (monster + 나 중에서 두 생물체가 만날 경우의수) 가 monster끼리 싸우다 죽는 확률이 된다..

3)의 사건이 발생하면 monster가 2마리씩 죽게되고.. 이 과정을 0마리가 될때까지 반복하면 된다. 풀고나서도 그닥 확신이 않섰던 문제..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 int nC2(int n)
  9 {
 10     int res;
 11     res = n * (n-1);
 12     res /= 2;
 13     return res;
 14 }
 15
 16 class MonstersAndBunnies {
 17 public:
 18
 19 double survivalProbability(int M, int B)
 20 {
 21     int a, b;
 22     double res;
 23     if (M & 1)
 24         return 0.0;
 25     if (M == 0)
 26         return 1.0;
 27     res = 1.0;
 28     while (M) {
 29         a = nC2(M);
 30         b = nC2(M+1);
 31         res *= (double)a / (double)b;
 32         M -= 2;
 33     }
 34 printf("res = %lf\n", res);
 35     return res;
 36 }
 37
 38 };





[600] PrimeSums

주어진 bag (multiset이라고 생각하면 된다)의 sub-bag 중 원소의 합이 prime이 되는 sub-bag의 개수를 구하는 문제..

이 문제는 동전교환문제의 변형정도로 생각해서 DP로 풀면 될듯하다.. 문제는 중복제거와 0에 대한 특별처리 정도.. 이문제를 끝까지 잡았으면 풀었으려나..? 못풀었으려나..?

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 int is_prime[500001];
  9 long long dp[500001];
 10 void sieve()
 11 {
 12     int i, j;
 13     memset(is_prime, -1 ,sizeof(is_prime));
 14     is_prime[1] = is_prime[0] = 0;
 15     for (i = 2; i <= 500000; i++) {
 16         if (is_prime[i]) {
 17             for(j = 2; i*j <= 500000; j++)
 18                 is_prime[i*j] = 0;
 19         }
 20     }
 21 }
 22
 23 class PrimeSums {
 24 public:
 25
 26 long long getCount(vector <int> bag)
 27 {
 28     int n;
 29     int i, j, k;
 30     int cnt[10001];
 31     long long sum, res;
 32
 33     sieve();
 34     memset(cnt, 0, sizeof(cnt));
 35     memset(dp, 0, sizeof(dp));
 36     n = bag.size();
 37     sum = 0;
 38
 39     for (i = 0; i < n; i++) {
 40         cnt[bag[i]]++;
 41         sum += bag[i];
 42     }
 43     dp[0] = 1 + cnt[0];
 44     for (i = 1; i <= 10000; i++) {
 45         if (cnt[i] == 0)
 46             continue;
 47         for (j = sum; j-i >= 0; j--) {
 48             for (k = 1; k <= cnt[i]; k++) {
 49                 if (j - (i*k) >= 0)
 50                     dp[j] += dp[j-i*k];
 51             }
 52         }
 53     }
 54     res = 0;
 55     for (i = 2; i <= sum; i++) {
 56         if (is_prime[i] && dp[i] != 0) {
 57             res += dp[i];
 58         }
 59     }
 60 printf("res = %lld\n", res);
 61     return res;
 62
 63 }
 64
 65 };





[900] MagicFingerprint

magic이란 연산은 임의의 수를 이웃하는 digit끼리의 차로 이루어진 새로운 수로 변환한다.. magic 연산을 계속 반복하면 결국 한자리 수가 되는데 그 수가 7이 되는 수를 lucky number라고 한다. A와 B사이의 수 중 lucky number의 개수 구하기..

이 문제를 푼사람 중에 정말 어이없게도 1부터 10억까지 미리 다돌려서 lucky number를 다 찍어놓은다음에.. 그 수를 수동으로 다 입력시켜놓은 사람도 있었다.. 아..!! 나는 왜 그런방법조차 생각을 못했지..????

to be updated..

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

흠냥.. 탑코더 SRM 393 참여 실패.. -_-;;  (0) 2008.03.12
TopCoder SRM 392 Div2  (0) 2008.03.07
TopCoder SRM 391 Div1  (0) 2008.02.27
TopCoder TCO08 Online Round 1  (2) 2008.02.17
TopCoder TCO08 Qualification Round 3(3A)  (0) 2008.02.15
TopCoder SRM 390 Div1  (2) 2008.02.03
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
  • By helloneo

to Top

티스토리툴바