Booking.com Back End CodeSprintの参加日記

全完で暫定85位/3075人。Tシャツ貰えるのかな?


Destination: Together <3

Jhonはn個の町、Ziziはm個の町を訪れたい。そのうちc個は重なっている。最後に訪れる都市が決まっているとして、二人の希望の都市すべてを訪れる順番は何通りあるか。

訪れる町の合計n+m-cをもとに計算する。

var num = n + m - c - 1;
UInt64 ret = 1;
while (num > 0)
{
    ret *= num;
    num--;
}
Console.WriteLine(ret);


Coupling Passions

グループにn人のメンバーがいて、それぞれm個の事柄に興味を持っている。さらに、y個の都市があり、それぞれがz個の満足させられる興味内容を持つ。メンバーは、1個以上の興味内容が満たされれば満足する。なるべく多くのメンバーを満足させるには、どの2都市を選べばよいか。アルファベット順で答えよ。ただし、解が複数になるときは、もっとも距離の近い2都市を答えること。
0 < n, m, y, z <= 250

都市数が250と少ないので、すべての組み合わせを試せば求められる。

if (cities.Count() == 1)
{
    Console.WriteLine(cities[0].Name);
    return;
}

var mi = -1;
var mj = -1;
var maxScore = -1;
var minDist = double.MaxValue;
for (int i = 0; i < y - 1; i++)
{
    for (int j = i + 1; j < y; j++)
    {
        var score = GetScore(cities[i], cities[j], passions);
        var dist = GetDist(cities[i], cities[j]);
        if (score > maxScore || (score == maxScore && dist < minDist))
        {
            mi = i;
            mj = j;
            maxScore = score;
            minDist = dist;
        }
    }
}

foreach (var c in new List<City>() { cities[mi], cities[mj] }.OrderBy(c => c.Name))
{
    Console.Write(c.Name + " ");
}
Console.WriteLine();


Reviews

複数の都市について、合計m個のレビューが付いている。各レビューには、レビュアーID・日時・レビュー本文がある。それぞれのレビューは以下のようにスコアが付けられる。
・日付が2016/6/15から2016/7/15なら20点、それ以外なら10点
・本文が100文字以上なら20点、それ以外なら10点
ここで、n個の興味内容が与えられたとき、それぞれについて最も高スコアのレビューを書いたレビュアーのIDを出力せよ
1 <= n <= 100
1 <= m <= 3250
0 <= r(レビュアーID) <= 100
レビュー本文は5000字以内

地道に統計を取るだけだが、少し工夫をしないとTLEになる。
レビュー本文が大きいので標準のConsole.ReadLine()が使えなかったり、日付がUnixTimeなので変換が必要だったり、入力文字列に無駄な空白があったりと、アルゴリズム以外のところが面倒だった。実際の仕事でのコーディングに近いのかもしれないが、プログラミングコンテストとしては面白くなかった。

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 passions = new List<string>();
        for (int i = 0; i < n; i++)
        {
            passions.Add(Console.ReadLine().ToUpper());
        }

        Dictionary<int, Reviewer> reviewers = new Dictionary<int, Reviewer>();
        for (int i = 0; i < m; i++)
        {
            str = Console.ReadLine().Split().Where(s => !string.IsNullOrEmpty(s)).ToArray();  //テストケースに変な空白が入っている...問題文に明記してないのはひどい
            var id = Int32.Parse(str[0]);
            var timeStamp = str[1];
            var body = ReadLine();
            var review = new Review() { TimeStamp = timeStamp, Body = body.ToUpper() };
            if (!reviewers.ContainsKey(id)) reviewers.Add(id, new Reviewer() { Id = id });
            reviewers[id].Reviews.Add(review);
        }
        foreach (var reviewer in reviewers) reviewer.Value.CalcScoreByPassion(passions);

        var reviewerList = reviewers.Select(r => r.Value).ToList();
        foreach (var passion in passions)
        {
            var best = reviewerList.OrderByDescending(r => r.GetScoreByPassion(passion)).ThenBy(r => r.Id).First();
            Console.WriteLine(best.GetScoreByPassion(passion) == -1 ? "-1" : best.Id.ToString());
        }
    }

    ///独自ReadLine()は省略
}

class Reviewer
{
    public int Id;
    public List<Review> Reviews = new List<Review>();
    public Dictionary<string, int> ScoreByPassion = new Dictionary<string,int>();

