HackerRank Week of Code - 19 参加日記

HackerRankのWeek of Code - 19に参加したのでそのメモ。
結果は346位/3176人だった。

4つのノードA,B,C,Dをもつ有向グラフを考える。D→Aのエッジをa、A→Bのエッジをb、B→Cのエッジをc、C→Dのエッジをd、A→Cのエッジをe、B→Dのエッジをfとする。
a~fの重みが与えられたとき、負の閉路をなくすためには、最小でいくら重みを足せばよいか。ただし、1つのエッジにのみ重みを足すことができる。
不可能な場合は-1を返こと。
制約：a~fの重みの値は-20から+20

全エッジに対し、足す重み全て(0~80)をチェックするだけでよい。
ちなみに、すべてのループがエッジaを通るため、答えが-1になることはない。

static bool Success(int a, int b, int c, int d, int e, int f, int val, int idx)
{
    switch (idx)
    {
        case 0: a += val; break;
        case 1: b += val; break;
        case 2: c += val; break;
        case 3: d += val; break;
        case 4: e += val; break;
        case 5: f += val; break;
    }

    return (b + f + a >= 0) && (b + c + d + a >= 0) && (e + d + a >= 0);
}

public static int Solve(int a, int b, int c, int d, int e, int f)
{
    for (int i = 0; i <= 80; i++)
    {
        for (int j = 0; j < 6; j++)
        {
            if (Success(a, b, c, d, e, f, i, j)) return i;
        }
    }

    return -1;  //should not be here since all loops have edge 'a'
}

Two Robots

無限個のキャンディーが入ったM個のコンテナが、１列に配置されている。そして2つのロボットがある。ロボットはコンテナ間を移動して、キャンディーを運ぶことができる。
キャンディー運ぶ順番（あるコンテナから別のコンテナへ）が指定されたとき、トータルで最小のロボット移動距離を求めよ（隣り合うコンテナ間の距離を距離1とする）。

キャンディーを運ぶ順番は次のように指定される。
N　#運ぶ回数
Ma1 Mb1　#コンテナMa1からMb1に運ぶ。必ず違う値
・・・
Man　Mbn

制約： ${ 1 \leq M \leq 1000, \, 1 \leq N \leq 1000 }$

次のDPを設定し、手順を後ろからループしていく。
DP[現在のロボットAの位置][現在のロボットBの位置] ＝以降の移動距離の最小（Aの位置＜Bの位置）

単純に実装するとメモリと実行時間が足りなくなるので、(1)DP配列の再利用(2)あり得ない条件は無視して枝刈り、を行った。

public class Solver
{
    public int n = 0;
    public int m = 0;
    public Tuple<int, int>[] queries;

    public int Solve()
    {
        int[][,] dp_all = new int[][,] { new int[m + 2, m + 2], new int[m + 2, m + 2] };

        int[] minIdx = new int[m + 1];
        for (int idx = 0; idx < m + 1; idx++)
        {
            minIdx[idx] = Int32.MaxValue;
        }

        for (int idx = 0; idx < queries.Length; idx++)
        {
            var val = queries[idx].Item2;
            if (minIdx[val] == Int32.MaxValue || idx < minIdx[val])
            {
                minIdx[val] = idx;
            }
        }

        int dpIdx = 0;
        for (int idx = queries.Length - 1; idx >= 0; idx--)
        {
            var q = queries[idx];

            var pos1 = idx == 0 ? 0 : queries[idx-1].Item2;

            for (int pos2 = 0; pos2 < m + 1; pos2++)
            {
                if (pos2 != 0 && idx < minIdx[pos2]) continue;  //cannot be

                var dp = dp_all[dpIdx];
                var dp_next = dp_all[dpIdx == 0 ? 1 : 0];

                dp[Math.Min(pos1, pos2), Math.Max(pos1, pos2)] = Math.Abs(q.Item1 - q.Item2);

                var movePos1 = (pos1 == 0 ? 0 : Math.Abs(pos1 - q.Item1))
                    + ((idx == queries.Length - 1) ? 0 : dp_next[Math.Min(q.Item2, pos2), Math.Max(q.Item2, pos2)]);

                var movePos2 = (pos2 == 0 ? 0 : Math.Abs(pos2 - q.Item1))
                    + ((idx == queries.Length - 1) ? 0 : dp_next[Math.Min(q.Item2, pos1), Math.Max(q.Item2, pos1)]);

                dp[Math.Min(pos1, pos2), Math.Max(pos1, pos2)] += Math.Min(movePos1, movePos2);
            }

            dpIdx = dpIdx == 0 ? 1 : 0;
        }

        return dp_all[dpIdx == 0 ? 1 : 0][0, 0];
    }
}

