Hatena::Grouptopcoder

chokudaiの日記

 | 

2010-10-23

SRM 485 Div1 Medium RectangleAvoidingColoring

00:41 | SRM 485 Div1 Medium RectangleAvoidingColoring - chokudaiの日記 を含むブックマーク はてなブックマーク - SRM 485 Div1 Medium RectangleAvoidingColoring - chokudaiの日記 SRM 485 Div1 Medium RectangleAvoidingColoring - chokudaiの日記 のブックマークコメント

問題

省略

解説

5*5以上だと死ぬから、4以下だってわかって、それなら4C2*2bitでDPすればいいよねってだけ

public class RectangleAvoidingColoring {

    int lena, lenb;

    public long count(string[] board)
    {
        if (board.Length >= 5 && board[0].Length >= 5) return 0;
        if (board.Length > board[0].Length)
        {
            lena = board.Length;
            lenb = board[0].Length;
        }
        else
        {
            lenb = board.Length;
            lena = board[0].Length;
        }
        int[,] b = new int[lena, lenb];
        int i, j;
        for (i = 0; i < lena; i++)
        {
            for (j = 0; j < lenb; j++)
            {
                char c;
                if (board.Length > board[0].Length) c = board[i][j];
                else c = board[j][i];
                if (c == 'W') b[i, j] = 0;
                else if (c == 'B') b[i, j] = 1;
                else b[i, j] = 2;
            }
        }
        return count(b);
    }

    long count(int[,] board)
    {
        int i, j, k, l, m;

        int count = lenb * (lenb - 1) / 2;
        int[] numa = new int[count];
        int[] numb = new int[count];
        int temp = 0;
        for (i = 0; i < lenb; i++)
        {
            for (j = i + 1; j < lenb; j++)
            {
                numa[temp] = i;
                numb[temp] = j;
                temp++;
            }
        }
        long MAX = 1 << count;
        long[,] dp = new long[MAX, MAX];
        dp[0, 0] = 1;
        for (i = 0; i < lena; i++)
        {
            int black = 0;
            int white = 0;
            for (j = 0; j < lenb; j++)
            {
                if (board[i, j] == 0) white += (1 << j);
                if (board[i, j] == 1) black += (1 << j);
            }

            long[,] ndp = new long[MAX, MAX];
            for (j = 0; j < MAX; j++)
            {
                for (k = 0; k < MAX; k++)
                {
                    if (dp[j, k] == 0) continue;
                    for (l = 0; l < (1 << lenb); l++)
                    {
                        if ((white & l) != 0) continue;
                        if ((black & l) != black) continue;
                        long nexta = j;
                        long nextb = k;
                        for (m = 0; m < count; m++)
                        {
                            if (bit(l, numa[m]) == 0 && bit(l, numb[m]) == 0)
                            {
                                if (((nexta >> m) & 1) == 1) break;
                                else nexta += (1 << m);
                            }
                            if (bit(l, numa[m]) == 1 && bit(l, numb[m]) == 1)
                            {
                                if (((nextb >> m) & 1) == 1) break;
                                else nextb += (1 << m);
                            }
                        }
                        if (m != count) continue;
                        ndp[nexta, nextb] += dp[j, k];
                    }
                }
            }
            dp = ndp;
        }
        long res = 0;
        for (j = 0; j < MAX; j++)
        {
            for (k = 0; k < MAX; k++)
            {
                res += dp[j, k];
            }
        }
        return res;
    }

    int bit(int num, int a)
    {
        return ((num >> a) & 1);
    }
}
 |