おにぎりおにぎりおにぎりおにぎりおにぎりおにぎりおにぎりおにぎりおにぎりおにぎり日記

 | 

2012-02-19

SRM533

23:59

challeng全然できなかった。



Easy

後ろから考えると、star[0]*star[star.Length-1]が最後に来て、

その前の状態には何を入れてもいい、ということに気づいて、メモ化再帰。

練習でDP解も書いておいた。

    public int maxEnergy(int[] weight)
    {
        int len = weight.Length;
        int[,] dp = new int[len, len];
        for (int k = 1; k <= len; k++)
            for (int i = 0; i + k < len; i++)
                for (int j = i + 1; j < i + k; j++)
                    dp[i, i + k] = Math.Max(dp[i, i + k], dp[i, j] + dp[j, i + k] + weight[i] * weight[i + k]);
        return dp[0, len - 1];
    }//maxEnergy



Medium


適当に偶奇で場合分けして当然落ちた。

#の数が、奇数なら最初1つの状態から、偶数なら0の状態から、

2つ一気に足していくことを考えると、

やっぱり適当に偶奇で場合分け。

連結の処理を忘れてはいけない。

(この解法の必要性は自明だが、十分性は感覚だよりorz)



    public string ableToUnlock(string[] board)
    {
        int row = board.Length;
        int col = board[0].Length;
        int[] cntRow = new int[row];
        int[] cntCol = new int[col];

        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col; j++)
            {
                if (board[i][j] == '#')
                    cntRow[i]++;
            }//for j
        }//for i

        for (int j = 0; j < col; j++)
        {
            for (int i = 0; i < row; i++)
            {
                if (board[i][j] == '#')
                    cntCol[j]++;
            }//for i
        }//for j

        int cnt = 0;
        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col; j++)
            {
                if (board[i][j] == '#')
                    cnt++;
            }//for j
        }//for i

        int r = 0;
        for (int i = 0; i < row; i++)
        {
            if ((cntRow[i] & 1) == 1)
                r++;
        }//for i

        int c = 0;
        for (int i = 0; i < col; i++)
        {
            if ((cntCol[i] & 1) == 1)
                c++;
        }//for i

        UnionFind uf = new UnionFind(row * col);
        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col; j++)
            {
                if (board[i][j] == '#')
                {
                    for (int p = 0; p < row; p++)
                    {
                        if (board[p][j] == '#')
                            uf.Unite(i * col + j, p * col + j);
                    }//for p
                    for (int p = 0; p < col; p++)
                    {
                        if (board[i][p] == '#')
                            uf.Unite(i * col + j, i * col + p);
                    }//for p
                }
            }//for j
        }//for i

        for (int i = 0; i < row * col; i++)
        {
            if (uf.Size(i) != cnt && uf.Size(i) != 1)
                return "NO";
        }//for i

        if ((cnt & 1) == 1)
        {
            if (r == 1 && c == 1)
                return "YES";
            return "NO";
        }

        if ((r == 0 && c == 0) || (r == 0 && c == 2))//|| (r == 2 && c == 0))
            return "YES";
        return "NO";

    }//ableToUnlock

 |