SRM 525 DIV2 950 MagicalSquare

DPで解く問題。どのような状態を保持するかが悩ましかった。最初、dp[r][i][j][k]としてr行目まで見たときに、各カラムが先頭からi, j, k文字まで埋まっている場合のパターン数を保持するようにした。しかしよく考えると、kはi, jが決まれば一意にきまるので、dp[r][i][j]とした。

　計算量は、(行数 4) * (カラムの埋まっている文字 50^2) * (現在注目している行の文字の分割パターン 50^2) * (文字列比較 50)であやしかったけど、投げてみる。TLE。ループの中にbreakを入れて枝狩りをしてみる。Accept。

　んー、通ったものの、計算量はもう一段階落ちると思う。文字列の比較をハッシュとか使ってやればいいのかなー。Editorialに期待します。

view plainprint?

1. long long int dp[4][51][51];  
2.   
3. class MagicalSquare {  
4. public:  
5.     long long int getCount(vector<string> rowStrings, vector<string> columnStrings) {  
6.         memset(dp, 0, sizeof(dp));  
7.   
8.         vector<string> rows(4);  
9.         rows[0] = "";  
10.         REP(i, rowStrings.size()) rows[i+1] = rowStrings[i];  
11.   
12.         dp[0][0][0] = 1;  
13.         int rLen[4];  
14.         int cLen[3];  
15.   
16.         REP(i, 4) rLen[i] = rows[i].length();  
17.         REP(i, 3) cLen[i] = columnStrings[i].length();  
18.   
19.         if (rLen[1] + rLen[2] + rLen[3] != cLen[0] + cLen[1] + cLen[2])  
20.             return 0;  
21.   
22.         int s = 0;  
23.         REP (r, 3) {  
24.             s += rLen[r];  
25.             REP (i, cLen[0]+1) REP(j, cLen[1]+1) {  
26.                 if (!dp[r][i][j]) continue;  
27.   
28.                 int k = s - i - j;  
29.   
30.                 REP(p, rLen[r+1]+1) {  
31.                     string s1 = rows[r+1].substr(0, p);  
32.                     if (columnStrings[0].substr(i, s1.length()) != s1) break;  
33.   
34.                     FOR (q, p, rLen[r+1]+1) {  
35.                         string s2 = rows[r+1].substr(p, q-p);  
36.                         string s3 = rows[r+1].substr(q);  
37.   
38.                         if (columnStrings[1].substr(j, s2.length()) != s2) break;  
39.                         if (columnStrings[2].substr(k, s3.length()) != s3) continue;  
40.   
41.                         dp[r+1][i+s1.length()][j+s2.length()] += dp[r][i][j];  
42.                     }  
43.                 }  
44.             }  
45.         }  
46.   
47.         return dp[3][cLen[0]][cLen[1]];  
48.     }  
49. };  

long long int dp[4][51][51];

class MagicalSquare {
public:
    long long int getCount(vector<string> rowStrings, vector<string> columnStrings) {
        memset(dp, 0, sizeof(dp));

        vector<string> rows(4);
        rows[0] = "";
        REP(i, rowStrings.size()) rows[i+1] = rowStrings[i];

        dp[0][0][0] = 1;
        int rLen[4];
        int cLen[3];

        REP(i, 4) rLen[i] = rows[i].length();
        REP(i, 3) cLen[i] = columnStrings[i].length();

        if (rLen[1] + rLen[2] + rLen[3] != cLen[0] + cLen[1] + cLen[2])
            return 0;

        int s = 0;
        REP (r, 3) {
            s += rLen[r];
            REP (i, cLen[0]+1) REP(j, cLen[1]+1) {
                if (!dp[r][i][j]) continue;

                int k = s - i - j;

                REP(p, rLen[r+1]+1) {
                    string s1 = rows[r+1].substr(0, p);
                    if (columnStrings[0].substr(i, s1.length()) != s1) break;

                    FOR (q, p, rLen[r+1]+1) {
                        string s2 = rows[r+1].substr(p, q-p);
                        string s3 = rows[r+1].substr(q);

                        if (columnStrings[1].substr(j, s2.length()) != s2) break;
                        if (columnStrings[2].substr(k, s3.length()) != s3) continue;

                        dp[r+1][i+s1.length()][j+s2.length()] += dp[r][i][j];
                    }
                }
            }
        }

        return dp[3][cLen[0]][cLen[1]];
    }
};