어제 새벽 1시에 열렸던 매치.. 흑.. 통한의 리서밋 덕분에.. 점수가 폭락했다.. ㅠ_ㅠ
이번엔 나름 솔루션을 빨리 떠올려서 210점대에 서밋 완료했는데..
한참후에 초기화 안한걸 발견.. 리서밋.. -_-;; 덕분에 또 div2로 떨어졌다..;;;;
500점은 상당히 까다로웠고.. 1000점은 열어보지도 않음..

사용자 삽입 이미지


Level1 - PrimeSoccer

more..

축구 경기가 90분이라고 할때 시작부터 5분마다 양 팀이 골을 넣을 수 있는 확률이 percentage로 주어진다.. 각 5분 간격에 최대 넣을 수 있는 골은 최대 1골이라고 가정.. (즉, 최대 넣을 수 있는 골은 18골이 됨) 이때, 양 팀중 최소 한팀이라도 넣은 골의 수가 prime일 확률 구하기..

간단하게 DP로 풀었다.
dp[i][j] = i번째 period에 j골을 넣을 확률이라고 하면..
dp[i][j] = dp[i-1][j] * (이번에 골을 못넣을 확률) + dp[i-1][j-1] * (이번에 골을 넣을 확률)
이 된다.

그리고 나서 inclusion exclusion principle에 의해서..
A팀이 prime 골을 기록할 확률 + B팀이 prime 골을 기록할 확률에서 두 팀 모두 prime 골을 기록할 확률을 빼면 된다.

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 int is_prime(int u)
  9 {
 10     int i;
 11     if (u < 2)
 12         return 0;
 13     for (i = 2; i < u; i++) {
 14         if (u % i == 0)
 15             return 0;
 16     }
 17     return 1;
 18 }
 19
 20 class PrimeSoccer {
 21 public:
 22
 23 double getProbability(int A, int B)
 24 {
 25     int i, j;
 26     double dp[20][20], dp2[20][20];
 27     double sum;
 28     memset(dp, 0, sizeof(dp));
 29     memset(dp2, 0, sizeof(dp2));
 30     dp[0][0] = 1.0;
 31     for (i = 1; i <= 18 ; i++) {
 32         dp[i][0] = dp[i-1][0] * (1.0 - ((double)A / 100.0));
 33         for (j = 1; j <= 18; j++) {
 34             dp[i][j] = dp[i-1][j] * (1.0 - ((double)A / 100.0));
 35             dp[i][j] += dp[i-1][j-1] * (double)A / 100.0;
 36         }
 37     }
 38     dp2[0][0] = 1.0;
 39     for (i = 1; i <= 18 ; i++) {
 40         dp2[i][0] = dp2[i-1][0] * (1.0 - ((double)B / 100.0));
 41         for (j = 1; j <= 18; j++) {
 42             dp2[i][j] = dp2[i-1][j] * (1.0 - ((double)B / 100.0));
 43             dp2[i][j] += dp2[i-1][j-1] * (double)B / 100.0;
 44         }
 45     }
 46     sum = 0.0;
 47     for (i = 2; i <= 18; i++) {
 48         if (is_prime(i)) {
 49             sum += dp[18][i];
 50             sum += dp2[18][i];
 51         }
 52     }
 53     for (i = 2; i <= 18; i++) {
 54         for (j = 2; j <= 18; j++) {
 55             if (is_prime(i) && is_prime(j)) {
 56                 sum -= dp[18][i] * dp2[18][j];
 57             }
 58         }
 59     }
 60 printf("%lf\n", sum);
 61     return sum;
 62 }
 63
 64 };



Level2 - CavePassage

more..

여행객들이 동굴을 지나가야한다.. 지도는 단 하나이고 지도 없이는 동굴을 지나갈 수 없다. 여러명이 그룹을 지어 동굴을 통과하게 된다.. 동굴 안에 다리가 있는데.. 특정 무게 이상이 한번에 지나갈 수 없다.. 사람들끼리 서로 trust하는 사람이 있다.. 같이 가는 그룹중에 최소 한명이라도 trust하는 사람이 있어야.. 같은 그룹으로 갈 수 있다.. 사람마다 걷는 속도가 있고.. 같은 그룹일 경우 가장 느린사람 속도에 맞춰서 지나게 된다.. 등등..

이문제는 여러모로 유명한 문제인데 한때 구글 입사 면접문제로도 알려진 UVa 10037 - Bridge 문제를 여러가지 제약조건을 두어서 더 복잡하게 꼬아놨다.. 젠장!!!


to be updated..



Level3 - WorkersOnPlane

more..




to be updated..

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

TopCoder SRM 434 Div 1  (0) 2009.02.10
TopCoder SRM 432 Div 1  (0) 2009.01.07
TopCoder SRM 428 Div 1  (0) 2008.12.03
탑코더 스름 426 디비젼 1  (0) 2008.11.25
TopCoder SRM 425 Div 2 (완료)  (0) 2008.11.13
TopCoder SRM 422 Div 1  (4) 2008.10.19
TopCoder SRM 421 Div 1  (0) 2008.10.12
TopCoder SRM 420 Div 2  (0) 2008.10.03
TopCoder SRM 418 Div 2  (0) 2008.09.21
TopCoder SRM 417 Div 2  (0) 2008.09.13
TopCoder SRM 416 Div2  (0) 2008.09.07

Comments

  1. mynotepad 2008.10.20 09:49 신고 Permalink Modify/Delete Reply

    PrimeSoccer 를 나는 2^18 가지수의 부분집합 문제로 풀었는데..
    이런 DP 해법도 있었구먼..

  2. Radient 2008.10.23 03:07 신고 Permalink Modify/Delete Reply

    저도 nCr로 Pascal 삼각형의 계수 구해서 확률에 곱하는걸로;;

    아마 소요자형이랑 거의 비슷한게 푼것 같아요...

    500번은 정말 지옥같은 제약조건들 때문에.....

Leave a Comment


to Top