読者です 読者をやめる 読者になる 読者になる

Codingame『Dwarfs standing on the shoulders of giants』クリア

C# プログラミング ゲーム

Shingeki no KyojinShingeki no Kyojin / Xubaet


 ドワーフが巨人の肩に乗って……何?
ブログ書く直前までインフルエンザの話かと思ってたけど違うの?*1


www.codingame.com



 そういやLinkedListとかあるけど使ったことないわ。
使うと便利だったりするんだろうな。多分。

using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
class Solution
{
    //めんどいので全部確保
    static Influ[] r = new Influ[10000];
    
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine()); // the number of relationships of influence
        
        for (int i = 0; i < n; i++)
        {
            string[] inputs = Console.ReadLine().Split(' ');
            int x = int.Parse(inputs[0]);
            int y = int.Parse(inputs[1]);
            //移す方のノードを作りリンクを追加する
            if(r[x] == null) r[x] = new Influ();
            r[x].Next.Add(y);        
            //移される方のノードが無ければ作る
            if(r[y] == null) r[y] = new Influ();
        }
        
        int max = 0;
        foreach(Influ e in r) {
            if(e != null) {
                //再帰で調べる
                int tmp = sercher(e, e.N);
                //一番大きいノードの値を得る
                if(max < tmp) max = tmp;
            }
        }
        
        // Write an action using Console.WriteLine()
        // To debug: Console.Error.WriteLine("Debug messages...");

        Console.WriteLine(max); // The number of people involved in the longest succession of influences
    }

    //再帰で調べる    
    static int sercher(Influ e, int upn)
    {
        //既に来てたならN+1を返す
        if(e.isVisit == true) return e.N+1;

        //足跡を残す
        e.isVisit = true;
        
        //先を計算して値の大きい方(長距離)を選ぶ
        foreach(int next in e.Next) {
            int p = sercher(r[next], e.N);
            if(e.N < p) e.N = p;
        }

        //N+1を返す
        return e.N+1;        
    }
 
    //インフルエンザクラス
    class Influ
    {
        //リンク
        public List<int> Next = new List<int>();
        //移した数
        public int N = 0;
        //訪問フラグ
        public bool isVisit = false;        
    }
}


*1:英語が非常に弱い