HackerRank Week of Code 30 参加日記

C# プログラミングコンテスト

289位/10554人でレートほぼ変化なし。以下、難易度EasyとMediumのものは省略する。

Poles

斜面上にn本のポールがあり、それぞれ高度x[i]と重さw[i]が与えられる（高度はユニーク）。これをk本のスタックにまとめたい。
・スタック位置はもともとポールがあった場所のみ有効
・ポールは下にのみ移動できる
・移動には、(ポールの重さx高度差)のコストがかかる
このときの最小コストを求めよ。
1 <= k < n <= 5000
1 <= w[i], x[i] <= 10^6
ポールは高度順（昇順）で与えられる

以下、ポールの順序を逆転して考える(0が一番上、n-1が一番下。必ず1番下のポール位置を使うことがヒントになる）。
F(n, k)を、ポール0~nでk個のスタックを作ったときの最小コストと定義する。
{F(n, k) = \min_{ 1 \leq x \leq n } F(n-1, k-1) + \sum_{i=x}^{n}(x_i - x_n) * w_i}
{F(n, k) = \min_{ 1 \leq x \leq n } F(n-1, k-1) + \sum_{i=x}^{n} x_i * w_i - \sum_{i=x}^{n} x_n * w_i}
{F(n, k) = \min_{ 1 \leq x \leq n } F(n-1, k-1) + \sum_{i=x}^{n} x_i * w_i - x_n * \sum_{i=x}^{n} w_i}
{A(n) = \sum_{i=1}^{n} w_i}、{ B(n) = \sum_{i=1}^{n} x_i * w_i }とすると、
{F(n, k) = \min_{1 \leq x \leq n} F(x-1, k-1) + B(n) - B(n-1) - x_n * [A(n) - A(x-1)] }
{F(n, k) = B(n) - x_n * A(n) + \min_{1 \leq x \leq n} F(x-1,k-1) - B(x-1) + x_n * A(n-1)}
このように展開すると、まず{B(n) - x_n * A(n)}の部分は予め計算すれば定数時間で求めることができる。
そして、{\min_{1 \leq x \leq n} F(x-1,k-1) - B(x-1) + x_n * A(n-1)}の部分は、独立項{F(x-1,k-1) - B(x-1)}、傾き{A(n-1)}の線集合について、最小値を求めることと同義。傾き{ A(n-1) }は単調増加しているので、Convex Hull Trickを使うといちいちループせずとも効率よく求めることができる。
Convex Hull Trickはこのサイトが分かりやすかった。
http://wcipeg.com/wiki/Convex_hull_trick

class Program
{
    const int MAXN = 5000;
    static double[] weight = new double[MAXN + 5];
    static double[] pos = new double[MAXN + 5];
    static double[] A = new double[MAXN + 5];
    static double[] B = new double[MAXN + 5];
    static double[] F = new double[MAXN + 5];
    static double[,] dp = new double[MAXN, 2];

    static void Main(string[] args)
    {
        int N, K, x, k;

        var s = Console.ReadLine().Split().Select(v => Int32.Parse(v)).ToList();
        N = s[0];
        K = s[1];

        for (x = N - 1; x >= 0; --x)
        {
            s = Console.ReadLine().Split().Select(v => Int32.Parse(v)).ToList();
            pos[x] = s[0];
            weight[x] = s[1];
        }

        for (x = 0; x < N; ++x)
        {
            A[x] = weight[x] + (x > 0 ? A[x - 1] : 0);
            B[x] = pos[x] * weight[x] + (x > 0 ? B[x - 1] : 0);
            F[x] = dp[x, 1] = B[x] - pos[x] * A[x];
        }

        var convexHullTrick = new ConvexHullTrick();

        for (k = 2; k <= K; ++k)
        {
            convexHullTrick.Init();

            convexHullTrick.AddLine(A[k - 2], dp[k - 2, (k - 1) & 1] - B[k - 2]);

            for (x = k - 1; x < N; ++x)
            {
                if (k == x + 1)
                    dp[x, k & 1] = 0;
                else
                    dp[x, k & 1] = F[x] + convexHullTrick.Query(pos[x], true);

                convexHullTrick.AddLine(A[x], dp[x, (k - 1) & 1] - B[x]);
            }
        }

        Console.WriteLine((double)dp[N - 1, K & 1]);
    }
}

public class ConvexHullTrick
{
    class Line
    {
        public double A;
        public double B;

        public Line(double a, double b)
        {
            A = a;
            B = b;
        }

        public double GetY(double x)
        {
            return A * x + B;
        }
    }

    Deque<Line> lines = new Deque<Line>();

    public void Init()
    {
        lines.Init();
    }

    // y = ax + b
    public void AddLine(double a, double b)
    {
        Insert(new Line(a, b));
    }

    double Area(Line a, Line b, Line c)
    {
        var ax = (b.A - a.A);
        var bx = (c.B - a.B);
        var ay = (c.A - a.A);
        var by = (b.B - a.B);
        return ax * bx - ay * by;
    }

    bool Cw(Line a, Line b, Line c)
    {
        return Area(a, b, c) < 0;
    }

    void Insert(Line l)
    {
        while (lines.Count > 1 && Cw(lines[lines.Count - 2], lines[lines.Count - 1], l))
        {
            lines.PopBack();
        }

        if (lines.Count == 1)
        {
            if (lines[0].B > l.B)
                lines.PushBack(l);
        }
        else
        {
            lines.PushBack(l);
        }
    }

    public double Query(double x, bool canRemoveFrontLines = false)
    {
        if (lines.Count == 0)
        {
            return 0;
        }

        if (canRemoveFrontLines)
        {
            while (lines.Count > 1 && lines[0].GetY(x) > lines[1].GetY(x))
            {
                lines.PopFront();
            }
            return lines[0].GetY(x);
        }
        else
        {
            for (int i = 0; i < lines.Count - 1; i++)
            {
                if (lines[i].GetY(x) < lines[i + 1].GetY(x))
                {
                    return lines[i].GetY(x);
                }
            }
        }

        return lines[lines.Count - 1].GetY(x);
    }
}

DequeはC++のDequeをC#で実装した個人ライブラリのもの。List等だとTLEになる。


Range Modular Queries

整数の数列{ A = [ a_0, a_1, ..., a_{n-1} ] }が与えられる。次にq個のクエリが"left right x y"の形で与えられる。クエリごとに、数列で以下の条件を満たす要素数を答えよ。
{ left \leq i \leq right}
{ a_i \equiv y (mod \, x) }
（制約）
1 <= n, q, <= 4 x 10^4
0 <= a[i] <= 4 x 10^4
0 <= left <= right < n
1 <= x <= x x 10^4
0 <= y < x

・xが小さいとき
あらかじめ、x,yのすべての組み合わせについて、a[i]%x==y を満たす要素番号を配列で持てばよい。Left・Rightで二分探索すればO(logN)で求めることができる。
・xが大きいとき
xが大きいとあらかじめ準備することが不可能になる。その代わりa[i]の組み合わせ数が小さくなるので、こちらを列挙できる。同様に、あり得るa[i]の組み合わせ分だけそれぞれ要素番号を持っておけば、Left・Rightでの二分探索が可能になる。

class Program
{
    static int N = 40000;
    static int K = 200; //sqrt(N)

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

        // [x, y] => list of all indices satisfy a[i] % x == y
        var pos = new List<int>[K + 2, K + 2];
        for (int i = 0; i < K + 2; i++) for (int j = 0; j < K + 2; j++) pos[i, j] = new List<int>();

        // [z] => list of all indices satisfy a[i] == z
        var poss = new List<int>[N + 1];
        for (int i = 0; i < N + 1; i++) poss[i] = new List<int>();

        int n, q;
        var str = Console.ReadLine().Split().Select(v => Int32.Parse(v)).ToArray();
        n = str[0];
        q = str[1];

        var a = ReadLine().Split().Select(v => Int32.Parse(v)).ToArray();

        for (var i = 1; i < K; i++)
        {
            for (int j = 0; j < n; j++)
            {
                pos[i, a[j] % i].Add(j);
            }
        }

        for (var i = 0; i < n; i++)
        {
            poss[a[i]].Add(i);
        }

        for (var i = 0; i < q; i++)
        {
            str = Console.ReadLine().Split().Select(v => Int32.Parse(v)).ToArray();
            var l = str[0];
            var r = str[1];
            var x = str[2];
            var y = str[3];

            int ans = 0;
            if (x < K)
            {
                int st = LowerBound(pos[x, y], l);
                int en = UpperBound(pos[x, y], r);
                --en;
                if (en - st + 1 >= 1) ans += en - st + 1;
            }
            else
            {
                // iterate through all a[i] candidates that satisfy a[i] % x == y
                for (int z = y; z <= 40000; z += x)
                {
                    // count the number within the range
                    int st = LowerBound(poss[z], l);
                    int en = UpperBound(poss[z], r);
                    --en;
                    if (en - st + 1 >= 1) ans += en - st + 1;
                }
            }

            Console.WriteLine(ans);
        }

        Console.Out.Flush();
    }
}

