天下一プログラマーコンテスト2016予選Aの参加日記

2完の141位/446人。さっさともう一問解けるようになりたい。

A - 天下一プログラマーゲーム

1~100の数のうち、3と5のいずれでも割り切れない数の合計を求めよ。

Console.WriteLine(Enumerable.Range(1, 100).Where(s => s % 3 != 0 && s % 5 != 0).Sum());

このFizzbuzz的難問が解ければ上位0.5%のプログラマのはず。
参考：どうしてプログラマに・・・プログラムが書けないのか?

B - PackDrop

N台の機器からなるネットワークがある。ネットワークは根付き木の形をしていて、機器0がルートである。このとき、機器間にPackDropという、0.01の確率でパケットを破壊する装置をいくつか置くことができる。子を持たない機器B(1)…B(M)それぞれに対し、機器0からの望ましいパケット到達率が与えられたとき、最少のPackDropの個数を求めよ。

なるべくルートの近くにPackDropを置くようにすればよい。

class Program
{
    static void Main(string[] args)
    {
        var str = Console.ReadLine().Split();
        var n = Int32.Parse(str[0]);
        var m = Int32.Parse(str[1]);
        var e = new List<List<int>>();
        for (int i = 0; i < n; i++) e.Add(new List<int>());

        for (int i = 1; i <= n - 1; i++)
        {
            var p = Int32.Parse(Console.ReadLine());
            e[i].Add(p);
            e[p].Add(i);
        }

        var pd = new int[n];
        for (int i = 0; i < n; i++) pd[i] = 0;

        for (int i = 0; i < m; i++)
        {
            str = Console.ReadLine().Split();
            var b_ = Int32.Parse(str[0]);
            var c_ = Int32.Parse(str[1]);
            pd[b_] = c_;
        }

        foreach (var c in e[0])
            Dfs(0, c, pd, e);

        var ret = 0;
        Dfs2(0, ref ret, 0, 0, pd, e);
        Console.WriteLine(ret);
    }

    static int Dfs(int prev, int idx, int[] pd, List<List<int>> e)
    {
        if (pd[idx] != 0) return pd[idx];
        var ret = Int32.MaxValue;

        foreach (var c in e[idx])
        {
            if (c == prev) continue;
            ret = Math.Min(ret, Dfs(idx, c, pd, e));
        }

        pd[idx] = ret;
        return ret;
    }

    static void Dfs2(int prev, ref int sum, int val, int idx, int[] pd, List<List<int>> e)
    {
        sum += (pd[idx] - val);
        foreach (var c in e[idx])
        {
            if (c == prev) continue;
            Dfs2(idx, ref sum, pd[idx], c, pd, e);
        }
    }
}

C - 山田山本問題

文字列AiとBiがそれぞれN個与えられる(i:0~N-1)。アルファベットの順番を任意に変え、すべてのAiがBiより辞書順で小さくなるようにしたい。そのようなアルファベットの並びはあるか。ある場合は、辞書順最小のものを出力せよ。

アルファベット26文字をノードとするDAGを、Kahnのアルゴリズムを使ってトポロジカルソートをすればよい。入次数0の頂点集合を優先キューにすることで、最終的な解が辞書順最小になる。

static void Main(string[] args)
{
    var edges = new List<List<int>>();
    for (int i = 0; i < 26; i++) edges.Add(new List<int>());

    var n = Int32.Parse(Console.ReadLine());

    for (int i = 0; i < n; i++)
    {
        var str = Console.ReadLine().Split();
        var astr = str[0];
        var bstr = str[1];

        var idx = 0;
        while (idx < Math.Min(astr.Length, bstr.Length) && astr[idx] == bstr[idx]) idx++;
        if (idx == Math.Min(astr.Length, bstr.Length))
        {
            if (astr.Length > bstr.Length)
            {
                Console.WriteLine(-1);
                return;
            }
            continue;
        }
        edges[astr[idx] - 'a'].Add(bstr[idx] - 'a');
    }

    var ret = new List<int>();

    var inEdgeNum = new int[26];
    for (int i = 0; i < edges.Count(); i++)
        foreach (var e in edges[i]) inEdgeNum[e]++;

    var que = new PriorityQueue<int>();
    for (int i = 0; i < 26; i++)
    {
        if (inEdgeNum[i] == 0) que.Push(i);
    }

    while (que.Count() > 0)
    {
        var val = que.Pop();
        ret.Add(val);

        foreach (var e in edges[val])
        {
            inEdgeNum[e]--;
            if (inEdgeNum[e] == 0) que.Push(e);
        }
    }

    Console.WriteLine(ret.Count() == 26 ? ret.Select(v => ((char)(v + 'a')).ToString()).Aggregate((a, b) => a + b) : "-1");
}

