TopCoder SRM 444 Div1 - TopCoderとJ言語と時々F#

250 Failed System Test 173.26 -> 0.00
500 Passed System Test 247.76
1000 Opened

これに撃墜で+50。

Mediumが通せて普通に嬉しい。Easyが落ちて普通に死ぬべき。

MediumはDPだけど一見貪欲法でもいけそうな気がする問題。そしてサンプルケースは貪欲法で全部通る。

だから貪欲法で解いてる人のを撃墜しようと狙ってたのに、貪欲法は意外にも一人しかいなくて残念。id:chokudaiの部屋にはたくさんいたようで、まあこの辺りは運だなぁと。

Easyはくだらない見落としで死んだ。Mediumを送信した後時間があったのにMediumの見直ししかしてなくて、Easyのミスを発見することができなかった。

それでもMediumが解けたのと撃墜で、レーティングは上昇。

1680 → 1758(+78)

250 UnfoldingTriangles

後になってPracticeで通したもの。

public class UnfoldingTriangles {
    public int solve(string[] grid, int unfoldLimit)
    {
        int res = -1;
        int Y = grid.Length, X = grid[0].Length;
        for (int y = 0; y < Y; ++y)
        {
            for (int x = 0; x < X; ++x)
            {
                if (grid[y][x] == '/')
                {
                    if (x != X - 1)
                    {
                        if (grid[y][x + 1] == '#') continue;
                    }
                    int sh = 0;
                    for (int i = 0; ; ++i)
                    {
                        int nx = x - i, ny = y + i;
                        if (nx < 0 || ny >= Y) break;
                        if (grid[ny][nx] != '/') break;
                        if (x != X - 1 && grid[ny][x + 1] == '#') break;
                        for (int k = nx + 1; k <= x; ++k)
                        {
                            if (grid[ny][k] == '/') sh++;
                            if (grid[ny][k] == '.') sh = -1000;
                        }
                        if (sh < 0) break;
                        if (sh > unfoldLimit) break;
                        if (ny != Y - 1)
                        {
                            bool ok = true;
                            for (int k = nx; k <= x; ++k)
                                if (grid[ny + 1][k] == '#')
                                    ok = false;
                            if (!ok) continue;
                        }
                        res = Math.Max(i + 1, res);
                    }
                }
            }
        }
        return res == -1 ? -1 : (res * (res + 1) / 2);
    }

500 FourBlocks

あるx座標tと、x座標がtのところにブロックが入ってるか入ってないかの状態を2進数で表したsを考えて、x座標がt未満の部分は全て埋まっていると考えたとき、x座標がtの部分がsである状態から最適な埋め方をした時に得られる得点を dp[t][s] としてDP。

yの大きさが10まで、xの大きさが25までだから 0 <= t < 25 で 0 <= s < 1024 = 2¹⁰だから計算量的には余裕。

public class FourBlocks {
    int N, M;
    int[,] dp = new int[25, 1024];
    int[] k = new int[25];
    int[,] G;

    public int getmax(int i, int st)
    {
        if (dp[i, st] > 0)
            return dp[i, st];
        if (i == M - 1)
        {
            int res = 0;
            for (int j = 0; j < N; ++j)
            {
                if (st % 2 == 0) res++;
                st /= 2;
            }
            return res;
        }
        int ret = 0, zeros = 0;
        for (int j = 0; j < N; ++j)
        {
            if ((st & (1 << j)) == 0)
                zeros++;
        }
        ret = zeros + getmax(i + 1, k[i + 1]);
        List<int> ok = new List<int>();
        for (int j = 0; j < N - 1; ++j)
        {
            if ((st & (1 << j)) == 0 && (st & (1 << (j + 1))) == 0)
            {
                if ((k[i + 1] & (1 << j)) == 0 && (k[i + 1] & (1 << (j + 1))) == 0)
                {
                    ok.Add(j);
                }
            }
        }
        for (int j = 0; j < (1<<ok.Count); ++j)
        {
            List<int> nxt = new List<int>();
            bool t = true;
            for (int x = 0; x < ok.Count; ++x)
            {
                if ((j & (1 << x)) != 0)
                {
                    if (nxt.Count != 0 && nxt[nxt.Count - 1] + 1 == ok[x])
                    {
                        t = false;
                        break;
                    }
                    nxt.Add(ok[x]);
                }
            }
            if (!t) continue;
            int nk = k[i + 1];
            for (int x = 0; x < nxt.Count; ++x)
            {
                nk |= 1 << nxt[x];
                nk |= 1 << (nxt[x] + 1);
            }
            ret = Math.Max(ret, getmax(i + 1, nk) + zeros + nxt.Count*16 - 2*nxt.Count);
        }
        return dp[i, st] = ret;
    }

    public int maxScore(string[] grid)
    {
        N = grid.Length;
        M = grid[0].Length;
        G = new int[N + 2, M + 2];
        for (int i = 0; i < 1024; ++i)
            for (int j = 0; j < 25; ++j)
                dp[j, i] = -1;
        int ct = 0;
        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= M; ++j)
                if (grid[i - 1][j - 1] == '1')
                {
                    ct++;
                    G[i, j] = 1;
                }
                else
                    G[i, j] = 0;
        for (int i = 1; i <= M; ++i)
        {
            k[i - 1] = 0;
            for (int j = 1; j <= N; ++j)
            {
                k[i - 1] *= 2;
                if (G[j, i] == 1) k[i - 1] += 1;
            }
        }
        return ct + getmax(0, k[0]);
    }
}