GENIUS 질문입니다

  • jsk
    jsk

    GENIUS 문제 질문입니다.
    다음과 같이 생각하고 풀었는데 어디가 틀렸는지 봐주시면 감사하겠습니다..

    p(i, t)를 i번 곡이 t분 후 시작할 확률이라 하면,

    p(i, t) = sum(p(j,t-l_j)*A_ji,1<=j<=N)

    가 되므로 k분 후까지 모든 확률을 계산 하는데 O(kN^2)이 걸립니다.

    그랬더니 시간초과가 나와서 다시 생각해보니, 확률이 수렴하는 경우에는 굳이 k분 후까지 계산할 필요가 없어서,

    현재 시간에서 4분 전까지 모든 확률이 같을 때(<0.0000000001) 멈추게 만들었습니다.

    각 곡의 길이가 최대 4분이므로 최근 5분동안 N개의 곡이 나올 확률이 시간에 상관없이 같다면, 수렴하기 때문이라고 생각했습니다.

    초반부 확률은 1, 0, 0 등으로 주어지므로 100분 이후에 확률이 수렴하는지 체크했습니다.

    맨 아래에 제가 사용했던 테스트케이스를 적어놓았습니다.

    #include<stdio.h>
double ab(double x){
    return (x<0.0)?(-x):x;
}
int main(){
    int tc, i, j, j2, j3, n, k, m, l[50], q[10], c, d;
    double t[50][50], p[50][5], ans;
    scanf("%d", &tc);
    for(i=0;i<tc;i++){
        scanf("%d %d %d", &n, &k, &m);
        for(j=0;j<n;j++)
            scanf("%d", &l[j]);
        for(j=0;j<n;j++)
            for(j2=0;j2<n;j2++)
                scanf("%lf", &t[j][j2]);
        for(j=0;j<m;j++)
            scanf("%d", &q[j]);

        for(j=0;j<n;j++){
            for(j2=0;j2<5;j2++)
                p[j][j2] = 0.0;
        }
        p[0][0] = 1.0;
        for(j=1;j<=k;j++){
            c = 0;
            for(j2=0;j2<n;j2++){
                p[j2][j%5] = 0.0;
                for(j3=0;j3<n;j3++){
                    p[j2][j%5] += p[j3][((j-l[j3])%5<0)?(j-l[j3])%5+5:(j-l[j3])%5]*t[j3][j2];
                }
                if(j>100){
                    d = 0;
                    for(j3=1;j3<5;j3++){
                        if(ab(p[j2][j%5]-p[j2][(j-j3)%5])<0.0000000001)
                            d++;
                    }
                    if(d==4)
                        c++;
                }
            }
            if(c==n)
                break;
        }
        for(j=0;j<m;j++){
            ans = 0.0;
            for(j2=0;j2<l[q[j]];j2++)
                ans += p[q[j]][((k-j2)%5<0)?(k-j2)%5+5:(k-j2)%5];
            printf("%.10lf ", ans);
        }
        printf("\n");
    }
    return 0;
}

    10
    1 1 1
    1
    1
    0
    1 1000 1
    4
    1
    0
    3 1000000 3
    4 4 2
    0.18 0.40 0.42
    0.15 0.46 0.39
    0.58 0.23 0.19
    0 1 2
    4 1000000 4
    1 3 2 4
    0.26 0.07 0.49 0.18
    0.21 0.33 0.15 0.31
    0.41 0.20 0.38 0.01
    0.28 0.31 0.18 0.23
    2 0 3 1
    4 1000000 4
    4 3 4 4
    0.08 0.47 0.12 0.33
    0.10 0.02 0.39 0.49
    0.08 0.33 0.35 0.24
    0.14 0.19 0.58 0.09
    1 3 2 0
    3 1000000 3
    4 4 2
    1 0 0
    0 1 0
    0 0 1
    0 1 2
    2 1000000 2
    1 2
    1 0
    0 1
    0 1
    4 1000000 4
    4 3 3 2
    1 0 0 0
    0 1 0 0
    0 0 1 0
    0 0 0 1
    1 2 3 0
    4 1000000 4
    4 4 4 4
    0.99 0.01 0 0
    0.99 0 0.01 0
    0.99 0 0 0.01
    0 0 0 1
    0 1 2 3
    10 1000000 10
    1 2 3 4 1 2 3 4 1 2
    0 0 0 1 0 0 0 0 0 0
    0 0 1 0 0 0 0 0 0 0
    1 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 1 0 0 0 0
    0 1 0 0 0 0 0 0 0 0
    0 0 0 0 1 0 0 0 0 0
    0 0 0 0 0 0 0 0 1 0
    0 0 0 0 0 0 1 0 0 0
    0 0 0 0 0 0 0 1 0 0
    0 0 0 0 0 0 0 0 0 1
    0 1 2 3 4 5 6 7 8 9


    9년 전
1개의 댓글이 있습니다.
  • JongMan
    JongMan

    1번 뒤에는 무조건 2번, 2번 뒤에는 무조건 3번, 그 뒤에는 무조건 4번, 4번 뒤에는 1번.. 이렇게 빙빙 돈다면 어떨까요? :-)


    9년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.