D - グラフィカルグラフ

重複のない大文字のアルファベットからなる無向木がある。この木の各頂点に接続する辺の本数は、4本以下である。
この木を100x100以下のマスで視覚的に表示せよ。

適当な根を選び、DFSで頂点を置いていけばよい。頂点数が26以下なので、距離を2^26、2^(26-1)、・・・と半分にしていけば、必ず重なることはない。表示する前に100x100に入るように整形する。

class Program
{
    static long[] dx = new long[] { -1, 0, 1, 0 };
    static long[] dy = new long[] { 0, 1, 0, -1 };

    static void Main(string[] args)
    {
        var n = Int32.Parse(Console.ReadLine());

        var edges = new List<List<int>>();
        for (int i = 0; i < n; i++) edges.Add(new List<int>());

        for (int i = 0; i < n - 1; i++)
        {
            var str = Console.ReadLine().Split();
            var v = str[0][0] - 'A';
            var w = str[1][0] - 'A';
            edges[v].Add(w);
            edges[w].Add(v);
        }

        var posX = new long[n];
        var posY = new long[n];
        Dfs(-1, 0, 0, 1 << 26, 0, 0, posX, posY, edges);

        Clean(posX);
        Clean(posY);

        var ret = new char[53, 53];
        for (int i = 0; i < 53; i++)
            for (int j = 0; j < 53; j++)
                ret[i, j] = '.';

        for (int i = 0; i < posX.Length; i++)
        {
            ret[posX[i], posY[i]] = (char)(i + 'A');
        }

        AddLines(ret, edges);
            
        Console.WriteLine("53 53");
        for (int i = 0; i < ret.GetLength(0); i++)
        {
            for (int j = 0; j < ret.GetLength(1); j++)
            {
                Console.Write(ret[i, j]);
            }
            Console.WriteLine();
        }
    }

    static void Dfs(int predDir, int prev, int idx, long dist, long currentX, long currentY, long[] posX, long[] posY, List<List<int>> edges)
    {
        posX[idx] = currentX;
        posY[idx] = currentY;

        var dir = predDir == -1 ? 0 : (predDir + 3) % 4;    //avoid to go backward
        foreach(var next in edges[idx])
        {
            if (next == prev) continue;

            var nextPosX = currentX + (dx[dir] * dist);
            var nextPosY = currentY + (dy[dir] * dist);

            Dfs(dir, idx, next, dist / 2, nextPosX, nextPosY, posX, posY, edges);
            dir = (dir + 1) % 4;
        }        
    }

    static void Clean(long[] pos)
    {
        var values = pos.Distinct().OrderBy(v => v).ToList();
        for (int i = 0; i < pos.Count(); i++)
        {
            pos[i] = values.IndexOf(pos[i]) * 2 + 1;
        }
    }

    static void AddLines(char[,] ret, List<List<int>> edges)
    {
        for (int i = 0; i < ret.GetLength(0); i++)
        {
            for (int j = 0; j < ret.GetLength(1); j++)
            {
                if (ret[i, j] != '.' && ret[i, j] != '-' && ret[i, j] != '|')
                {
                    for (int dir = 0; dir < 4; dir++)
                    {
                        DrawLine(ret, i, j, dir, edges[ret[i, j] - 'A']);
                    }
                }
            }
        }
    }

    static void DrawLine(char[,] ret, int x, int y, int dir, List<int> children)
    {
        var drawChar = dir == 0 || dir == 2 ? '|' : '-';

        var curX = x + dx[dir];
        var curY = y + dy[dir];
        while (curX >= 0 && curX < ret.GetLength(0) && curY >= 0 && curY < ret.GetLength(1) && ret[curX, curY] == '.')
        {
            curX += dx[dir];
            curY += dy[dir];
        }

        if (curX >= 0 && curX < ret.GetLength(0) && curY >= 0 && curY < ret.GetLength(1) && children.Contains(ret[curX, curY] - 'A'))
        {
            curX = x + dx[dir];
            curY = y + dy[dir];
            while (ret[curX, curY] == '.')
            {
                ret[curX, curY] = drawChar;
                curX += dx[dir];
                curY += dy[dir];
            }
        }
    }
}