研究室に行ったら後輩達の卒論を応援するためのビックマックが60個も置いてありました(僕も頂きました)、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/nikkei2019-qual)にて開催されました、全国統一プログラミング王決定戦予選の第四回目です。

今回は、第四問「D. Restore the Tree」の問題と僕との戦闘記です。

0.はじめに

1.問題文

N 頂点の根付き木 (注記を参照) があり、その頂点には 1 から N までの番号が振られています。根以外の各頂点には、その親から一本の有向辺が伸びています。なお、根は頂点 1 とは限りません。

高橋くんは、このグラフに M 本の新たな有向辺を書き加えました。書き足された各辺 u → v は、ある頂点 u からその子孫であるような頂点 v に向かって伸びています。

高橋くんが辺を書き加えたあとの N 頂点 N − 1 + M 辺の有向グラフが与えられます。より具体的には、 N − 1 + M 組の整数のペア ( A 1 , B 1 ) , . . . , ( A N − 1 + M , B N − 1 + M ) が与えられ、これらは i 番目の辺が頂点 A i から頂点 B i に向かって伸びていることを表します。

元の根付き木を復元してください。

f:id:nemurin_blog:20190130012327p:plain

2.入力例

入力

入力は以下の形式で標準入力から与えられる。

N
A_(1) B_(1)
..
A_(N-1+M) B_(N-1+M)

出力

N 行出力せよ。 i 行目には、頂点 i が元の木の根であれば 0 を出力し、そうでなければ元の木で頂点 i の親を表す整数を出力すること。

なお、元の木は一意に定まることが示せる。

3.入出力例

こればっかりは実際に書いてイメージすることが重要だと思いました。

入力

入力されたグラフは次のようなものです。 f:id:nemurin_blog:20190129234732p:plain

出力

0
1
2

これは、 1 → 2 → 3 という根付き木に辺 1 → 3 を書き足したものであると考えられます。

f:id:nemurin_blog:20190130012511j:plain

3.コンテスト終わってから見た時の初見の感想(本番は解けなかったので…)

入力の分割とパースが必要
図は書けて問題の意味は分かった
そもそもグラフってどうプログラミングに落とし込めばいいねん…(圧倒的挫折)

f:id:nemurin_blog:20190130012645j:plain

4.他の人のコードを読んだ学び

(ソートしたい配列をＣと表記しています)

複数リストの配列の作り方

Enumerable.Range(0, n + 1).Select(_ => new List<int>()).ToArray();

グラフの接続判定(boolのルックアップテーブルに落とし込む！)

var hasParent = new bool[n + 1];

LINQのかき方、要素のスキップ(一文でif条件を設定できるのはキモチイイ…)

string.Join(Environment.NewLine, upper.Skip(1).Select(u => u[0]));

どうやってグラフをたどっていくか…→接続先をQueueに入れて処理を繰り返す！

今回もすごく勉強になりました…

5.コード

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
class Program
    {
    static void Main(string[] args)
        {
        string[] temp=System.Console.ReadLine().Split(' ');
        int N_EdgeNum = int.Parse(temp[0]);
        int M_NewArcNum = int.Parse(temp[1]);
        int ArcNum = N_EdgeNum - 1 + M_NewArcNum;
        List<int>[] upper =Enumerable.Range(0, N_EdgeNum + 1).Select(_ => new List<int>()).ToArray();
        List<int>[] lower = Enumerable.Range(0, N_EdgeNum + 1).Select(_ => new List<int>()).ToArray();
        bool[] hasparent = new bool[N_EdgeNum + 1];
        for (int i = 0; i < ArcNum; i++)
        {
            temp = Console.ReadLine().Split(' ');
            var a = int.Parse(temp[0]);
            var b = int.Parse(temp[1]);
            upper[b].Add(a);
            lower[a].Add(b);
        }
        int root = Enumerable.Range(1, N_EdgeNum).First(x => upper[x].Count == 0);
        Queue<int> queue = new Queue<int>();
        queue.Enqueue(root);
        while (queue.Count > 0)
        {
            var p = queue.Dequeue();
            foreach (var child in lower[p])
            {
                if (upper[child].Count == 1)
                {
                    queue.Enqueue(child);
                }
                else
                {
                    upper[child].Remove(p);
                }
            }
        }
        upper[root].Add(0);
        var answer = string.Join(Environment.NewLine, upper.Skip(1).Select(u => u[0]));
        Console.WriteLine(answer);
    }
    }

7.最後に

問題を理解するために入力例は重要ですね！

入力例などの詳しい問題はAtCoder(https://atcoder.jp/contests/nikkei2019-qual)に書かれております！

LINQマスターに俺はなりたい…

ねむーの日記~AtCoderな日々~

福岡に住むプログラミング好きのブログです！

【プログラミングコンテスト】全国統一プログラミング王決定戦予選④