HackerRank Week of Code 32 参加日記

C# アルゴリズム プログラミングコンテスト

396位/8447人の不本意な結果。レートも少し落ちた。
以下、Easy問題は省略する。


Circular Walk

次の式が与えられる。
{ R[i] = (R[i-1] \times g + seed) \, mod \, p }
円周上にn個の点(0~n-1)があったとき、点iから距離R[i]までジャンプすることができる。たとえばR[i]が2であれば、{i-1, i-1, i, i+1, i+2}へジャンプできる。点sから点tまでの最少ジャンプ数を答えよ。不可能な場合は-1を出力すること。
1 <= n <= 10^7
0 <= s, t <= n
1 <= p <= n
0 <= R[0], g, seed < p

現在地から到達できる最小点と最大点を保持してイテレーションしていけばよい。セグメント木で効率よく求められそうだが、nが小さいので愚直にループして間に合う。実装では面倒なエッジ処理を避けるため、最初にR[]を3つつなげ直線とみなして解いた。

public static int GetAns(int n, int s, int t, int r_0, int g, int seed, int p)
{
    var r = GetR(r_0, n, g, seed, p);
    return GetAns(n, s, t, r);
}

public static int[] GetR(int r_0, int n, int g, int seed, int p)
{
    var ret = new int[n];
    ret[0] = r_0;
    for (int i = 1; i < n; i++)
    {
        ret[i] = (ret[i - 1] * g + seed) % p;
    }
    return ret;
}

public static int GetAns(int n, int s, int t, int[] r)
{
    var newR = new int[r.Length * 3];
    for (int i = 0; i < r.Length; i++)
    {
        newR[i] = newR[i + n] = newR[i + 2 * n] = r[i];
    }

    var ts = new List<int>{ t, t + n, t + 2 * n };
    var left = s + n;
    var right = s + n;
    var oldLeft = -1;
    var oldRight = -1;

    var ret = 0;
    while (true)
    {
        if (left < 0 || right >= newR.Length) break;  //fail safe

        foreach (var tc in ts)
        {
            if (left <= tc && tc <= right) return ret;
        }

        var newLeft = left;
        var newRight = right;

        var cur = left;
        while (cur <= right)
        {
            if (oldLeft != -1 && cur == oldLeft) cur = oldRight + 1;

            newLeft = Math.Min(newLeft, cur - newR[cur]);
            newRight = Math.Max(newRight, cur + newR[cur]);

            cur++;
        }

        if (newLeft == left && newRight == right) break;    //no change -> no answer
        oldLeft = left;
        oldRight = right;
        left = newLeft;
        right = newRight;

        ret++;
    }

    return -1;
}


Geometric Trick

a,b,cからなる長さnの文字列sがある。次を満たす(i,j,k)の組み合わせ数を答えよ。

  • s[i] = "a", s[j] = "b", s[k] = "c"
  • (j + 1)^2 = (i + 1)(k + 1)

1 <= n <= 5 x 10^5

i*kが平方数のとき、iの素因数のうちべき乗数が奇数のものと、とkの素因数のうちべき乗数が奇数のものが一致する。たとえば
i = 3^2 * 5^1 * 7*2
k = 5^3 * 11*2
とすると、べき乗数が奇数になっている素因数はi、kともに5で一致しているため、i*kは平方数になる。
これを利用し、i、kすべてについてこの情報（べき乗数が奇数の素因数組み合わせ）が同じものどおしで、i*kがj*jの集合に存在するかチェックすればよい。情報の一致不一致はHash化して判断する。また、素因数分解はエラトステネスの篩の応用で高速に求められる。

// s[i] = 'a', s[j] = 'b', s[k] = 'c'
// (j + 1) ^ 2 = (i + 1)(k + 1)
public static long GetAns(string s)
{
    var Is = new List<int>();
    var J_pows = new HashSet<long>();
    var Ks = new List<int>();
    for (int i = 0; i < s.Length; i++)
    {
        if (s[i] == 'a') Is.Add(i + 1);
        if (s[i] == 'b') J_pows.Add((long)(i + 1) * (i + 1));
        if (s[i] == 'c') Ks.Add(i + 1);
    }

    // sieve (2-s.Length + 1)
    var p = new int[s.Length + 2];
    for (int i = 2; i < p.Length; i++)
    {
        if (p[i] != 0) continue;
        for (int j = i; j < p.Length; j += i) p[j] = i;
    }

    // hash list
    var rnd = new Random();
    var hashList = new long[s.Length + 2];
    for (int i = 1; i < hashList.Length; i++) hashList[i] = ((hashList[i - 1] * 37L + 123847L) << 31) + rnd.Next();

    // prime hash => i/j values
    var i_hashes = GetHashes(Is, p, hashList);
    var k_hashes = GetHashes(Ks, p, hashList);

    var ret = 0L;

    foreach (var hash in i_hashes.Keys)
    {
        foreach (var i in i_hashes[hash])
        {
            if (!k_hashes.ContainsKey(hash)) continue;
            foreach(var k in k_hashes[hash])
            {
                if (J_pows.Contains((long)i * k)) ret++;
            }
        }
    }

    return ret;
}

static Dictionary<long, List<int>> GetHashes(List<int> values, int[] primes, long[] hashes)
{
    var ret = new Dictionary<long, List<int>>();
    foreach (var v in values)
    {
        var hash = GetHash(v, primes, hashes);
        if (!ret.ContainsKey(hash)) ret.Add(hash, new List<int>());
        ret[hash].Add(v);
    }
    return ret;
}