LowerBound()とUpperBound()は個人ライブラリのもの。


A Graph Problem

以下の２つを定義する。
・無向グラフGの三角形の数を、辺(u, v)・(u, w)・(v, w)がGの辺であるトリプル{u, v, w}(順序は問わない)の数と定義する
・グラフG'を、三角形の数/頂点数が最大となるグラフGのvertex-induced sub-graphと定義する
Gが与えられたとき、G'のいずれか一つを出力せよ。
1 <= 頂点数 <= 50

例として、次のグラフを考える。
f:id:yambe2002:20170408022715p:plain
これを以下のようなS-Tグラフに変換する。
f:id:yambe2002:20170408022722p:plain
このグラフをよく観察すると、
・m = 0.1のとき
最大フローは三角形の数より小さい
・m = 0.333...のとき
最大フローは三角形の数より小さい。三角形Aからのフローは1になるが、三角形B+Cからのフローが2に満たないので。
・m = 0.5のとき
最大フローは三角形の数と等しくなる。三角形Aからのフローは1、三角形B+Cからのフローが2になる。
・mがそれより大きいとき
最大フローは三角形の数と等しくなる
となっている。つまり、ちょうどフローと三角形の数が等しくなる場合のmが、求める「三角形の数/頂点数が最大」となることが分かる。よって、mを使って二分探索すれば解が求められる。
最終的な解は、「ちょうどフローと三角形の数が等しくなる場合」よりも少しだけ小さいmを使って最大フローを求めたときの、T側の集合（Maximum Closure Problemの最適解ではないほうの集合）になる。

