HackerRank Week of Code - 22 参加日記

457位/12356人。Mediumを1つ落としたのが痛い。いつも数学がネックだ・・・。

Cookie Party

n人のゲストとm枚のクッキーがある。ゲスト全員に同じ枚数を配るためには、あと何枚クッキーを焼けばよいか。

クッキーがすでに足りているか、足りない場合はゲストの人数で割り切れるかで場合分けする。

if (m <= n)
    Console.WriteLine(n - m);
else if (m % n == 0)
    Console.WriteLine(0);
else
    Console.WriteLine((m / n + 1) * n - m);


Making Polygons

N本の棒aiが与えられる。この棒すべてを使って非退化な多角形を作るには、最少で何本の棒を折る必要があるか。折れた棒は両方使うものとする。
1 <= N <= 50
1 <= ai <= 100

「非退化」というのは重なった辺も、長さゼロの辺も存在しないという意味で、要するに普通の多角形のことらしい。
1本しかないときは、当然2回折らないと多角形にならない。
2本のときは、同じ長さなら2回、違う長さなら1回折る必要がある。
3本以上あるなら、
 最長の辺の長さ > それ以外の辺の長さ合計
に合致したら一本も折らなくてよい。それ以外のときは、最長のものを1回折る必要がある。

if (a.Count() == 1)
{
    Console.WriteLine(2);
}
else if (a.Count() == 2)
{
    if (a[0] == a[1]) Console.WriteLine(2);
    else Console.WriteLine(1);
}
else
{
    if (a[0] < a.Sum() - a[0]) Console.WriteLine(0);
    else Console.WriteLine(1);
}

理屈は簡単だが、棒が1本からという条件を見逃すとWAになってしまう。


Matching Sets

2つの整数の集合{ X = { x_0, x_1, ..., x_{n-1} }, Y = { y_0, y_1, ..., y_{n-1} } }があり、次のオペレーションが可能である。
1、XとYから1つずつ{ x_i, x_j }を選ぶ({ i \neq j})
2,{ x_i }から1引き、 { y_j }に1足す
XとYが等しくなる最少のオペレーション回数を求めよ。不可能な場合は-1を返すこと。

XとYの合計が異なるときは不可能。それ以外であれば、両方ともソートして1つずつオペレーションしていけば良い。

if (x.Sum() != y.Sum())
{
    Console.WriteLine(-1);
    return;
}

Int64 diff = 0;
x.Sort();
y.Sort();
for (int i = 0; i < n; i++)
{
    diff += Math.Abs(x[i] - y[i]);
}

Console.WriteLine(diff / 2);


Number of Sequences

整数の数列が次を満足するとき、この数列はNiceであるとする
{ 0 \leq a_k \leq k - 1 }
{ a_k \equiv\,a_m\,mod\,k } (kがmを割り切るすべてのk,mのペアについて)
一部が-1になっている整数の数列nが与えられる。-1に任意の数字を入れたとき、この数列がNiceになる組み合わせ数を求めよ。

まず、a[i]の添え字がa[p*q]と素因数分解できるものは無視することができる(中国の剰余定理によりa[p]とa[q]が決まっていれば、a[p*q]が一意に求まるため)。
そして、各素数のべき乗番目
 a[p], a[p^2], a[p^3] ... (p^x < n)
について、値が-1ならp通りのパターンがある。
たとえば、p=3のとき
 a[3]: -1 → あり得る値は { 0, 1, 2 }
 a[9]: -1 → あり得る値は { 0, 1, 2, 3, 4, 5, 6, 7, 8 }
となるが、a[3]でどの値が選ばれたとしても、a[9]で候補になる数は9/3=3個になる。

