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분 이후에 확률이 수렴하는지 체크했습니다.

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

~~~ c++
#include
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