static long GetHash(int value, int[] primes, long[] hashes)
{
    if (value == 1) return 0;
    var curIdx = value;
    var ret = 0L;
    do
    {
        ret ^= hashes[primes[curIdx]];
        curIdx /= primes[curIdx];
    } while (curIdx > 1);

    return ret;
}


Balls and Boxes

n種類の色があり、色iのボールがA[i]個ある。さらにm個の箱があり、箱jにはC[j]個のボールが入る。

  • 箱には、同色のボールは2個以上は入らない
  • 色iのボールを箱jに入れると、B[i][j]のキャンディーがもらえる
  • 箱にC[j]個より多くのボールを入れると、ペナルティとして超過分^2のキャンディを払う

のとき、なるべく多くのキャンディーを稼げ。
1 <= n, m <= 100
1 <= A[i] <= 100
0 <= C[i] <= 100
0 <= B[i][j] <= 10^3

次のような最小費用流の問題に還元できる(Uは大きな値)。
f:id:yambe2002:20170602124236j:plain
最小費用はたとえば
U - ボーナス[0]
U - ボーナス[1] + ペナルティ
U
U - ボーナス[3]
のような合計値になる(色2は箱に入れられていない)。最終的に求めたいのはボーナスとペナルティの合計だから、Sum(A)＊Uからこの値を引いたものが解答になる。

public static int GetAns(int n, int m, int[] a, int[] c, int[][] b)
{
    var total = a.Sum();

    var graph = new MinCostFlow(n + m + 2 + 1);
    var s = n + m;
    var t = s + 1;

    var U = 3000;

    // colors
    for (int col = 0; col < n; col++)
    {
        graph.AddEdge(s, col, a[col], 0);
        graph.AddEdge(col, t, a[col], U);
    }

    // boxes
    for (int box = 0; box < m; box++)
    {
        var boxNode = box + n;

        // ordinal
        graph.AddEdge(boxNode, t, c[box], 0);

        // additional
        for (int j = 1; j <= 30; j++)
        {
            graph.AddEdge(boxNode, t, 1, 2 * j - 1);
        }
    }

    for (int col = 0; col < n; col++)
    {
        for (int box = 0; box < m; box++)
        {
            var boxNode = box + n;
            graph.AddEdge(col, boxNode, 1, U - b[col][box]);
        }
    }

    var flow = U * total - graph.GetMinCostFlow(s, t, total);
    return flow;
}

public class MinCostFlow
{
    const int INF = 1 << 30;

    class Edge
    {
        public int v, r;
        public int c, w;
        public Edge(int v, int c, int w, int r)
        {
            this.v = v;
            this.c = c;
            this.w = w;
            this.r = r;
        }
    }

    List<List<Edge>> _graph;

    public MinCostFlow(int n)
    {
        _graph = new List<List<Edge>>();
        for (int i = 0; i < n; i++) _graph.Add(new List<Edge>());
    }

    public void AddEdge(int u, int v, int c, int w)
    {
        int x = _graph[u].Count();
        int y = _graph[v].Count();
        _graph[u].Add(new Edge(v, c, w, y));
        _graph[v].Add(new Edge(u, 0, -w, x));
    }

    List<T> GetList<T>(int size)
    {
        var ret = new List<T>();
        for (int i = 0; i < size; i++) ret.Add(default(T));
        return ret;
    }

    public int GetMinCostFlow(int s, int t, int f)
    {
        int n = _graph.Count();
        int ret = 0;
        var h = GetList<int>(n);
        var dist = GetList<int>(n);
        var cap = GetList<int>(n);
        var use = GetList<int>(n);

        while (f > 0)
        {
            var q = new PriorityQueue<ComparablePair<int, int>>(1);
            for (int i = 0; i < dist.Count(); i++) dist[i] = INF;
            dist[s] = 0;
            cap[s] = f;
            q.Push(new ComparablePair<int, int>(0, s));
            while (q.Count() != 0)
            {
                var d = -q.Peek().Item1;
                var u = q.Peek().Item2;
                q.Pop();
                if (dist[u] != d)
                {
                    continue;
                }
                foreach (var e in _graph[u])
                {
                    if (e.c > 0 && dist[e.v] > dist[u] + e.w + h[u] - h[e.v])
                    {
                        dist[e.v] = dist[u] + e.w + h[u] - h[e.v];
                        q.Push(new ComparablePair<int, int>(-dist[e.v], e.v));
                        use[e.v] = e.r;
                        cap[e.v] = Math.Min(cap[u], e.c);
                    }
                }
            }
            if (dist[t] == INF)
            {
                return -1;
            }
            int v = t;
            while (v != s)
            {
                int u = _graph[v][use[v]].v;
                int x = _graph[v][use[v]].r;
                int y = use[v];
                _graph[u][x].c -= cap[t];
                _graph[v][y].c += cap[t];
                ret += cap[t] * _graph[u][x].w;
                v = u;
            }
            for (int i = 0; i < n; i++)
            {
                h[i] += dist[i];
            }
            f -= cap[t];
        }
        return ret;
    }
}

MinCostFlowは蟻本より。C#だとTLEぎりぎりになるようだ。なお本番ではMinCostの算出にPrimal-Dualを使っていたのと、二分探索でFlowを固定して最小費用を複数回もとめたので多くのケースでTLEになっていた。