全完で暫定85位/3075人。Tシャツ貰えるのかな?
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);
グループに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();
複数の都市について、合計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; } }
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()は個人ライブラリのもの。
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は個人ライブラリのもの。
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; }