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);