[algospot] GENIUS

문제링크 입니다

[GENIUS] 문제 😭😭😭😭😭

MP3 플레이어에 들어 있는 곡들을 전부 셔플 모드로 들을 때 최대의 문제점은 서로 어울리지 않는 노래들이 갑자기 나올 수 있다는 것입니다. 끈적한 애시드 재즈를 듣고 있다가 갑자기 시끄러운 데스 메탈이 나오는 것만큼 분위기를 깨는 것도 없지요. 때문에 전세계에서 가장 잘 나가는 MP3 플레이어를 생산하는 오렌지 사에서는 이번에 지니어스라는 기능을 출시했습니다. 지니어스는 MP3 플레이어에 들어 있는 곡들을 셔플 모드로 들을 때 잘 어울리는 것끼리 순서대로 재생되도록 해 줍니다.

태윤이는 오렌지 사의 새 MP3 플레이어를 산 뒤 재미로 지니어스의 동작 원리를 분석해 보았습니다. 지니어스를 사용하면 한 곡 다음에 다음 곡이 재생될 확률은 두 곡의 유사도에 따라 결정됩니다. 태윤이는 MP3 플레이어에 담긴 음악들 간의 유사도를 조사해, i 번 곡 다음에 j 번 곡이 재생될 확률을 나타내는 확률 행렬 T 를 만들었습니다.

태윤이는 방금 재생 버튼을 눌러 0번 곡을 듣기 시작했습니다. K 분 30초가 지난 후 태윤이가 좋아하는 곡이 재생되고 있을 확률은 얼마일까요? MP3 플레이어에 들어 있는 곡들의 길이는 모두 1분, 2분, 3분 혹은 4분입니다.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 MP3 플레이어에 들어 있는 곡의 수 N (1 <= N <= 50 ) 과 K (1 <= K <= 1,000,000) , 그리고 태윤이가 좋아하는 곡의 수 M (1 <= M <= 10) 이 주어집니다. 그 다음 줄에는 N 개의 정수로 각 곡의 길이 Li 가 분 단위로 주어지고, 그 후 N 줄에는 한 곡이 재생된 후 다음 곡이 재생될 확률을 나타내는 행렬 T 가 주어집니다. T 의 i 번 줄의 j 번 숫자 (0 <= i,j < N) T[i,j] 는 i 번 곡이 끝난 뒤 j 번 곡을 재생할 확률을 나타냅니다. T 의 각 행의 합은 1 입니다. 각 테스트 케이스의 마지막 줄에는 M 개의 정수로 태윤이가 좋아하는 곡의 번호 Qi 가 주어집니다.

출력

각 테스트 케이스마다 한 줄로 태윤이가 좋아하는 M 개의 곡에 대해 각 곡이 재생되고 있을 확률을 출력합니다. 10^-7 이하의 절대/상대 오차가 있는 답은 정답으로 인정됩니다.

입력 예제

3
3 6 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 10 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 1000 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

출력 예제

0.42360000 0.49660000 0.07980000
0.31060929 0.13791635 0.26756048 0.28391388
0.18648004 0.28409359 0.42243515 0.10699122

전체 코드는 다음과 같습니다.

//
//  GENIUS.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/10/14.
//


#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream fin("GENIUS.txt");

int N; // MP3 플레이어에 들어 있는 곡의 수 1<= <=50
int K; // K 분 30초 의 1<= <=1000000
int M; // 태윤이가 좋아하는 곡의 수 1<= <=10
int L[51]; // N개의 곡의 길이 1<= <=4;
double T[51][51]; // i번 곡이 끝난 뒤 j번 곡이 재생할 확률

class Matrix{
private:
    vector<vector <double> > v;
    int m_size;
public:
    Matrix(int n, vector<vector<double >> v2) : m_size(n){
        v.resize(m_size, vector<double>(m_size,0));
        for(int i=0; i<m_size; i++){
            for(int j=0; j<m_size; j++){
                v[i][j] = v2[i][j];
            }
        }
    };
    Matrix(int n) : m_size(n){
        v.resize(m_size, vector<double>(m_size,0));
    };

    Matrix Identity(){
        Matrix result(m_size);
        for(int i=0; i<m_size; i++){
            for(int j=0; j<m_size; j++){
                if(i==j) result.v[i][j] = 1;
                else result.v[i][j] = 0;
            }
        }
        return result;
    };

    Matrix operator*(Matrix &M){
        Matrix result(m_size);
        for(int i=0; i< m_size; i++){
            for(int j=0; j< m_size; j++){
                for(int k=0; k< m_size; k++){
                    result.v[i][j] += (v[i][k] * M.v[k][j]);
                }
            }
        }
        return result;
    };

    Matrix pow(int k){
        if(k == 0) return Identity();
        Matrix result(m_size);
        // 홀
        if(k % 2 == 1) return pow(k-1)**this;
        Matrix half = pow(k/2);
        return half*half;
    };

    double *operator[](int i){
        return &v[i][0];
    }

    void PrintMatrix(){
        for(int i=0; i<m_size; i++){
            for(int j=0; j<m_size; j++){
                cout << v[i][j] << " ";
            }
            cout << endl;
        }
    }
};

vector<double> getProb2(){
    //start(time-3, 0) ~ start(time-3, N-1)
    //start(time-2, 0) ~ start(time-2, N-1)
    //start(time-1, 0) ~ start[time-1, N-1)
    //start(time  , 0) ~ start(time  , N-1).
    Matrix W(N*4);
    // 첫 3*n의 원소는 그대로 복사해 온다.
    // 이해가 정말 안됬는데 이렇게 하니 좀 되었음..
    // NOOX start(time-3) -> (time-2 + time-1 + time)
    // NNOX start(time-2) -> (time-1 + time);
    // NNNX start(time-1) -> (time);
    // XXXX start(time  ) -> (time분 후 곡이 불러질 확률을 구한다. T를 이용해서 );
    for(int i=0; i<3*N; i++)
        W[i][i+N] = 1.0;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            W[3*N+i][(4-L[j])*N +j] = T[j][i];
        }
    }
    Matrix Wk = W.pow(K);

    vector<double> result(N);
    //song번 노래가 재생되고 있을 모두 확률을 계산한다.
    for(int song=0; song<N; song++){
        //song 번 노래가 시작했을 시간을 모두찾아 결과에 저장한다.
        for(int start=0 ; start<L[song] ; start++){
            result[song] += Wk[(3-start)*N + song][3*N];
        }
    }
    return result;

}
int main(int argc, const char * argv[]) {
    int test_case;
    fin >> test_case;

    for(int i = 0; i < test_case; i++){
        fin >> N >> K >> M;
        for(int j=0; j<N; j++){
            fin >> L[j];
        }
        for(int j=0; j<N; j++){
            for(int k=0; k<N; k++){
                fin >> T[j][k];
            }
        }

        vector<double> result = getProb2();
        for(int j=0; j<M; j++){
            int Song;
            fin >> Song;
            printf("%.8f ",result[Song]);

        }
        cout << endl;
    }
    return 0;
}