SRM525 Div2 Hard(950) 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; }};