Hatena::Grouptopcoder

chokudaiの日記

 | 

2010-10-23

SRM 485 Div1 Easy AfraidOfEven

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

問題

偶数怖い人が等差数列を割りまくる。元の数列で最小のやつを返す

解き方

上2つが決まれば全部決まる。入力が4つ以上で1000以下なので、出てくる数字は2000以下だから、全通り試せる

ソースコード

public class AfraidOfEven {
    int max = (int)1e7;
    public int[] restoreProgression(int[] seq)
    {
        int i;
        int len = seq.Length;
        for (int a = 1; a * seq[0] < max; a *= 2)
        {
            int[] res = new int[len];
            res[0] = a * seq[0];
            for (int b = 1; b * seq[1] < max; b *= 2)
            {
                res[1] = b * seq[1];
                for (i = 2; i < len; i++)
                {
                    res[i] = (int)(res[1] * (long)i - res[0] * (long)(i - 1));
                    if (!make(res[i], seq[i])) break;
                }
                if (i == len) return res;
            }
        }
        return new int[0];
    }

    bool make(int a, int b)
    {
        if (a % b != 0) return false;
        int c = a / b;
        if (c == 0) return false;
        if ((c & (c - 1)) == 0) return true;
        return false;
    }
}

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);
    }
}
 |