static void Main(string[] args)
{
    Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });

    var n = Int32.Parse(Console.ReadLine());
    var a = ReadLine().Split().Select(s => Int32.Parse(s)).ToList();
    a.Insert(0, 0);

    //それぞれのkの因数すべて
    var facts = Enumerable.Range(0, n + 1).Select(v => new List<int>()).ToList();
    for (var k = 2; k <= n; k++)
    {
        Int64 kp = k;
        while (kp <= n)
        {
            facts[(int)kp].Add(k);
            kp += k;
        }
    }

    //すでに値がある場合に、Niceに違反する因数がないかチェック
    for (var k = n; k > 0; k--)
    {
        if (a[k] == -1) continue;
        foreach (var fact in facts[k])
        {
            if (a[fact] != -1 && a[fact] != a[k] % fact)
            {
                Console.WriteLine(0);
                Console.Out.Flush();
                return;
            }
            a[fact] = a[k] % fact;
        }
    }

    //kが(素数^p)で表せるならその素数を取得
    var basePrimes = new int[n + 1];
    for (var k = 2; k <= n; k++)
    {
        if (facts[k].Count() == 1)
        {
            Int64 kp = k;
            while (kp <= n)
            {
                basePrimes[kp] = k;
                kp *= k;
            }
        }
    }

    //a[k]が-1かつkが(素数^p)で表せるなら、k通りの組み合わせがある
    Int64 ret = 1;
    for (var k = 2; k <= n; k++)
    {
        if (a[k] == -1 && basePrimes[k] != 0)
        {
            ret *= (Int64)basePrimes[k];
            ret %= 1000000007;
        }
    }

    Console.WriteLine(ret);
    Console.Out.Flush();
}


Submask Queries

要素数nの集合{ U = {1, 2, ..., n} }がある。Uの部分集合すべてに値0が代入されている。
この時、次の3タイプのクエリが渡される。
1. 1 x S:集合Sの部分集合すべてに値xを代入する
2. 2 x S:集合Sの部分集合すべての値についてxとXORをとる
3. 3 s:集合Sの値を出力する
クエリが連続で与えられるので、出力値を求めよ。
1 <= n <= 16
1 <= m(クエリ数) <= 10^5
0 <= x <= 2^30 - 1

最後に代入された時間と値、そしてそこからのXOR合算を効率よく求める必要がある。
各クエリごとのループ回数を少なくするため、下位8ビットと上位8ビットに平方分割する。クエリ1・2では、下位8ビットのサブセットすべてについて、以下の情報を保持していく。

var set_times = new int[1 << 8, 1 << 8];   //最後に代入した時間
var set_values = new int[1 << 8, 1 << 8];  //代入された値
var xor_time = new List<ComparablePair<int, int>>[1 << 8, 1 << 8];  // XORした時間と、そこまでのXOR合算

クエリ3では、①該当ビットに最後に代入された値を取得し、②その時間をもとにそこからのXOR合算を算出する。
たとえば、
1:XOR、2:代入、3:XOR、4:代入、5:代入、6:XOR、7:XOR
だったとしたら、最終的な値は5で代入された値へ、3までのXOR合算と7までのXOR合算をXORしたものになる。この、最後の代入の直前のXORは、時間で二分探索すれば求められる。
①②いずれも、上位8ビットのスーパーセットすべて+下位8ビットのパターンで行えばよい。