    public void CalcScoreByPassion(List<string> passions)
    {
        foreach (var passion in passions)
        {
            var score = Reviews.Sum(r => r.GetScoreByPassion(passion));
            if (score > 0) ScoreByPassion.Add(passion, score);
        }
    }

    public int GetScoreByPassion(string passion)
    {
        return ScoreByPassion.ContainsKey(passion) ? ScoreByPassion[passion] : -1;
    }
}

class Review
{
    public string TimeStamp;
    public string Body;

    bool? _isInRange;
    bool IsInRange
    {
        get
        {
            if (_isInRange == null)
            {
                try
                {
                    //UnixTimeを変換して比較…
                    var timeStamp_Datetime = new DateTime(1970, 1, 1, 0, 0, 0, 0, System.DateTimeKind.Utc);
                    timeStamp_Datetime = timeStamp_Datetime.AddSeconds(UInt64.Parse(TimeStamp));

                    if (new DateTime(2016, 6, 15) <= timeStamp_Datetime && timeStamp_Datetime <= new DateTime(2016, 7, 15))
                        _isInRange = true;
                    else
                        _isInRange = false;
                }
                catch { _isInRange = false; }
            }
            return (bool)_isInRange;
        }
    }

    Dictionary<string, int> ScoreByPassion = new Dictionary<string, int>();

    public int GetScoreByPassion(string passion)
    {
        if (ScoreByPassion.ContainsKey(passion)) return ScoreByPassion[passion];

        if (!Body.Contains(passion))
        {
            ScoreByPassion.Add(passion, 0);
            return 0;
        }
        var ret = Body.Length >= 100 ? 20 : 10;
        ret += (IsInRange ? 20 : 10);

        ScoreByPassion.Add(passion, ret);
        return ret;
    }
}


Good Memories

n人が遠足で訪れたイベントの順番を思い出したとする。ただし、すべてのイベントを思い出しているとは限らない。このとき、順番に矛盾があるかどうか答えよ。
たとえば、遠足に行ったのが2人だとして、思い出した内容が次のときは矛盾がない。
 1. Eiffel tower, Olympus, Disneyland
 2. Eiffel tower, Oktoberfest, Disneyland
しかし以下のような場合は矛盾している。
 1. Disneyland, Eiffel tower
 2. Eiffel tower, Disneyland
1 <= x(遠足の回数) <= 20
1 <= n <= 200
イベントの個数は1000以下、イベント名は50文字以下

前のイベント->後のイベントをエッジとする有向グラフを作成し、トポロジカルソートを試みればよい。ソート不可なら矛盾ありになる。前問と違ってとてもコンテストらしい問題。

var x = Int32.Parse(Console.ReadLine());
for (int i = 0; i < x; i++)
{
    var n = Int32.Parse(Console.ReadLine());

    var idx = 0;
    Dictionary<string, int> attToIdIdx = new Dictionary<string, int>();

    var edge = new List<List<int>>();
    for (int j = 0; j < 1001; j++) edge.Add(new List<int>());

    for (int j = 0; j < n; j++)
    {
        var str = Console.ReadLine().Split(',').Select(s => s.Trim()).ToArray();
        for (int k = 0; k < str.Length - 1; k++)
        {
            if (!attToIdIdx.ContainsKey(str[k]))
            {
                attToIdIdx.Add(str[k], idx);
                idx++;
            }
            if (!attToIdIdx.ContainsKey(str[k + 1]))
            {
                attToIdIdx.Add(str[k + 1], idx);
                idx++;
            }
            edge[attToIdIdx[str[k]]].Add(attToIdIdx[str[k + 1]]);
        }
    }

    var ok = TopologicalSort(Enumerable.Range(1, idx).ToList(), edge) != null;

    if (ok) Console.WriteLine("ORDER EXISTS");
    else Console.WriteLine("ORDER VIOLATION");
}

TopologicalSort()は個人ライブラリのもの。


Event Raffle

n人のメンバーと、n枚のチケットがある。メンバーはそれぞれ、いくつかの興味のある事柄を持っている。チケットはそれぞれ、満足させられる興味事項を持っている。メンバーは、最低1つの興味が満たされれば満足する。なるべく多くのメンバーを満足させるようにチケットを割り当てたとき、満足したメンバーは何人か。

