読者です 読者をやめる 読者になる 読者になる

HackerRank Week of Code - 19 参加日記

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


Fix the Cycles

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個のコンテナが、1列に配置されている。そして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を使えば解くことができる。