Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-09-20

MatArith

| 21:03

問題文, TCI '02 Round 2

Algorithm Tutorials -- Planning an Approach to a TopCoder Problem: Section 1から。

行列同士の足し算と掛け算。

169.75/500 (1 failed)

typedef long long int64;

class MatArith {
public:
    vector <string> calculate(vector <string> A, vector <string> B, vector <string> C, string equation) {
        return print(calc(parse(A),parse(B),parse(C),equation));
    }
private:
    vector<string> print(vector<vector<int64> > M) {
        const int R = M.size();
        if (R == 0) return vector<string>();
        const int C = M[0].size();
        vector<string> ret(R);
        for (int r = 0; r < R; r++) {
            ostringstream oss;
            for (int c = 0; c < C; c++) {
                if (c >= 1) oss << " ";
                oss << M[r][c];
            }
            ret[r] = oss.str();
        }
        return ret;
    }
    vector<vector<int64> > parse(vector<string>& M) {
        const int R = M.size();
        vector<vector<int64> > ret(R);
        for (int r = 0; r < R; r++) {
            istringstream iss(M[r]);
            int t;
            while (iss >> t) ret[r].push_back(t);
        }
        return ret;
    }
    vector<vector<int64> > calc(const vector<vector<int64> > A,
            const vector<vector<int64> > B, const vector<vector<int64> > C,
            const string& equation) {
        stack<vector<vector<int64> > > matStack;
        int opStack = 0;
        for (int i = 0; i < equation.size(); i++) {
            if (equation[i] == '+') {
                opStack++;
            } else if (equation[i] == '*') {
                vector<vector<int64> > T1 = matStack.top(); matStack.pop();
                i++;
                vector<vector<int64> > T2;
                if (equation[i] == 'A') T2 = A;
                else if (equation[i] == 'B') T2 = B;
                else  T2 = C;
                vector<vector<int64> > M = matmul(T1, T2);
                if (M.size() == 0) return M;
                matStack.push(M);
            } else if (equation[i] == 'A') {
                matStack.push(A);
            } else if (equation[i] == 'B') {
                matStack.push(B);
            } else {
                matStack.push(C);
            }
        }
        while (opStack-- > 0) {
            vector<vector<int64> > T1 = matStack.top(); matStack.pop();
            vector<vector<int64> > T2 = matStack.top(); matStack.pop();
            vector<vector<int64> > M = matadd(T1, T2);
            if (M.size() == 0) return M;
            matStack.push(M);
        }
        return matStack.top();
    }
    vector<vector<int64> > matmul(const vector<vector<int64> >& A,
            const vector<vector<int64> >& B) {
        const int RA = A.size(), CA = A[0].size();
        const int RB = B.size(), CB = B[0].size();
        if (CA != RB) return vector<vector<int64> >();
        vector<vector<int64> > M(RA, vector<int64>(CB,0));
        for (int i = 0; i < RA; i++) {
            for (int j = 0; j < CB; j++) {
                for (int k = 0; k < CA; k++) {
                    M[i][j] += A[i][k] * B[k][j];
                }
                if (M[i][j] > 2147483647ll || M[i][j] < -2147483648ll)
                    return vector<vector<int64> >();
            }
        }
        return M;
    }
    vector<vector<int64> > matadd(const vector<vector<int64> >& A,
            const vector<vector<int64> >& B) {
        const int RA = A.size(), CA = A[0].size();
        const int RB = B.size(), CB = B[0].size();
        if (RA != RB || CA != CB) return vector<vector<int64> >();
        vector<vector<int64> > M(RA, vector<int64>(CA,0));
        for (int i = 0; i < RA; i++) {
            for (int j = 0; j < CA; j++) {
                M[i][j] += A[i][j] + B[i][j];
                if (M[i][j] > 2147483647ll || M[i][j] < -2147483648ll)
                    return vector<vector<int64> >();
            }
        }
        return M;
    }
};