static void Main(string[] args)
{
    Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });

    var str = Console.ReadLine().Split();
    var n = Int32.Parse(str[0]);
    var m = Int32.Parse(str[1]);

    var set_times = new int[1 << 8, 1 << 8];   //last updated time to [H, L]
    var set_values = new int[1 << 8, 1 << 8];  //[H, L] => value of mask { all subsets of H } + L
    var xor_time = new List<ComparablePair<int, int>>[1 << 8, 1 << 8];  // time of xor -> xor value of mask [H, L]

    for (int i = 0; i < 1 << 8; i++)
    {
        for (int j = 0; j < 1 << 8; j++)
        {
            set_times[i, j] = -1;
            xor_time[i, j] = new List<ComparablePair<int, int>>() { new ComparablePair<int, int>(-1, 0) };
        }
    }

    for (int i = 0; i < m; i++)
    {
        str = Console.ReadLine().Split();
        var bit = 0;
        for (int j = 0; j < n; j++)
        {
            bit *= 2;
            if (str[str[0] == "1" || str[0] == "2" ? 2 : 1][j] == '1') bit += 1;
        }
        var top = bit >> 8;
        var bottom = bit & 0xFF;

        //assign
        if (str[0] == "1")
        {
            var val = Int32.Parse(str[1]);
            var sub = bottom;
            do
            {
                set_values[top, sub] = val;
                set_times[top, sub] = i;
                sub = (sub - 1) & bottom;
            } while (sub != bottom);
        }

        //xor
        if (str[0] == "2")
        {
            var val = Int32.Parse(str[1]);
            var sub = bottom;
            do
            {
                xor_time[top, sub].Add(new ComparablePair<int, int>(i, val ^ xor_time[top, sub].Last().Item2));
                sub = (sub - 1) & bottom;
            } while (sub != bottom);
        }

        //print
        if (str[0] == "3")
        {
            //find the last updated time and its time
            var val = 0;
            var lastUpdated = -1;

            //iterate supersets of top
            var comp = ~top & 0xFF;
            for (int sub = comp; ; sub = (sub - 1) & comp)
            {
                int super_top = top | sub;  //superset of top
                if (set_times[super_top, bottom] > lastUpdated)
                {
                    lastUpdated = set_times[super_top, bottom];
                    val = set_values[super_top, bottom];
                }
                if (sub == 0) break;
            }

            //apply xors from the last updated time
            comp = ~top & 0xFF;
            for (int sub = comp; ; sub = (sub - 1) & comp)
            {
                int super_top = top | sub;  //superset of top
                var tgt_xors = xor_time[super_top, bottom];

                var right_xor = tgt_xors.Last().Item2;
                var left_xor = GetLastXor_BeforeLastUpdate(tgt_xors, lastUpdated).Item2; //get the last xor-ed value before the update time using binary search

                // getting xors from i to j: xor(0..j) ^ xor(0..i-1)
                val ^= (left_xor ^ right_xor);

                if (sub == 0) break;
            }

            Console.WriteLine(val);
        }
    }

    Console.Out.Flush();
}

//return [upper_bound() - 1], xors are sorted by item1
static ComparablePair<int, int> GetLastXor_BeforeLastUpdate(List<ComparablePair<int, int>> xors, int time)
{
    var lb = -1;
    var ub = xors.Count();

    while (ub - lb > 1)
    {
        var mid = (lb + ub) / 2;
        if (xors[mid].Item1 <= time)
        {
            lb = mid;
        }
        else
        {
            ub = mid;
        }
    }

    return xors[lb];
}

AGC003の参加日記

2完で416位/700人くらい。AtCoderのコンテストは問題文が分かりやすくて良い(日本語だからというだけじゃなく)。


A - Wanna go back home

二次元平面上のある点から、1ターンずつ東西南北いずれかに正の距離移動する。ターンごとの方角が与えられたとき、元の位置に戻ることができるか。

東西と南北それぞれについて、たとえば東だけなどある方向に行きっぱなしになっていなければ、元の位置に戻ることができる。

if (((str.Count(c => c == 'E') == 0 && str.Count(c => c == 'W') == 0) || (str.Count(c => c == 'E') > 0 && str.Count(c => c == 'W') > 0)) &&
    ((str.Count(c => c == 'N') == 0 && str.Count(c => c == 'S') == 0) || (str.Count(c => c == 'N') > 0 && str.Count(c => c == 'S') > 0)) )
{
    Console.WriteLine("Yes");
}
else
{
    Console.WriteLine("No");
}


B - Simplified mahjong