メンバーとチケットで二部マッチングを行えばよい。

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

var rightSides = new List<HashSet<string>>();
for (int i = 0; i < n; i++)
{
    var str = Console.ReadLine().Split();
    rightSides.Add(new HashSet<string>(str.Skip(2)));
}

var leftSides = new List<HashSet<string>>();
for (int i = 0; i < n; i++)
{
    var str = Console.ReadLine().Split();
    leftSides.Add(new HashSet<string>(str.Skip(1)));
}

var biMatching = new BipartiteMatching();
for (int l = 0; l < leftSides.Count(); l++)
{
    var left = leftSides[l];
    for (int r = 0; r < rightSides.Count(); r++)
    {
        var right = rightSides[r];

        if (left.Any(lv => right.Contains(lv)))
        {
            biMatching.AddPair(l, r);
        }
    }
}

Console.WriteLine(biMatching.GetMaxMatchingNum());

BipertiteMatchingは個人ライブラリのもの。


Northern Tour

n個の都市がe本の双方向の道でつながれている。それぞれの道は通過するのにh時間かかる。また、都市には、滞在しなければならない時間viが設定されている。いま都市Bevagnaにいるとき、時間内になるべく多くの都市を訪れたい。その順番を答えよ。ただし、以下の制約がある。
・現在は月曜の午前8時である
・0時から午前8時までは睡眠をとる必要がある
・睡眠をとるのは必ず都市でなければならない
・睡眠中は滞在時間にカウントされない
・滞在時間を超えないと、その都市を離れることはできない
・期限は日曜の午前8時
1 <= n <= 20
1 <= e <= 20
1 <= vi <= 1000
1 <= h <= 1000

現在地・経過時間・訪問済み都市情報を保持してDijkstraすればよい。それに加え、経路復元が必要なので、親ノードも情報も持つ。

static void Main(string[] args)
{
    ///入力は省略

    //dijkstra
    Node ret = null;
    var que = new PriorityQueue<Node>();
    que.Push(new Node() { Current = 0, Time = 8, Visited = 1 });

    while (que.Count() > 0)
    {
        var node = que.Pop();
        if (ret == null || (ret.VisitedNum < node.VisitedNum))
            ret = node;

        foreach (var edge in graph[node.Current])
        {
            var nextNode = GetNextNode(edge, node, c);
            if (nextNode == null) continue;
            que.Push(nextNode);
        }
    }

    ///出力は省略(retを親までたどって逆に出力)
}

static Node GetNextNode(Edge edge, Node curretNode, Dictionary<int, int> cityNumToCost)
{
    //already visited
    if ((curretNode.Visited & (1 << edge.To)) != 0) return null;

    var ret = new Node()
    {
        Time = curretNode.Time,
        Current = edge.To,
        Visited = curretNode.Visited | (1 << edge.To),
        VisitedNum = curretNode.VisitedNum + 1,
        Parent = curretNode,
    };

    //update time
    var day = curretNode.Time >> 8;
    var hour = curretNode.Time & 0xFF;

    //add traveling time
    if (24 - hour >= edge.Cost)
    {
        hour += edge.Cost;
    }
    else
    {
        day++;
        hour = 8;
        if (24 - hour >= edge.Cost)
        {
            hour += edge.Cost;
        }
        else
        {
            return null;
        }
    }
    if (hour == 24)
    {
        hour = 8;
        day++;
    }

    //add staying time
    var stayTime = cityNumToCost[edge.To];
    while (stayTime > 0)
    {
        var diffTime = Math.Min(24 - hour, stayTime);
        hour += diffTime;
        stayTime -= diffTime;
        if (hour == 24)
        {
            hour = 8;
            day++;
        }
    }

    if (day > 5 && hour != 8) return null;

    ret.Time = (day << 8) | (hour & 0xFF);
    return ret;
}

class Node : IComparable
{
    public int Time;
    public int Current;
    public int Visited;
    public int VisitedNum;
    public Node Parent;

    public int CompareTo(object obj)
    {
        var tgt = obj as Node;
        if (tgt.Visited == Visited) return Time.CompareTo(tgt.Time);
        return VisitedNum.CompareTo(tgt.VisitedNum);
    }
}

class Edge
{
    public int Cost;
    public int To;
}