class Program
{
    static double MAX_FLOW = double.MaxValue;

    static void Main(string[] args)
    {
        var n = Int32.Parse(Console.ReadLine());

        // graph
        var g = new bool[n, n];
        for (var i = 0; i < n; i++)
        {
            var s = Console.ReadLine().Split().Select(v => v == "1").ToArray();
            for (var j = 0; j < n; j++)
            {
                g[i, j] = s[j];
            }
        }

        // triangles
        var t = new List<Tuple<int, int, int>>();
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < i; ++j)
            {
                for (int k = 0; k < j; ++k)
                {
                    if (g[i, j] && g[j, k] && g[k, i])
                    {
                        t.Add(new Tuple<int, int, int>(i, j, k));
                    }
                }
            }
        }

        int S, T;
        S = t.Count() + n;
        T = t.Count() + n + 1;
        Dinic graph = new Dinic();

        double l = 0, r = 50 * 50 * 50;
        while ((r - l) > 1e-10)
        {
            double m = (l + r) / 2;

            graph.Init();
                
            for (var i = 0; i < n; i++)
            {
                graph.AddEdge(S, t.Count() + i, m);
            }
            for (var i = 0; i < t.Count(); i++)
            {
                graph.AddEdge(t.Count() + t[i].Item1, i, MAX_FLOW);
                graph.AddEdge(t.Count() + t[i].Item2, i, MAX_FLOW);
                graph.AddEdge(t.Count() + t[i].Item3, i, MAX_FLOW);
                graph.AddEdge(i, T, 1);
            }

            var x = graph.GetMaxFlow(S, T);

            if (t.Count() > x)
            {
                l = m;
            }
            else
            {
                r = m;
            }

        }

        var ret = graph.GetStCut(S).Where(v => v >= t.Count() && v != S && v != T).Select(v => v - t.Count());
        Console.WriteLine(ret.Count());
        foreach (var v in ret) Console.Write((v + 1) + " ");
        Console.WriteLine();
    }
}

Dinicは個人ライブラリのもの。