1からNまでの整数が書かれたカードが、それぞれAi枚ある。2枚のカードについて、整数の差の絶対値が1以下ならペアを作ることができる。作ることのできるペアの最大数を求めよ。

連続したカードごとのグループを作り、グループ内のカード枚数/2を合計すればよい。

Int64 ret = 0;
Int64 sum = 0;
for (int i = 0; i < a.Count(); i++)
{
    if (a[i] == 0)
    {
        ret += sum / 2;
        sum = 0;
    }
    else sum += a[i];
}
ret += sum / 2;
Console.WriteLine(ret);


C - BBuBBBlesort!

長さNの数列Aに以下の操作を行い、昇順にソートする。
・操作1:連続する2つの要素の順番を反転
・操作2:連続する3つの要素の順番を反転
最少の操作1の回数を答えよ。
1 <= N <= 10^5
0 <= Ai <= 10^0 (整数のみ)

操作2は何回行ってもも構わないので、奇数位置にある値はコストなしで動かすことができる。よって、偶数位置にあるものを、奇数位置へ動かす回数が答えとなる。
(同じ回数だけ、奇数位置から偶数位置に動かすものがある)

var n = Int32.Parse(Console.ReadLine());
var a = new List<Int64>();
var dictIdx = new Dictionary<Int64, int>();
for (int i = 0; i < n; i++)
{
    a.Add(Int64.Parse(Console.ReadLine()));
    dictIdx.Add(a[i], i);
}

var wk = a.OrderBy(v => v).ToList();
var indices = new Int64[n];
for (int i = 0; i < wk.Count; i++)
{
    indices[dictIdx[wk[i]]] = i;
}

Int64 ret = 0;
for (int i = 0; i < a.Count(); i++)
{
    if (i % 2 == 0 && indices[i] % 2 == 1) ret++;
}
Console.WriteLine(ret);

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

Morgan Stanley Codeathon 2016の参加日記

3完1部分点で暫定192位/3601人。数学が分からなくて苦しんだ。


Jesse and Profit

ある銘柄の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);

AGC002の参加日記

AGC第二回。2完397位/662人で惨敗。

A - Range Product

整数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");


B - Box and Ball

箱が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());


C - Knot Puzzle

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

閃けばひどく単純に解けるが、思いつかないとかなり嵌るタイプの問題だった。


D - Stamp Rally

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人。さっさともう一問解けるようになりたい。

A - 天下一プログラマーゲーム

1~100の数のうち、3と5のいずれでも割り切れない数の合計を求めよ。

Console.WriteLine(Enumerable.Range(1, 100).Where(s => s % 3 != 0 && s % 5 != 0).Sum());

このFizzbuzz的難問が解ければ上位0.5%のプログラマのはず。
参考:どうしてプログラマに・・・プログラムが書けないのか?


B - PackDrop

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


C - 山田山本問題

文字列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");
}


D - グラフィカルグラフ

重複のない大文字のアルファベットからなる無向木がある。この木の各頂点に接続する辺の本数は、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

CamelCaseの文字列に、英単語がいくつあるか答えよ。

大文字の数+1を返せばよい。

Console.WriteLine(str.Count(s => s >= 'A' && s <= 'Z') + 1);


String Construction

空文字列pに以下の操作を行い、文字列sを作りたい。最小のコストを答えよ。
・p末尾に任意の文字を足す(1ドル)
・p内の部分文字列を、p末尾に足す(0ドル)

2度目以降に使う文字にはコストがかからないので、sから重複を排除した文字数を答えればよい。

Console.WriteLine(s.Distinct().Count());


Short Palindrome

英小文字のみからなる文字列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をループすることで求めることができる。
f:id:yambe2002:20160725053056p:plain

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()は個人ライブラリより。


Balanced Forest

ノード数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以上なのだから、もっと簡略化できそうな気がする。
(あるノードのサブ木合計値が、そのノードの子で発生することは有り得ないため)