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

Remaining Factors

整数Nが与えられたとき、N^2を割り切るがNを割り切らない数で、N未満のものの個数を答えよ。
1 <= N <= 10^12

整数Nの素因数分解を ${ N = p_1^{k_1} P_1^{k_2} }$ とおく。 ${ N^2 = p_1^{2k_1} P_1^{2k_2} }$ なので、 ${N^2}$ の因数は ${ (2K_1+1)(2K_2+1) - 1 }$ 個とわかる。
このうちN未満のものは ${ \frac{(2K_1+1)(2K_2+1) - 1}{2} }$ 個となる。これと、 ${N}$ の因数数 ${ (k_1+1)(k_2+1) -1 }$ との差が答えとなる。

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番目のポートフォリオの収益の分散が ${\frac{1}{i}}$ であるとする。各ポートフォリオに重みづけwiを付けたとき、全体の収益分散を最小化したい。このときの期待収益と分散を答えよ。
0 <= wi <= 1
${ \sum wi = 1 }$

分散を最小化するのだから、収益は無視して重みづけwiが求められる。ポートフォリオそれぞれの分散が ${1, \frac{1}{2}, \frac{1}{3}}$ だとする。このとき、重みづけを ${\frac{1}{6}, \frac{2}{6}, \frac{3}{6} }$ のようにすれば、最終的な分散が ${\frac{1}{6}}$ になって最小化する。あとは、この重みづけを使って利益を求めればよい。

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

Guga Traveling

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