TopCoder SRM 441 Div1

1. 250 Passed System Test 179.60
2. 500 Passed System Test 311.19
3. 1000 Opened

初めてMedium通せた！

のは嬉しいんだけど、今回のMediumは気付けばとても簡単だったのでもっと早く提出すべきだったなぁ。Mediumが初めてのせいで警戒しすぎたところはあった。

撃墜はなし。やろうと思ったけどMediumあたり自信があまり無かったので撃墜失敗してSystemTestでも落ちたら悲劇だなーと考えてやらなかった。Mediumが結構落とされてた。

レーティングは1409 → 1552(+143)

というわけで黄色くなりました！

ちなみにSRM440後のレーティングが1408なのに今回のレーティングが1409からなのはよくわからない。気付いたら1増えてた。

ソース↓

250 PerfectPermutation

何か明らかにコードが冗長。無駄なことしてる。

無駄なことが多いから提出もとうぜん遅くなるわけで、それは得点に大きくかかわるからどうにかしないと。

public class PerfectPermutation {
    public int reorder(int[] P) {
        int[] Q = new int[P.Length];
        bool[] V = new bool[P.Length];

        P.CopyTo(Q, 0);
        for (int j = 0; j < P.Length; ++j)
        {
            V[j] = false;
        }

        int c = 0, i = 0;
        while(c < P.Length)
        {
            V[i] = true;
            c++;
            if (V[Q[i]] == true && i != P.Length - 1)
            {
                for (int j = 0; j < P.Length; ++j)
                {
                    if (V[j] == false)
                    {
                        int t = Q[i];
                        Q[i] = Q[j];
                        Q[j] = t;
                        break;
                    }
                }
            }
            i = Q[i];
        }

        int res = 0;
        for (int j = 0; j < P.Length; ++j)
        {
            //Console.Write("{0} ", Q[j]);
            if (P[j] != Q[j]) res++;
        }
        return res;
    }
}

500 StrangeCountry

連結成分に分解してそれらを結合していく方針で。

ある連結成分に頂点がN個含まれているとき、その連結成分に辺がN本以上あれば、その連結成分と他の連結成分をつなげることができる。

あと、つなげ方に二種類あったのは実は意味ない感じ。

一本も辺が出ていない頂点を他の頂点とつなげることは不可能なので、一本のも辺が出ていない頂点があれば即-1を返す。

public class StrangeCountry {
    List<List<int>> G, P;
    List<int> ver;
    bool[] V;
    int idx, ct;

    private void f(int p)
    {
        V[p] = true;
        ct++;
        P[idx].Add(p);
        for (int i = 0; i < G[p].Count; ++i)
        {
            if (V[G[p][i]] == false)
            {
                f(G[p][i]);
            }
        }
    }

    public int transform(string[] g)
    {
        int N = g.Length;
        G = new List<List<int>>();
        for (int i = 0; i < g.Length; ++i)
        {
            G.Add(new List<int>());
            for (int j = 0; j < g.Length; ++j)
            {
                if (g[i][j] == 'Y')
                {
                    G[i].Add(j);
                }
            }
        }

        V = new bool[N];
        for (int i = 0; i < N; ++i)
        {
            V[i] = false;
        }
        idx = 0;
        ct = 0;
        P = new List<List<int>>();
        ver = new List<int>();
        while (ct < N)
        {
            int s;
            for (s = 0; s < N; ++s)
            {
                if (V[s] == false)
                    break;
            }
            P.Add(new List<int>());
            f(s);
            ver.Add(0);
            for (int i = 0; i < P[idx].Count; ++i)
            {
                ver[idx] += G[P[idx][i]].Count;
            }
            ver[idx] /= 2;
            if (P[idx].Count == 1)
            {
                return -1;
            }
            idx++;
        }

        int x = 0;
        while (P.Count != 1)
        {
            int s;
            for (s = 0; s < P.Count; ++s)
            {
                if (ver[s] >= P[s].Count)
                {
                    break;
                }
            }
            if (s == P.Count && P.Count != 1)
            {
                return -1;
            }
            int t;
            for (t = 0; t < P.Count; ++t)
            {
                if (t != s)
                {
                    break;
                }
            }
            P[s].AddRange(P[t]);
            ver[s] += ver[t];
            P.RemoveAt(t);
            ver.RemoveAt(t);
            x++;
        }
        return x;
    }
}