GENIUS 소스 분석좀 해주실 분...

  • cjkis
    cjkis

    #include
    #include
    #include
    #include
    #include
    #include
    #include
    using namespace std;
    
    
    struct SquareMatrix {
        int N;
        vector > v;
        SquareMatrix(int _N);
        ~SquareMatrix();
        static SquareMatrix identity(int N);
        SquareMatrix operator * (const SquareMatrix& rhs) const;
        SquareMatrix pow(int n) const;
        double* operator [] (int idx);
    };
    
    SquareMatrix::SquareMatrix(int _N) {
        N = _N;
        v.resize(N, vector(N, 0));
    }
    
    SquareMatrix::~SquareMatrix() {
    }
    
    SquareMatrix SquareMatrix::identity(int N) {
        SquareMatrix ret = SquareMatrix(N);
        for(int i = 0; i < N; i++) ret.v[i][i] = 1;
        return ret;
    }
    
    SquareMatrix SquareMatrix::operator * (const SquareMatrix& rhs) const {
        assert(N == rhs.N);
    
        SquareMatrix ret = SquareMatrix(N);
        for(int k = 0; k < N; k++)
            for(int i = 0; i < N; i++)
                for(int j = 0; j < N; j++)
                    ret.v[i][j] += v[i][k] * rhs.v[k][j];
        return ret;
    }
    
    SquareMatrix SquareMatrix::pow(int n) const {
        if(n == 0) return identity(N);
        if(n % 2 > 0) return (*this) * pow(n-1);
        SquareMatrix half = pow(n/2);
        return half * half;
    }
    
    double* SquareMatrix::operator [] (int idx) {
        return &v[idx][0];
    }
    
    
    int n, k, length[50];
    double T[50][50];
    
    vector getProb1() {
        // c[time][song] = time분 후에 song번 노래가 시작할 확률
        double c[5][50];
    
        memset(c, 0, sizeof(c));
        c[0][0] = 1.0;
        for(int time = 1; time <= k; ++time) 
            for(int song = 0; song < n; ++song) {
                double& prob = c[time % 5][song];
                prob = 0;
                for(int last = 0; last < n; last++) 
                    prob += c[(time - length[last] + 5) % 5][last] * T[last][song];
            }
        vector ret(n);
        // song번 노래가 재생되고 있을 확률을 계산한다
        for(int song = 0; song < n; song++) 
            // song번 노래가 시작했을 시간을 모두 찾아 더한다
            for(int start = k-length[song]+1; start <= k; start++) 
                ret[song] += c[start % 5][song];
        return ret;
    }
    
    // k분 30초 후에 각 곡이 재생되고 있을 확률을 반환한다
    vector getProb2() {
        SquareMatrix W(4*n);
        // 첫 3*n개의 원소는 그대로 복사해온다
        for(int i = 0; i < 3*n; ++i) 
            W[i][i+n] = 1.0;
        // 마지막 n개의 원소는 이전 원소들의 선형 결합으로 이루어진다
        for(int i = 0; i < n; ++i) 
            // C[time+1][i] = C[time+1-length[j]][j] * T[j][i];
            for(int j = 0; j < n; ++j) 
                W[3*n+i][(4-length[j])*n+j] = T[j][i];
    
        SquareMatrix Wk = W.pow(k);
        vector ret(n);
        // song번 노래가 재생되고 있을 확률을 계산한다
        for(int song = 0; song < n; ++song) 
            // song번 노래가 시작했을 시간을 모두 찾아 더한다
            for(int start = 0; start < length[song]; ++start)
                ret[song] += Wk[(3-start)*n+song][3*n];
        return ret;
    }
    
    bool eq(double a, double b) {
        return fabs(a-b) <= 1e-7;
    }
    
    int main(int argc, char* argv[]) {
        bool verify = (argc > 1) && (strcmp(argv[1], "verify") == 0);
        int cases;
        scanf("%d", &cases);
        for(int cc = 0; cc < cases; ++cc) {
            int m;
            scanf("%d %d %d", &n, &k, &m);
            for(int i = 0; i < n; i++) scanf("%d", &length[i]);
            for(int i = 0; i < n; i++) {
                double rowSum = 0;
                for(int j = 0; j < n; j++) {
                    scanf("%lf", &T[i][j]);
                    rowSum += T[i][j];
                }
                if(!eq(1.0, rowSum)) {
                    printf("rowsum(%d) = %.8lf\n", i, rowSum);
                }
            }
    
            vector sol2 = getProb2();
    
            if(verify) {
                vector sol1 = getProb1();
                for(int i = 0; i < n; i++) 
                    if(!eq(sol1[i], sol2[i])) {
                        printf("Case %d\n", cc);
                        for(int j = 0; j < n; j++) 
                            printf("sol1[%d] = %.8lf, sol2[%d] = %.8lf\n", 
                                    j, sol1[j], j, sol2[j]);
                        return 0;
                    }
            }
            for(int i = 0; i < m; i++) {
                int song;
                scanf("%d", &song);
                printf("%s%.8lf", (i ? " " : ""), sol2[song]);
            }
            printf("\n");
        }
    }
    

    vector<double> getProb1() {
        // c[time][song] = time분 후에 song번 노래가 시작할 확률
        double c[5][50];
    
        memset(c, 0, sizeof(c));
        c[0][0] = 1.0;
        for(int time = 1; time <= k; ++time) 
            for(int song = 0; song < n; ++song) {
                double& prob = c[time % 5][song];
                prob = 0;
                for(int last = 0; last < n; last++) 
                    prob += c[(time - length[last] + 5) % 5][last] * T[last][song];
            }
        vector<double> ret(n);
        // song번 노래가 재생되고 있을 확률을 계산한다
        for(int song = 0; song < n; song++) 
            // song번 노래가 시작했을 시간을 모두 찾아 더한다
            for(int start = k-length[song]+1; start <= k; start++) 
                ret[song] += c[start % 5][song];
        return ret;
    }
    

    알고리즘 책 보면서 하고 있는데요 도저히 이해가...

    스포일러는 전체소스고 바로 보이는 C++소스가 제가 궁금한 함수 부분인데요..

    크게 위의 for문과 아래 for문이 있는데요
    위의 for문에서 c[5][50]의 값을 끝까지 구했는데요
    그럼 아래 for문에서 그냥 c[time%5][song]의 값이 답이 되는 것 아닌가요? 왜 다시 더해주는건지 잘 모르겠네요

    주석 보면 'c[time][song] = time분 후에 song번 노래가 시작할 확률' 이라고 되어 있으니 time과 song이 10과 3이라면 10분 후에 3번 노래가 시작할 확률은 그냥 c[time%5][3]아닌가요?

    그리고 첫번째 for문에서 time이 1부터 k까지인 경우의 확률을 순서대로 구하면서 마지막시간-0 ~ 마지막시간-4 인 경우의 확률을 c에 저장 되는 것 같은데 맞나요?
    즉 마지막시간인 k가 되기 전의 5가지 경우만 저장되는거 같은데 맞죠??


    5년 전
2개의 댓글이 있습니다.
  • nosiar
    nosiar

    time분 후에 song번 노래가 시작할 확률이 아니라 time분 후에 song번 노래가 재생되고 있을 확률을 구하는 거네요


    5년 전 link
  • cjkis
    cjkis

    아 ㄳㄳ 콩사진님


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