TopCoder SRM 700 Div2

TopCoder SRM 700 Div2 の解説。

Xylophone (Easy)

問題

TopCoder Statistics - Problem Statement

方針

やるだけ。
7の剰余で分類して、それぞれ使われているか数えればよい。

ソースコード(C#)

class Xylophone
{
    public static int countKeys(int[] keys)
    {
        bool[] b = new bool[7];
        foreach (var i in keys)
        {
            b[i % 7] = true;
        }
        int ans = 0;
        for (int i = 0; i < b.Length; i++)
        {
            if (b[i]) ans++;
        }
        return ans;
    }
}

XMarksTheSpot (Med)

問題

TopCoder Statistics - Problem Statement

方針

全探索。 まずは盤面を調べる。
'O'の上下左右の端を調べて持っておき、'?'の位置を調べて持っておく。
'?'が'O'であるか'.'であるかを全通り場合分けして試す。ビット演算を使うとよい。

ちなみに?の場合分けをする際、毎回盤面を調べているとシステムテストで落ちる。

ソースコード(C#)

using System;
using System.Collections.Generic;
class XMarksTheSpot
{
    public static int countArea(string[] s)
    {
        int ans = 0;
        List<int> qx = new List<int>();
        List<int> qy = new List<int>();
        int l = int.MaxValue;
        int r = int.MinValue;
        int u = int.MaxValue;
        int d = int.MinValue;
        for (int i = 0; i < s.Length; i++)
        {
            for (int j = 0; j < s[0].Length; j++)
            {
                if(s[i][j]=='?')
                {
                    qx.Add(i);
                    qy.Add(j);
                }
                else if (s[i][j] == 'O')
                {
                    l = Math.Min(l, j);
                    r = Math.Max(r, j);
                    u = Math.Min(u, i);
                    d = Math.Max(d, i);
                }
            }
        }

        for (int bitcnt = 0; bitcnt < (1<<qx.Count); bitcnt++)
        {
            int ltmp = l;
            int rtmp = r;
            int utmp = u;
            int dtmp = d;
            for (int qcnt = 0; qcnt < qx.Count; qcnt++)
            {
                if (((bitcnt >> qcnt) & 1) == 1)
                {
                    ltmp = Math.Min(ltmp, qy[qcnt]);
                    rtmp = Math.Max(rtmp, qy[qcnt]);
                    utmp = Math.Min(utmp, qx[qcnt]);
                    dtmp = Math.Max(dtmp, qx[qcnt]);
                }
            }
            
            ans += (rtmp - ltmp + 1) * (dtmp - utmp + 1);
        }
        return ans;
    }
}

XYZCoder (Hard)

問題

TopCoder Statistics - Problem Statement

方針

DP。
順位が下の人間から見ていき、 順位を決めた人間の数、部屋内での優勝者が決まった数をキーにしてDPすればよい。
最後に、優勝者の順列を出すために、部屋数の階乗を掛ける。
適宜modをとること。

DPの雑なイメージはこちら。

使った人数＼部屋トップが決まった人数		0		1		2		3
6		1		5		9		5
		↑	↗	↑	↗	↑	↗	↑
5		1		4		5		0
		↑	↗	↑	↗	↑		↑
4		1		3		2		0
		↑	↗	↑	↗	↑		↑
3		1		2		0		0
		↑	↗	↑		↑		↑
2		1		1		0		0
		↑	↗	↑		↑		↑
1		1		0		0		0
		↑		↑		↑		↑
0		1		0		0		0

ソースコード(C#)

class XYZCoder
{
    public static int countWays(int room,int size)
    {
        long ans = 1;
        long mod = 1000000007;

        long[,] dp = new long[room * size + 10, room + 10]; //member,winner
        dp[0, 0] = 1;
        for (int member = 1; member <= room*size; member++)
        {
            for (int winner = 0; winner <= room; winner++)
            {
                if(winner>0 && member >= winner*size)
                {
                    dp[member, winner] = (dp[member - 1, winner] + dp[member - 1, winner - 1]) % mod;

                }
                else
                {
                    dp[member, winner] = dp[member - 1, winner];
                }
            }
        }
        ans = dp[room * size, room];
        for (int i = 1; i <= room; i++)
        {
            ans = (ans * i) % mod;
        }
        return (int)(ans % mod);
    }
}