Scalar Products

次の数列を考える。
${ a_0 = 0, a_1 = C, a_{i+2} = (a_{i+1} + a_i) \% M,\,where\,0 \leq i \leq 2n}$
このとき、ベクトル ${v_1, v_2, ..., v_n}$ を次のように規定する。
${v_1 = (a_2, a_3), v_2 = (a_4, a_5), ..., v_n = (a_{2n}, a_{2n+1})}$
Sを ${v_i, v_j \, (v\leq i, j \leq n)}$ のスカラ積の集合としたとき、Sの剰余の個数をMでModしたものを求めよ。
制約： ${1 \leq C \leq 10^9, 1 \leq M \leq 10^9, 1 \leq n \leq 3 \times 10^5}$

${a_0 = 0,\, a_1 = C }$ で開始するフィボナッチ数列の変種と考えればよい。

フィボナッチ数列の特徴
${ a_x \times a_y + a_{x+1} \times a_{y+1} = a_{x+y+1} }$
を利用すると、この数列に対しては
${ a_x \times a_y + a_{x+1} \times a_{y+1} = C \times a_{x+y+1} }$
が導き出せる。

よって、 ${ C \times a_{x+y+1} }$ の部分を見ていけばよい。

public class Solver
{
    public long Solve(long c, long m, long n)
    {
        c %= m;
        var resultSet = new HashSet<long>();

        var prev = c;
        long prev2 = 0;
        for (int i = 2; i <= 4 * n - 1; i++)
        {
            var val = (prev2 + prev) % m;

            if (i % 2 == 1 && i >= 7) resultSet.Add((val * c) % m);

            prev2 = prev;
            prev = val;
        }

        return resultSet.Count() % m;
    }
}

これは解けなかったのが悔しかった。
「フィボナッチ数列」で検索してみるべきだった。

Coolguy and Two Subsequences

一次元配列A[]（長さN、Indexは1から始まる）が与えられたとき、次の疑似コードで得られるansを答えよ。
//f(a, b)はA[a, b]の最小値を返す
ans = 0
for a -> [1, N]
    for b -> [a, N]
        for c -> [b + 1, N]
            for d -> [c, N]
                ans = ans + min(f(a, b), f(c, d))

ans = ans % (10^9 + 1)
制約： ${ 1 \leq N \leq 2 \times 10^5, \, 1 \leq A_i \leq 10^9 }$

まった手が出なかった。
Editorialは理解できるのだが、最後が「これをSegmentTreeを使って解けばよい」で終わっていて困る・・・。このレベルなら自明であるべきなのだろうか。

仕方ないので、SegmentTreeの集中特訓をしてから、後でもう一度解いてみることにする。

Editorialの内容

配列Aにあるすべての数字xについて、 ${ min( f(a, \, b), \, f(c,\,d) ) = x }$ になる回数を求めればよい。
これを ${ cnt(x) }$ とすると、最終的な解答は ${ sum( x \times cnt(x) ) }$ になる。

ここで、
　 ${g(x) = min( f(a, \, b), \, f(c,\,d) ) \geq x になる回数}$
と定義すると、
${cnt(x) = cnt(x) - cnt(x + 1)}$ となる。

${g(x)}$ を求めるためには、別の配列Bを用意するとよい。
BはAと同じ長さで、 ${a_i \geq x}$ なら ${b_i = 1}$ 、それ以外なら ${b_i = 0}$ のもの。

すると、 ${g(x)}$ は
　 ${x1 \leq y1}$ かつ
　 ${y1 + 1 \leq x2}$ かつ ${ x2 \leq y2 }$
になる ${(x1,\,y1,\,x2,\,y2)}$ の組み合わせのうち、
${ B[x1:y1]}$ と ${ B[x2:y2] }$ の範囲内すべてが1になるものの数と等しくなる。

${g(x)}$ はSegmentTreeを使えば解くことができる。