TopCoder Open 2011 시작!!
작년에 TCO10 때 휴가까지 쓰고 참가했는데도 불구하고 Qual round 도 통과못한 아쉬움이 있었는데..
올해도 상황을 보니 작년과 비슷하게 진행되고 있다.. -_- 
맞았다고 생각한 500 이 의외로 fail 하면서 637 등.. 간발의 차이로 탈락했다.. 젠장!!!!
500 이 fail 한 이유는 특정 케이스에 대해서 TLE 가 나는거였는데.. 나와 같은 이유로 fail 한 사람이 많았다..
이런 xx 같은 경우가 다 있다니..!!







Level1 - MinimumLiars

더보기


i번째 사람이 liar 라면 claim[i] 는 전체 liar 수보다 크고, i번째 사람이 liar 가 아니라면 claim[i] 는 전체 liar 수보다 작거나 같다.. 최소 가능한 liar 수 구하기

liar 수를 0 ~ n 까지 넣고 시도해보았다..

  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 MinimumLiars {
 13 public:
 14
 15 int getMinimum(vector <int> claim)
 16 {
 17     int n;
 18     int i, j;
 19     int cnt;
 20     n = claim.size();
 21     for (i = 0; i <= n; i++) {
 22         cnt = 0;
 23         for (j = 0; j < n; j++) {
 24             if (claim[j] <= i) {
 25             }
 26             else {
 27                 cnt++;
 28             }
 29         }
 30         if (cnt == i) {
 31             return i;
 32         }
 33     }
 34     return -1;
 35 }
 36
 37 };




Level2 - FoxListeningToMusic

더보기


각 음악의 재생 길이가 나오고.. random play 를 할때, T+0.5 초 순간에 i 번째 음악이 play 될 확률 구하기..

전형적인 DP 로 풀었다..
P[i][j] = i 초에 j 음악이 play 될 확률이라고 놓고 풀었다..

최악의 경우 loop 가 2억번 돌아서 약간 불안했는데.. tc 를 50개 다 넣어봐도 잘 돌아가길래 submit
근데 특정 case 에서 fail 했다.. ㅠ_ㅠ;
double 값이 너무 작아지면 연산 속도가 갑자기 떨어지는 것 같다.. ㅠ_ㅠ;; (링크
그래서 너무 작은값이 나올때 무시하고 돌렸다..
문제 출제자.. 이건 좀 너무하잖아!!

  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 tt;
 14 double P[100001][51];
 15
 16 class FoxListeningToMusic {
 17 public:
 18
 19 vector <double> getProbabilities(vector <int> length, int T)
 20 {
 21     int i, j, k;
 22     int temp;
 23     double p;
 24     vector<double> res;
 25     n = length.size();
 26     tt = T;
 27     p = 1.0 / (double)n;
 28     for (i = 0; i < n; i++) {
 29         res.push_back(0);
 30     }
 31     for (i = 0; i <= T; i++) {
 32         for (j = 0; j < n; j++) {
 33             P[i][j] = 0.0;
 34         }
 35     }
 36     for (i = 0; i < n; i++) {
 37         if (length[i] > T)
 38             res[i] += p;
 39         else
 40             P[length[i]][i] = p;
 41     }
 42     for (i = 1; i <= T; i++) {
 43         for (j = 0; j < n; j++) {
 44             temp = i+length[j];
 45             for (k = 0; k < n; k++) {
 46                 if (P[i][k] > 1e-15) {
 47                     if (temp > T)
 48                         res[j] += P[i][k] * p;
 49                     else
 50                         P[temp][j] += P[i][k] * p;
 51                 }
 52             }
 53         }
 54     }
 55     return res;
 56 }
 57
 58 };





Level3 - SquareSeries

더보기



to be updated..



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

SRM 511  (0) 2011.07.04
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
SRM 503 흑흑 ㅠ_ㅠ;;  (0) 2011.04.18
SRM 501  (0) 2011.04.01
SRM 498 - WTF!!  (0) 2011.02.27
SRM 496  (2) 2011.02.02

Comments

  1. kureyo 2011.05.16 17:24 신고 Permalink Modify/Delete Reply

    안녕하세요, 오랜만이에요 :)
    사실 med같은 경우는 O(TNN)이 아니라 O(TN)솔루션이 있어서 그걸로 풀라는게 아니었을지;;
    저는 반대로 TNN에 T=80000,N=50으로 챌린지 시도하다가 실패했네요. ㅠㅠ
    TCO서버가 애매하게 좋아져서(?) 특수한 데이타에서 걸리나봐요.

Leave a Comment


to Top