SRM525 Div2 Hard(950) MagicalSquare

MagicalSquare

S[0][0], S[0][1], S[1][0], S[1][1]を決めれば、残りのマスも定まる。事前にrowStrings, columnStringsのそれぞれの位置からの最長一致長を求めて高速化する。

#include <string>
#include <vector>
using namespace std;

class MagicalSquare{public:
long long getCount( vector <string> rowStrings, vector <string> columnStrings )
{
    int R[3], C[3];
    for ( int i=0; i<3; i++ )
        R[i] = (int)rowStrings[i].length(),
        C[i] = (int)columnStrings[i].length();

    vector<vector<int> > L[3][3];
    for ( int i=0; i<3; i++ )
    for ( int j=0; j<3; j++ )
    {
        L[i][j] = vector<vector<int> >( R[i], vector<int>( C[j] ) );
        for ( int x=0; x<R[i]; x++ )
        for ( int y=0; y<C[j]; y++ )
            for ( int t=0;
                  x+t<R[i] && y+t<C[j] &&
                  rowStrings[i][x+t]==columnStrings[j][y+t];
                  t++ )
                L[i][j][x][y]++;
    }

    int ans = 0;

    int S[3][3];
    for ( S[0][0]=0; S[0][0]<=50; S[0][0]++ )
    for ( S[0][1]=0; S[0][1]<=50; S[0][1]++ )
    for ( S[1][0]=0; S[1][0]<=50; S[1][0]++ )
    for ( S[1][1]=0; S[1][1]<=50; S[1][1]++ )
    {
        for ( int i=0; i<2; i++ )
            S[2][i] = C[i] - S[0][i] - S[1][i];
        for ( int i=0; i<3; i++ )
            S[i][2] = R[i] - S[i][0] - S[i][1];

        bool f = true;
        for ( int i=0; i<3; i++ )
        for ( int j=0; j<3; j++ )
            if ( S[i][j]<0 )
                f = false;
        if ( S[0][2]+S[1][2]+S[2][2] != C[2] )
            f = false;
        if ( !f )
            continue;
        
        for ( int i=0; i<3; i++ )
        for ( int j=0; j<3; j++ )
        {
            int ox = 0;
            for ( int k=0; k<j; k++ )
                ox += S[i][k];
            int oy = 0;
            for ( int k=0; k<i; k++ )
                oy += S[k][j];

            if ( S[i][j]!=0 && L[i][j][ox][oy]<S[i][j] )
                f = false;
        }

        if ( f )
            ans++;
    }

    return ans;
}};