Booking.com Back End CodeSprintの参加日記
全完で暫定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; }
Morgan Stanley Codeathon 2016の参加日記
3完1部分点で暫定192位/3601人。数学が分からなくて苦しんだ。
ある銘柄のN日分の株価が与えられる。ちょうど利益Diを得るためには、いつ買っていつ売ればよいか。ただし、株を保持する日数は最小化したい。さらに、複数の解がある場合は、もっとも早く利益を得られる組み合わせを答えよ。
1 <= N <= 2x10^5
1 <= D <= 10
1 <= Ni, Di <= 10^8
簡単そうに見えるが、2つの制限を満足させるのに手間取った。後ろからループし、その日に買った場合に条件を満たせるかを判定していけばよい。
N日分の株価情報(最大2x10^5個)が1行で与えられるため、標準のConsole.ReadLine()だと入力バッファが足りないと思われる。
class Program { static void Main(string[] args) { var str = Console.ReadLine().Split(); var n = Int32.Parse(str[0]); var d = Int32.Parse(str[1]); var price = ReadLine().Split().Select(s => long.Parse(s)).ToArray(); for (int i = 0; i < d; i++) { var profit = long.Parse(Console.ReadLine()); int left = -1; int right = Int32.MaxValue; if (Get(profit, ref left, ref right, price)) Console.WriteLine(string.Format("{0} {1}", left + 1, right + 1)); else Console.WriteLine("-1"); } } static bool Get(long profit, ref int left, ref int right, long[] price) { var dict = new Dictionary<long, int>(); for (int i = price.Length - 1; i >= 0; i--) { if (dict.ContainsKey(price[i] + profit)) { var l = i; var r = dict[price[i] + profit]; if (left == -1 || right - left >= r - l) { right = r; left = l; } } if (!dict.ContainsKey(price[i])) dict.Add(price[i], i); else dict[price[i]] = i; } return left != -1; } static string ReadLine() { StringBuilder sb = new StringBuilder(); while (true) { int ch = Console.Read(); if (ch == -1) break; if (ch == '\r' || ch == '\n') { if (ch == '\r') Console.Read(); return sb.ToString(); } sb.Append((char)ch); } if (sb.Length > 0) return sb.ToString(); return null; } }
整数Nが与えられたとき、N^2を割り切るがNを割り切らない数で、N未満のものの個数を答えよ。
1 <= N <= 10^12
整数Nの素因数分解をとおく。なので、の因数は個とわかる。
このうちN未満のものは個となる。これと、の因数数との差が答えとなる。
static void Main(string[] args) { var n = UInt64.Parse(Console.ReadLine()); var factors = GetFactors(n); UInt64 ret1 = 1; foreach (var factor in factors) ret1 *= (2 * factor.Value + 1); ret1--; ret1 /= 2; UInt64 ret2 = 1; foreach (var factor in factors) ret2 *= (factor.Value + 1); ret2--; Console.WriteLine(ret1 - ret2); } public static Dictionary<UInt64, UInt64> GetFactors(UInt64 n) { var ret = new Dictionary<UInt64, UInt64>(); while (n % 2 == 0) { if (!ret.ContainsKey(2)) ret.Add(2, 0); ret[2]++; n = n / 2; } for (UInt64 i = 3; i <= Math.Sqrt(n); i = i + 2) { while (n % i == 0) { if (!ret.ContainsKey(i)) ret.Add(i, 0); ret[i]++; n = n / i; } } if (n > 2) { if (!ret.ContainsKey(n)) ret.Add(n, 0); ret[n]++; } return ret; }
Samantha and Portfolio Management
N個のポートフォリオと、それぞれの収益率riが与えられる。また、i番目のポートフォリオの収益の分散がであるとする。各ポートフォリオに重みづけwiを付けたとき、全体の収益分散を最小化したい。このときの期待収益と分散を答えよ。
0 <= wi <= 1
分散を最小化するのだから、収益は無視して重みづけwiが求められる。ポートフォリオそれぞれの分散がだとする。このとき、重みづけをのようにすれば、最終的な分散がになって最小化する。あとは、この重みづけを使って利益を求めればよい。
static void Main(string[] args) { var n = Int32.Parse(Console.ReadLine()); var r = new List<int>(); for (int i = 0; i < n; i++) r.Add(Int32.Parse(Console.ReadLine())); var w = GetW(r); var v = new Tuple<int, int>(1, Enumerable.Range(1, r.Count()).Sum()); var e = GetE(r, w); v = Modify(v); e = Modify(e); Console.WriteLine(string.Format("{0} {1}", e.Item1, e.Item2)); Console.WriteLine(string.Format("{0} {1}", v.Item1, v.Item2)); } static Tuple<int, int> Modify(Tuple<int, int> value) { var gcd = Gcd(value.Item1, value.Item2); return new Tuple<int, int>(value.Item1 / gcd, value.Item2 / gcd); } static List<Tuple<int, int>> GetW(List<int> r) { var b = Enumerable.Range(1, r.Count()).Sum(); var ret = new List<Tuple<int, int>>(); for (int i = 0; i < r.Count(); i++) { ret.Add(new Tuple<int, int>(i + 1, b)); } return ret; } static Tuple<int, int> GetE(List<int> r, List<Tuple<int, int>> e) { var t = 0; for (int i = 0; i < r.Count(); i++) { t += r[i] * e[i].Item1; } return new Tuple<int, int>(t, e[0].Item2); } static int Gcd(int a, int b) { if (a < b) { var tmp = a; a = b; b = tmp; } if (b == 0) return a; var p = a > b ? a : b; return Gcd(b, p % b); }
1~Nの町があり、いま町1に滞在している。町の間には、M本の普通の道とK本の特別な道がある(いずれも双方向)。それぞれの道には、通過に必要な時間zが与えられる。すべての特別な道を通って町Nまで行くときの最短時間を求めよ。
1 <= N <= 1000
1 <= M <= 2000
1 <= K <= 10
1 <= x, y <= N, x != y
1 <= z <= 1000
次のようなノードクラスを使ってDijkstraで最短経路を求めればよい。Kは最大で10本しかないのでビットで情報を持つことができる。
public class Node : IComparable { public int Current; //今いる町 public int Time; //今までの経過時間 public int PassedK; //通った特別な道情報 public int PassedKNum; //通った特別な道の本数 public int CompareTo(object obj) { var tgt = obj as Node; if (PassedKNum == tgt.PassedKNum) return Time.CompareTo(tgt.Time); return PassedKNum.CompareTo(tgt.PassedKNum); } }
Dikstraの部分。典型題のためかDifficultの割には正答率が高かった。
var que = new PriorityQueue<Node>(); que.Push(new Node() { Current = 0, Time = 0 }); var minCosts = new int[n, 1025]; //町Idx、特別な道情報->最小コスト for (int i = 0; i < n; i++) for (int j = 0; j < 1025; j++) minCosts[i, j] = Int32.MaxValue; Node ret = null; while (que.Count() > 0) { var node = que.Pop(); if (node.PassedKNum == k && node.Current == n - 1) if (ret == null || node.Time < ret.Time) ret = node; foreach (var edge in e[node.Current]) { var nextNode = GetNextNode(node, edge); if (nextNode.Time >= minCosts[nextNode.Current, nextNode.PassedK]) continue; minCosts[nextNode.Current, nextNode.PassedK] = Math.Min(minCosts[nextNode.Current, nextNode.PassedK], nextNode.Time); que.Push(nextNode); } } Console.WriteLine(ret.Time);
AGC002の参加日記
AGC第二回。2完397位/662人で惨敗。
整数a,bが与えられたとき、a, a+1, ..., bすべての積の符号を求めよ。
aとbが両方負のときは、個数の偶奇で解が変わる。
if (a > 0 && b > 0) Console.WriteLine("Positive"); else if ( (a <= 0 && b >= 0) || (a >= 0 && b <= 0)) Console.WriteLine("Zero"); else Console.WriteLine(Math.Abs(a - b) % 2 == 0 ? "Negative" : "Positive");
箱がN個あり、1番目の箱には赤いボールが、それ以外の箱には白いボールが1つずつ入っている。以下のM回の操作を行ったとき、最終的に赤いボールが入っている可能性のある箱は何個か。
・箱xからボールを取り出し、箱yに移す
それぞれの箱に入っているボールの数と、赤いボールが入っているかもしれない箱の集合を保持しながらシミュ―レーションする。ボールの数を管理しないと、箱が空になる場合に対処できない。
var num = new int[n + 1]; for (int i = 1; i < n + 1; i++) num[i] = 1; var ret = new HashSet<int>() { 1 }; for (int i = 0; i < m; i++) { str = Console.ReadLine().Split(); var x = Int32.Parse(str[0]); var y = Int32.Parse(str[1]); if (ret.Contains(x)) ret.Add(y); num[x]--; num[y]++; if (num[x] == 0) ret.Remove(x); } Console.WriteLine(ret.Count());
長さa[1], a[2], … a[N]のロープがある。1<=i<=N-1について、ロープiの右端とロープi+1の左端が結ばれている。繋がれているロープの長さの合計がL以上なら、どれか一つを解くことができる。すべての結び目を解くことは可能か。可能ならその手順も出力せよ。
2 <= N <= 10^5
1 <= a[i] <= 10^9
1 <= L <= 10^9
最後に残る2つのロープの合計長がL以上なら、そこに至るまでの手順はどのようでもよい。よって、長さがL以上になる2つの連続するロープを探し、そこだけを残して左右から解けばよい。
var tgt = -1; for (int i = 0; i < n - 1; i++) { if (a[i] + a[i + 1] >= l) { tgt = i; break; } } if (tgt == -1) { Console.WriteLine("Impossible"); return; } Console.WriteLine("Possible"); for (int i = 0; i < tgt; i++) Console.WriteLine(i + 1); for (int i = n - 1; i > tgt; i--) Console.WriteLine(i);
閃けばひどく単純に解けるが、思いつかないとかなり嵌るタイプの問題だった。
N頂点M辺の無向グラフがある。頂点は1~N、辺は1~Mに番号が振ってある。以下のクエリごとの最小スコアを求めよ。
・頂点xとy、および整数zが与えられる
・xまたはyから任意に頂点を訪れていく
・訪れた頂点数がzになったとき、辺の番号の最大値がスコアとなる
3 <= N <= 10^6
N-1 <= M <= 10^5
1 <= クエリ数(Q) <= 10^5
「クエリjのスコアをk以下にできるか?」という判定で二分探索をする。スコアがk以下になるかどうかは、UnionFindに辺1からkまでの頂点を結合していき、xとyが含まれる集合の頂点数がz以上になっているかで判断できる。
クエリの数が多いので、二分探索は並列に行わないと間に合わない。
class Query { public int X; public int Y; public int Z; //最終解が(left, Right]に存在する public int Left; public int Right; }
こんな風にクエリごとに二分探索のLeftとRightを持ち、エッジ1~Nのループ内で、今のエッジ番号がkに一致するクエリをアップデートしていく。
while (true) { if (queries.Count(v => v.Right - v.Left > 1) == 0) break; var tgts = new Dictionary<int, List<Query>>(); //これだと通らない。まだv.Leftが解答の可能性が残っている //foreach (var query in queries.Where(v => v.Right - v.Left > 1)) foreach(var query in queries) { var mid = (query.Left + query.Right) / 2; if (!tgts.ContainsKey(mid)) tgts.Add(mid, new List<Query>()); tgts[mid].Add(query); } if (tgts.Count() == 0) break; var unionFind = new UnionFind(n); for (int e = 0; e < m; e++) { unionFind.Unite(edges[e].Item1, edges[e].Item2); //2頂点を結合 if (tgts.ContainsKey(e)) { foreach (var query in tgts[e]) //どれかのクエリの (Left + Right) / 2 なら該当クエリをアップデート { var sum = unionFind.Size(query.X); if (!unionFind.Same(query.X, query.Y)) sum += unionFind.Size(query.Y); if (sum >= query.Z) query.Right = e; else query.Left = e; } } } }
手持ちのUnionFindにSize()を実装していなかったので追加しておいた。
天下一プログラマーコンテスト2016予選Aの参加日記
2完の141位/446人。さっさともう一問解けるようになりたい。
1~100の数のうち、3と5のいずれでも割り切れない数の合計を求めよ。
Console.WriteLine(Enumerable.Range(1, 100).Where(s => s % 3 != 0 && s % 5 != 0).Sum());
このFizzbuzz的難問が解ければ上位0.5%のプログラマのはず。
参考:どうしてプログラマに・・・プログラムが書けないのか?
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); } } }
文字列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"); }
重複のない大文字のアルファベットからなる無向木がある。この木の各頂点に接続する辺の本数は、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]; } } } }
World CodeSprint 5の参加日記
3完+1部分点で暫定349位/6403人。難易度Moderateを1つ落としたのが悔しい。
https://www.hackerrank.com/contests/world-codesprint-5/challenges
CamelCaseの文字列に、英単語がいくつあるか答えよ。
大文字の数+1を返せばよい。
Console.WriteLine(str.Count(s => s >= 'A' && s <= 'Z') + 1);
空文字列pに以下の操作を行い、文字列sを作りたい。最小のコストを答えよ。
・p末尾に任意の文字を足す(1ドル)
・p内の部分文字列を、p末尾に足す(0ドル)
2度目以降に使う文字にはコストがかからないので、sから重複を排除した文字数を答えればよい。
Console.WriteLine(s.Distinct().Count());
英小文字のみからなる文字列sが与えられる。このとき、次の条件を満たす部分文字列が、s内にいくつあるか答えよ。
・任意のインデックスa,b,c,d(0 <= a < b < c < d)について、s[a]==s[d]かつs[b]==s[c]
1 <= |s| <= 10^6、解答は10^9+7のModを出力する
動的計画法を次のように定義して解いた。
dp_1[i][j]:0~iの文字jの個数
dp_2[i][l][m]:0~iで、{…,文字l,…,文字m,…}になっているパターン数
→ dp_2[i][l][s[i]] = dp_1[i-1][l] + dp_2[i-1][l][s[i]]
dp_3[i][j][k]:0~iで、{…,文字j,…,文字k,…,文字k,…}になっているパターン数
→ dp_3[i][j][s[i]] = dp_2[i-1][l][s[i]] + dp_3[i-1][j][s[i]]
このまま実装するとメモリが不足するので、配列の再利用を行っている。
const ulong mod = 1000000007; static void Main(string[] args) { var s = Console.ReadLine(); var dp_1 = new ulong[26]; var dp_2 = new ulong[26, 26]; var dp_3 = new ulong[26, 26]; ulong ret = 0; for (int i = 0; i < s.Length; i++) { var c = s[i] - 'a'; for (int x = 0; x < 26; x++) { ret += dp_3[c, x]; ret %= mod; } for (int x = 0; x < 26; x++) { dp_3[x, c] += dp_2[x, c]; dp_3[x, c] %= mod; } for (int x = 0; x < 26; x++) { dp_2[x, c] += dp_1[x]; dp_2[x, c] %= mod; } dp_1[c]++; dp_1[c] %= mod; } Console.WriteLine(ret); }
Editorialよりすっきりした解だと思うのだが、どうだろうか。
Longest Increasing Subsequence Arrays
長さmのInt型の配列を作る。このとき、部分列として、必ず{1,2,3,…n}が含まれるようにしたい。可能なパターン数を答えよ。
1 <= m <= 5x10^5、1 <= n <= 10^5
n <= m
解答は10^9+7のModを出力する
Editorialより。S[n]の位置+1をループすることで求めることができる。
static Int64 Solve(Int64 m, Int64 n) { Int64 ret = 0; Int64 nPowX = 1; var n1PowX = ModPow(n - 1, m - n, mod); var invN1 = ModInv(n - 1, mod); for (Int64 x = 0; x <= m - n; x++) { //これだと大きいケースでTLEになる //var n1PowX = ModPow(n - 1, m - n - x, mod); //Invを掛けていく方法では、最終的に1になってはくれない if (m - n - x == 0) n1PowX = 1; var value = (Nck((int)(m - x - 1), (int)(n - 1)) * nPowX % mod) * n1PowX; value %= mod; ret += value; if (ret >= mod) ret -= mod; nPowX *= n; nPowX %= mod; n1PowX *= invN1; n1PowX %= mod; } return ret; }
(n-1)^(m-n-x)をループ内で直接求めるとTLEになるので、(n-1)^(-1)のModを掛けていくことで算出する。ただし、この方法だと最終的に(n-1)^0のとき解が1になってくれないので、その場合だけ直接1をアサインすることになる。
ModPow()、Nck()、ModInv()は個人ライブラリより。
ノード数nの木があり、各ノードにはc[i]個のコインが付いている。ここで、どれかのノードにコインがcw個付いたノードを足し、n+1ノードの木にする。この木の2つのエッジを切ったとき、出来た3つの木が同じ数のコインを持つようにしたい。cwの最小値を求めよ。不可能な場合は-1とする。
1 <= n <= 5x10^4
1 <= c[i] <= 10^9部分点(30%)
1 <= n <= 100
1 <= c[i] <= 100部分点(50%)
1 <= n <= 2000
1 <= c[i] <= 10^9
本番では50%の部分点だった。エッジでループし、該当エッジをカットしたときの小さいほうが、最終的な3つの木の1つとなり得るかを判定している。そのとき、予め「ノードAからみたノードB以降の木の合計値」を求めることで計算量を削減した。
https://www.hackerrank.com/contests/world-codesprint-5/challenges/balanced-forest/submissions/code/6349361
Editorialによると、ノード1をルートとし、各ノードに子ノードのコイン合計を持つことで、O(n Log(n))で算出できる。これは本番で場合分けがうまくいかず、断念したやり方だった。
Editorialサンプルの変数名やコメントを直したものが以下。
static Int64 Solve() { // Nodeクラスの配列を作成 // 各Nodeについて、サブ木の合計、DFSの到着時間、およびDFSのLeave時間を保持する Dfs(1, 0); // サブ木合計値から、最小の到着時間、最大の到着時間とそれぞれのノードインデックスを保持する辞書を作成する for (int i = 1; i <= n; i++) { if (!minArrivalTime_BySum.ContainsKey(c[i].SumOfSubtree)) { minArrivalTime_BySum[c[i].SumOfSubtree] = c[i].ArriveTime; maxArrivalTime_BySum[c[i].SumOfSubtree] = c[i].ArriveTime; idxOfMinArrivalTime_BySum[c[i].SumOfSubtree] = i; idxOfMaxArrivalTime_BySum[c[i].SumOfSubtree] = i; } else { if (minArrivalTime_BySum[c[i].SumOfSubtree] > c[i].ArriveTime) { minArrivalTime_BySum[c[i].SumOfSubtree] = c[i].ArriveTime; idxOfMinArrivalTime_BySum[c[i].SumOfSubtree] = i; } if (maxArrivalTime_BySum[c[i].SumOfSubtree] < c[i].ArriveTime) { maxArrivalTime_BySum[c[i].SumOfSubtree] = c[i].ArriveTime; idxOfMaxArrivalTime_BySum[c[i].SumOfSubtree] = i; } } } minCw = (Int64)1e15; // 木のコイン合計が偶数、かつちょうど半分のサブ木合計があったら、その値が解になり得る if (sum % 2 == 0 && maxArrivalTime_BySum.ContainsKey(sum / 2)) minCw = sum / 2; // 全ノードのループ for (int i = 1; i <= n; i++) { if (3 * c[i].SumOfSubtree <= sum) // この時は、該当サブ木にcwを足すことを試す TryAddCw_ToSubTree(i); else if (2 * c[i].SumOfSubtree < sum) // サブ木合計を、最終的な1/3の1つとできるか試す TryAddCw_ToAnotherTree(i); } return minCw == (Int64)1e15 ? -1 : minCw; } static void TryAddCw_ToSubTree(int x) { if ((sum - c[x].SumOfSubtree) % 2 == 0) //サブ木以外が2で割れなければ無理 { Int64 p = (sum - c[x].SumOfSubtree) / 2; //最終的な1/3のコイン数 if (maxArrivalTime_BySum.ContainsKey(p) && (c[idxOfMaxArrivalTime_BySum[p]].ArriveTime > c[x].ArriveTime || c[idxOfMaxArrivalTime_BySum[p]].LeaveTime < c[x].ArriveTime)) minCw = Math.Min(minCw, p - c[x].SumOfSubtree); else if (minArrivalTime_BySum.ContainsKey(p) && (c[idxOfMinArrivalTime_BySum[p]].ArriveTime > c[x].ArriveTime || c[idxOfMinArrivalTime_BySum[p]].LeaveTime < c[x].ArriveTime)) minCw = Math.Min(minCw, p - c[x].SumOfSubtree); else if (minArrivalTime_BySum.ContainsKey(p + c[x].SumOfSubtree) && c[idxOfMinArrivalTime_BySum[p + c[x].SumOfSubtree]].ArriveTime < c[x].ArriveTime && c[idxOfMinArrivalTime_BySum[p + c[x].SumOfSubtree]].LeaveTime >= c[x].ArriveTime) minCw = Math.Min(minCw, p - c[x].SumOfSubtree); else if (maxArrivalTime_BySum.ContainsKey(p + c[x].SumOfSubtree) && c[idxOfMaxArrivalTime_BySum[p + c[x].SumOfSubtree]].ArriveTime < c[x].ArriveTime && c[idxOfMaxArrivalTime_BySum[p + c[x].SumOfSubtree]].LeaveTime >= c[x].ArriveTime) minCw = Math.Min(minCw, p - c[x].SumOfSubtree); return; } } static void TryAddCw_ToAnotherTree(int x) { Int64 add = 3 * c[x].SumOfSubtree - sum; if (minArrivalTime_BySum[c[x].SumOfSubtree] != maxArrivalTime_BySum[c[x].SumOfSubtree]) minCw = Math.Min(minCw, add); else if (minArrivalTime_BySum.ContainsKey(c[x].SumOfSubtree - add) && (c[idxOfMinArrivalTime_BySum[c[x].SumOfSubtree - add]].ArriveTime < c[x].ArriveTime || c[idxOfMinArrivalTime_BySum[c[x].SumOfSubtree - add]].ArriveTime > c[x].LeaveTime)) minCw = Math.Min(minCw, add); else if (maxArrivalTime_BySum.ContainsKey(c[x].SumOfSubtree - add) && (c[idxOfMaxArrivalTime_BySum[c[x].SumOfSubtree - add]].ArriveTime < c[x].ArriveTime || c[idxOfMaxArrivalTime_BySum[c[x].SumOfSubtree - add]].ArriveTime > c[x].LeaveTime)) minCw = Math.Min(minCw, add); else if (minArrivalTime_BySum.ContainsKey(2 * c[x].SumOfSubtree - add)) minCw = Math.Min(minCw, add); return; } //// 省略 class Node { public Int64 SumOfSubtree; //c[i].s - sum of values in subtree rooted in i public int ArriveTime; //time when dfs arrived in i-th node public int LeaveTime; //time when dfs leave i-th node ( all children are marked) };
TryAddCw_ToSubTree()とTryAddCw_ToAnotherTree()で細かい場合分けをしているが、ノードのコイン数は必ず1以上なのだから、もっと簡略化できそうな気がする。
(あるノードのサブ木合計値が、そのノードの子で発生することは有り得ないため)
AGC001の参加日記
AGC第一回。参加者1200人超でめでたい。2完で318位でした。
Editorial:https://agc001.contest.atcoder.jp/data/agc/001/editorial.pdf
A: BBQ Easy - AtCoder Grand Contest 001 | AtCoder
バーベキュー用の串が2N本ある。1つの串焼きに2本の串を使う。1つの串焼きに使える具材は、短いほうの串の長さに等しい。最大でいくつの具材を串焼きにできるか。
串をソートしてペアを作り、それぞれの短いほうの和を求めればよい。標準入出力の凡ミスで二回もWAを出してしまった。
public static int Solve(int[] l) { var ret = 0; l = l.OrderByDescending(v => v).ToArray(); for (int i = 0; i < l.Length - 1; i+=2) ret += Math.Min(l[i], l[i + 1]); return ret; }
B: Mysterious Light - AtCoder Grand Contest 001 | AtCoder
1辺の長さがNの鏡3つを、反射面を内側に向けて正三角形状に組み合わせる。三角形の頂点をa,b,cとする。
辺abのある点x(aからの距離X)から、辺bcと水平に光を発射する。この光は、鏡に当たると反射するが、さらに光の軌跡に当たっても反射する不思議な性質がある。この光は、必ず元の点に戻ってくることが証明できる。光の軌跡の長さを求めよ。
2<=N<=10^12、1<=X<=N-1、NとXは整数
dfs(a,b)を、現在地(上図)からの、残りの距離を返す関数と定義して再帰的に解いた。
なおNの最大値が大きいので、Intだとオーバーフローする。
public static UInt64 Solve(UInt64 n, UInt64 x) { var ret = x + (n - x); ret += dfs(x, n - x); return ret; } public static UInt64 dfs(UInt64 a, UInt64 b) { if (a == 0 || b == 0) return 0; if (b % a == 0) { return a * 2 * (b / a - 1) + a; } var ret = (2 * a) * (b / a); if (a % (b % a) == 0) return ret + ((b % a) * 2) * (a / (b % a)) - b % a; ret += ((b % a) * 2) * (a / (b % a)); return ret + dfs(a % (b % a), b % a); }
良く分からないが、なんと3*GCD()で一発で解くこともできるらしい。
C: Shorten Diameter - AtCoder Grand Contest 001 | AtCoder
N頂点の木がある。直径をK以下にするためには、最少でいくつの頂点を削除する必要があるか。
各頂点(Kが奇数なら辺)で、距離K/2を超える頂点の数をもとめ、その最小値が解答になる。
public class Solver { static int maxDist; static List<List<int>> edges; public static int Solve(int n, int k, List<List<int>> e) { maxDist = k / 2; edges = e; var ret = Int32.MaxValue; for (int i = 0; i < n; i++ ) { if (k % 2 == 0) ret = Math.Min(ret, Dfs(i, -1, 0)); else foreach(var j in e[i]) ret = Math.Min(ret, Dfs(i, j, 0) + Dfs(j, i, 0)); } return ret; } static int Dfs(int cur, int prev, int dist) { var ret = dist > maxDist ? 1 : 0; foreach (var next in edges[cur]) { if (next == prev) continue; ret += Dfs(next, cur, dist + 1); } return ret; } }
本番では、①木の直径を求め②Kを超えていたらに端を削除、を繰り返してTLEだった。
部分点がない問題なので、TLEになりそうな時点で、実装せず別解法を考えるべきだった。
D: Arrays and Palindrome - AtCoder Grand Contest 001 | AtCoder
長さMの数列Aが与えられる。Aの総和はNである。このとき、以下を満たす数列Bを解答せよ。
次の条件を満たす長さNの文字列が、すべて同じ文字になる
先頭のa1文字、続くa2文字、さらに続くa3文字...はすべて回文
先頭のb1文字、続くb2文字、さらに続くb3文字...はすべて回文
Aの中央にある奇数長の回文が3個以上なら、Bを作ることは不可能。
それ以外なら、まず奇数を左右の端に移動したのち、どちらかの端から1つずつずらして取ったものが解答になる。
// return value: a, b.length, b public static Tuple<List<int>, int, List<int>> Solve(int n, int m, List<int> a) { if (a.Count(v => v % 2 == 1) > 2) return null; if (m == 1) { List<int> ret; if (a[0] > 2) ret = new List<int>() { a[0] - 1, 1 }; else ret = a.ToList(); return new Tuple<List<int>, int, List<int>>(a, ret.Count(), ret); } //move odd items to first and last if (a.Count(v => v % 2 == 1) > 0) { var fst = a.First(v => v % 2 == 1); a.Remove(fst); a.Insert(0, fst); var lst = a.Last(v => v % 2 == 1); var lstIdx = a.LastIndexOf(lst); a.RemoveAt(lstIdx); a.Add(lst); } var b = new List<int>() { a.Last() + 1 }; for (int i = a.Count - 2; i > 0; i--) { b.Add(a[i]); } if (a[0] > 1) b.Add(a[0] - 1); b.Reverse(); return new Tuple<List<int>, int, List<int>>(a, b.Count(), b); }
こういう問題だとLINQがとても便利。
ARC053 - ARC057メモ(練習)
ARC057
A: 2兆円 - AtCoder Regular Contest 057 | AtCoder
所持金がt円ある。ある日の所持金がt円なら、次の日には1+Kt円増えている。二兆円に達するのは何日後か。
やるだけだが、k=0のケースを考慮しないとTLEになる。
public double Solve(double a, double k) { if (k == 0) return 2E12 - a < 0 ? 0 : 2E12 - a; double n = 0; while (true) { if (a >= 2E12) break; a += (1 + k * a); n++; } return n; }
B: 高橋君ゲーム - AtCoder Regular Contest 057 | AtCoder
N日間、それぞれa[i]回のゲームを行う。i日目の勝率が0~i-1日目までの勝率より真に高かったらその日は機嫌が良い。合計でK回ゲームに勝ったとすると、機嫌のよかった日数の最大値はいくつか。
なかなか解けずに苦しんだが、問題の読み違えのせいだった。
dp[i][j]を、i日目までにj回勝率があがる場合の、最小のそれまでの勝利日数とする。
dp[i+1][]は、負けた場合と、勝率が上がりギリギリの勝利数の2パターンで計算していけば求まる。
最終的に、dp[N][j]がK以下になる最大のjが答えになる。
public class Solver { const int INF = 500000 * 2000 + 1; int[] sum; List<int> _a; public int Solve(int n, int k, List<int> a) { if (a.Sum() == k) return 1; _a = a; sum = new int[a.Count()]; sum[0] = a[0]; for (int i = 1; i < a.Count(); i++) { sum[i] = sum[i - 1] + a[i]; } var dp = new int[n, n + 1]; for (int i = 0; i < n; i++) for (int j = 0; j < n + 1; j++) dp[i, j] = INF; for (int i = 0; i < n; i++) dp[i, 0] = 0; dp[0, 1] = a[0] > 0 ? 1 : 0; for (int i = 1; i < n; i++) { for (int j = 1; j < n + 1; j++) { dp[i, j] = Math.Min(dp[i - 1, j], GetMinWinNum(dp[i - 1, j - 1], i)); } } var ret = 0; for (int i = 1; i < n + 1; i++) { if (dp[n - 1, i] > k) continue; ret = Math.Max(ret, i); } return ret; } int GetMinWinNum(int prevWinSum, int idx) { if (prevWinSum == INF) return INF; var prevWinRate = (double)prevWinSum / (double)sum[idx - 1]; var needWinCnt = (int)Math.Ceiling(prevWinRate * (double)_a[idx]); if ((double)needWinCnt / (double)_a[idx] <= prevWinRate) needWinCnt++; if (needWinCnt > _a[idx]) return INF; return prevWinSum + needWinCnt; } }
ARC056
A: みんなでワイワイみかん - AtCoder Regular Contest 056 | AtCoder
K個以上のみかんを買いたい。みかんは1個A円、もしくはL個B円。最小の支払金額を求めよ。A, B, C <= 10^9、L <= 10^9、B <= A*L
ぜんぶA円で買う・なるべくB円で買って残りをA円で買う・ぜんぶB円で買う、の3パターンしかない。intだとオーバーフローする。
static ulong Solve(ulong a, ulong b, ulong k, ulong l) { return Math.Min(k * a, Math.Min((k / l) * b + (k % l) * a, ((k / l) + 1) * b)); }
B: 駐車場 - AtCoder Regular Contest 056 | AtCoder
駐車スペースがN個あり、それぞれ1~Nに番号が振られている。各駐車スペースは双方向にM本の道でつながっている。そして駐車スペースSが入口につながっている。車i(1~N)が順番に入口から入り、かつ自分の番号の駐車スペースに停めるとき、無事に駐車できる車はどれか。
駐車スペースiに車iが駐車できるというこは、Sからiまでに、i以上の頂点のみからなる経路が存在することと同じ。Dijkstra変種で解ける。
public class Solver { public static IEnumerable<int> Solve(int n, int s, List<List<int>> e) { var dist = new int[n]; for (int i = 0; i < n; i++) dist[i] = -1; var que = new PriorityQueue<ComparablePair<int, int>>(); //desc by score que.Push(new ComparablePair<int, int>(s, s)); while (que.Count() > 0) { var nextPair = que.Pop(); var score = nextPair.Item1; var node = nextPair.Item2; if (dist[node] >= score) continue; dist[node] = score; foreach (var next in e[node]) que.Push(new ComparablePair<int, int>(Math.Min(next, score), next)); } return Enumerable.Range(1, n).Where(v => dist[v - 1] >= v - 1); } }
TLEに苦しんだけど、標準出力をFlushしてないというオチだった(ずっとアルゴリズムを疑って改善してた)。
以下のコードを忘れずに付けるようにしなければ。
Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }); foreach (var r in Solver.Solve(n, s - 1, e)) { Console.WriteLine(r); } Console.Out.Flush();
C: 部門分け - AtCoder Regular Contest 056 | AtCoder
社員がN人いて、各社員間は信頼度w[i,j]が定まっている。この会社をいくつかの部門に分けるとき、スコアを最大化せよ。
スコアは、(部門の数) x K - (異なる部門に属する2人の信頼度の総和)
1<=N<=17, 1<=w[i,j]<=10^16, 1<=K<=10^16
次のように言い換えることができる
- NxNの重み付き無向グラフの頂点を彩色する
- 使われた色の数xK-異なる色の間の重みの総和=スコア
- スコアの最大値はいくらか
Nが最大17であることに着目する。
DP[S]を頂点集合Sの解答だとすると、Sの部分集合tとuについて
DP[S] = dp[t] + k - (t-u間の重みの総和)
となる。
ある集合xの重み総和sub[x]は、その部分集合y・zについて
sub[x] = sub[y] + suz[z] + (y-z間の重みの総和)
なので、
DP[S] = dp[t] + k - sub[S] + sub[t] + sub[u]
と変形することができる。
public int Solve(int n, int k, int[,] w) { // すべての部分集合のコスト合計 var sub = new int[1 << 17]; for (int b = 0; b < 1 << n; b++) for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if (((1 << i) & b) != 0 && ((1 << j) & b) != 0) sub[b] += w[i, j]; // dp[S] は集合Sの解 var dp = new int[1 << 17]; for (int i = 0; i < 1 << n; i++) dp[i] = k; // Sを集合tと集合uに分解したとき、 // dp[S]は dp[t] + k - sub[S] + sub[t] + sub[u] になる for (int s = 0; s < 1 << n; s++) { for (int t = (s - 1) & s; t > 0; t = (t - 1) & s) { dp[s] = Math.Max(dp[s], dp[t] + k - sub[s] + sub[t] + sub[s - t]); } } return dp[(1 << n) - 1]; //dp[1 << n - 1] は通らないので注意! }
ARC055
A: 数え上げ - AtCoder Regular Contest 055 | AtCoder
1以上100以下の整数Nが与えられる。10^N+7を出力せよ。
1のあとN-1個のゼロを出力し、最後に7を出せばよい。
public string Solve(int n) { var ret = new StringBuilder(); ret.Append("1"); for (int i = 0; i < n - 1; i++) ret.Append("0"); ret.Append("7"); return ret.ToString(); }
B: せんべい - AtCoder Regular Contest 055 | AtCoder
大きさ1~Nのせんべいがランダムな順番に与えられる。大きさはそれぞれ1つずつ。与えられた時点で、食べるか食べないかを決定する。すでに見たせんべいの大小関係のみ分かる。最適戦略をとったとき、最大のせんべいNを食べることができる確率はいくらか。ただし、K枚までしか食べることはできない。
1<=K<=N<=1000
難しかった…。
今のせんべいが過去最大なら、(1)食べる(2)食べないのどちらかになる。
i番目のせんべいが過去最大になる確率は1/i、そうでない確率は1-1/i。
DFSで解けるが、「これまでの最大をすでに食べたか否か」を持たないとうまく遷移できない。
public class Solver { int _n; double[, ,] dp; public double Solve(int n, int k) { _n = n; dp = new double[n, k + 1, 2]; for (int i = 0; i < n; i++) for (int j = 0; j < k + 1; j++) for (int l = 0; l < 2; l++) dp[i, j, l] = -1; return dfs(0, k, 0); } double dfs(int idx, int k, int ateMaxVal) { if (idx == _n) return ateMaxVal; if (dp[idx, k, ateMaxVal] != -1) return dp[idx, k, ateMaxVal]; //current one is not max //rate: i - 1 / i var ret = ((double)(idx + 1 - 1) / (double)(idx + 1)) * dfs(idx + 1, k, ateMaxVal); //current one is max //rate: 1 / i //don't eat var temp = (1.0 / (double)(idx + 1)) * dfs(idx + 1, k, 0); //eat if(k > 0) temp = Math.Max(temp, (1.0 / (double)(idx + 1)) * dfs(idx + 1, k - 1, 1)); ret+=temp; dp[idx, k, ateMaxVal] = ret; return ret; } }
C: ABCAC - AtCoder Regular Contest 055 | AtCoder
長さNの文字列Sが与えられる。3つの空でない文字列A,B,Cを使い、S=ABCACと表現できる組み合わせは何通りか。
愚直に解いたら部分点になった。
public int Solve(char[] s) { var ret = 0; for (int ai = 0; ai < s.Length; ai++) for (int ci = s.Length - 1; ci > ai; ci--) if (Meet(s, ai, ci)) ret++; return ret; } bool Meet(char[] s, int ai, int ci) { var alen = ai + 1; var clen = s.Length - ci; var blen = s.Length - alen - alen - clen - clen; if(alen <= 0 || blen <= 0 || clen <= 0) return false; //check a while (ai >= 0) { if (s[ai] != s[alen + blen + clen + ai]) return false; ai--; } //check c while (ci < s.Length) { if (s[ci] != s[ci - clen - alen]) return false; ci++; } return true; }
ABC/ACの切れ目を全探索してゆく。このとき、AとCが両方存在できれば有効になる。
ACの存在を効率よく判定する方法は、ローリングハッシュでの二分探索や、Z-algorithmを使うやり方がある。
参考
ローリングハッシュ:蟻本(第二版)P.332
Z-algorithm:文字列の頭良い感じの線形アルゴリズムたち3 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
ARC054
A: 動く歩道 - AtCoder Regular Contest 054 | AtCoder
円周Lの動く歩道がある。動く歩道は、時計回りに1秒間にs進んでいる。唯一の出口が最北点から時計回りに距離Dにあり、いま距離Sにいる。1秒間にY歩けるとき、最短で何秒後に出口に着けるか。
時計回りと反時計回りを試す。
public double Solve(int l, int x, int y, int s, int d) { double leftDist = s > d ? Math.Abs(s - d) : l - Math.Abs(s - d); double rightDist = d > s ? Math.Abs(s - d) : l - Math.Abs(s - d); return s == d ? 0.0 : Math.Min(rightDist / (double)(y + x), y - x <= 0 ? double.MaxValue : leftDist / (double)(y - x)); }
B: ムーアの法則 - AtCoder Regular Contest 054 | AtCoder
現在のコンピューター性能でP年かかるタスクがある。コンピューターは、1.5年ごとに処理能力が2倍になる。なるべく早いタスクの終了時間を求めよ。(タスクは中断できないものとする)
0<=P<=10^18
x年後にタスク処理を始めるとするとき、終了時間はx+P/(2^(x/1.5))になる。これは凸関数なので、三分探索で求めることができる。
間違えてタスクの開始時間を返していたのに気づかず手間取った。
ちなみに、微分すれば一発で答えが出せるようだ。
public double Solve(double p) { double l = 0; double r = p; //ternary search while(r - l > 1E-10) { var m1 = l + (r - l) / 3.0; var m2 = l + (r - l) * 2.0 / 3.0; var t1 = m1 + p / Math.Pow(2.0, m1 / 1.5); var t2 = m2 + p / Math.Pow(2.0, m2 / 1.5); if (t1 < t2) { r = m2; } else { l = m1; } } return (l + r) / 2.0 + p / Math.Pow(2.0, ((l + r) / 2.0) / 1.5); //この計算を忘れていた }
ARC053
A: ドミノ色塗り - AtCoder Regular Contest 053 | AtCoder
H x Wのタイルがある。上下または左右に隣り合う2マスを選びたい。選び方は何通りか。
2 x W x H - (W + H) が答え。
Console.WriteLine(2 * h * w - w - h);
B: 回文分割 - AtCoder Regular Contest 053 | AtCoder
英小文字からなる文字列Sを適当にならびかえ、それを分割していくつかの回文文字列を作る。この回文文字列の長さの最小値をなるべく大きくしたい。この値を求めよ。
奇数個の文字を1つずつ、出来上がる回文文字列の中心に配置する。そして残った文字(すべて偶数個)をなるべく均等に割り振ればよい。
public static int Solve(string s) { var num = new int[26]; foreach (var c in s) num[c - 'a']++; var devideNum = 0; foreach (var n in num) if (n % 2 == 1) devideNum++; if(devideNum == 0) return s.Length; var ret = 1 + (((s.Length - devideNum) / 2) / devideNum) * 2; return ret; }
C: 魔法使い高橋君 - AtCoder Regular Contest 053 | AtCoder
N個の魔法がある。i番目の魔法を唱えると、a[i]℃温度が上がったのち、b[i]℃温度が下がる。魔法を唱える順番を調整し、気温の最大値をなるべく小さくしたい。この気温を答えよ。
温度が下がる魔法と上がる魔法に分け、下がる魔法をa[i]の昇順、上がる魔法をb[i]の降順でソートする。あとは下がる魔法→上がる魔法の順番で唱える。
public static Int64 Solve(int n, Int64[][] m) { var magics_dec = m.Where(v => v[0] < v[1]).OrderBy(v => v[0]); var magics_inc = m.Where(v => v[0] >= v[1]).OrderByDescending(v => v[1]); Int64 ret = 0, cur = 0; foreach (var magic in magics_dec.Concat(magics_inc)) { ret = Math.Max(ret, cur + magic[0]); cur += magic[0] - magic[1]; } return ret; }
これもintだとオーバーフローする。
部分的に正答になったときは、まずオーバーフローを疑うのが基本になりそう。