2017-06-02

HackerRank Week of Code 32 参加日記

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

次の式が与えられる。
${ 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になっていた。

2017-04-08

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は個人ライブラリのもの。

2017-03-31

Maximum closure problem

アルゴリズムグラフ

Maximum closure problem の学習まとめ。以下のサイトを参考にした。

Closure problem - Wikipedia
http%3A%2F%2Friot.ieor.berkeley.edu%2F~dorit%2Fpub%2Fscribe%2Flec11%2FLec11posted.pdf&usg=AFQjCNEhubnfNuotTV0_wrbkGGdEF9UHMA&sig2=ewamZFzAoKgnMP5FaFV5cA&bvm=bv.151325232,d.amc *1

Maximum closure problemとは、ノードに重み(正負あり)の付いた有向グラフがあたえられたとき、重みの合計値が最大になるグラフのClosedなサブセットを求める問題である。
Closedのグラフとは、グラフの全ノードについて、その下流ノードがすべてそのグラフに属するもの。たとえば下の図だと、(a)はClosedだが(b)はClosedではない。
f:id:yambe2002:20170331101834p:plain
(*1より抜粋)

求め方
次のようなS-Tグラフを作成する。
・Sから正の重みがついたノードへ、その重み付きのエッジを追加
・Tから負の重みがついたノードへ、その重み付きのエッジを追加
・それ以外のエッジは、重み∞にする
そしてS-Tの最小カットを行い、S側の集合が求めるサブセットになる。

例えば次のような元グラフがあったとする。
f:id:yambe2002:20170331101642p:plain

これをS-Tグラフ化したものが以下になる。(点線が最小カット)
f:id:yambe2002:20170331101655p:plain
S側の集合{b, c, d, e, g}が最大のClosedセットであり、重みの合計値は6になっている。

有向グラフ ${G}$ について、 ${ (s \cup S, t \cup T) }$ が ${ G_{s, t} }$ の最小カットであれば、 ${S}$ は ${G}$ の重みの合計が最大になっているclosedセットである。( ${ G_{s, t} }$ は ${ G }$ から作成した ${s-t}$ グラフ)

証明
${ W^+ \equiv { j \in V | w_i > 0 }}$ 、 ${ W^- \equiv { j \in V | w_i \leq 0 }}$ とする。
f:id:yambe2002:20170331103755p:plain
(*1より抜粋)

${ W^{+}}$ は定数なので、 ${ C( s \cup S, t \cup T ) }$ を最小化するということは、 ${ \sum_{ i \in S } W_i }$ の最大化と同じことがわかる。

最小s-tカットの求め方は、以下のスライドが分かりやすかった。
https://www.slideshare.net/KuoE0/acmicpc-minimum-cut

また、Dinicという方法で最小カット（最大フロー）を求める方法はこちらが参考になる。
https://www.slideshare.net/KuoE0/acmicpc-dinics-algorithm

DinicのC#実装

public class Dinic
{
    public class Edge
    {
        public int V;
        public double C;
        public Edge N;
        public Edge B;
    }

    Edge[] _pool = new Edge[0];
    int _topIdx;

    Edge[] _adj = new Edge[0];

    public int MaxIdx;
    int _minV;

    public Dinic()
    {
        Expand(ref _pool, 128, true);
        Expand(ref _adj, 128, false);
        Init();
    }

    public void Init()
    {
        for (int i = 0; i < _adj.Length; i++) _adj[i] = null;
        _topIdx = 0;
        MaxIdx = 0;
        _minV = Int32.MaxValue;
    }

    void Expand(ref Edge[] edges, int size, bool fillWithEmptyEdge = false)
    {
        if (edges.Length <= size)
        {
            var newEdges = new Edge[Math.Max(size, edges.Length * 2)];
            for (int i = 0; i < edges.Length; i++) newEdges[i] = edges[i];
            if (fillWithEmptyEdge)
            {
                for (int i = edges.Length; i < newEdges.Length; i++)
                {
                    newEdges[i] = new Edge();
                }
            }
            edges = newEdges;
        }
    }

    public void AddEdge(int u, int v, double c, double bc = 0)
    {
        MaxIdx = Math.Max(MaxIdx, Math.Max(u + 1, v + 1));
        _minV = Math.Min(_minV, Math.Min(u, v));

        Expand(ref _pool, _topIdx + 1, true);
        Expand(ref _adj, MaxIdx);

        _pool[_topIdx].V = v;
        _pool[_topIdx].C = c;
        _pool[_topIdx].N = _adj[u];
        _adj[u] = _pool[_topIdx];
        _topIdx++;

        _pool[_topIdx].V = u;
        _pool[_topIdx].C = bc;
        _pool[_topIdx].N = _adj[v];
        _adj[v] = _pool[_topIdx];
        _topIdx++;

        _adj[u].B = _adj[v];
        _adj[v].B = _adj[u];

        if (u == v)
        {
            _adj[u].N.B = _adj[u];
            _adj[v].B = _adj[v].N;
        }
    }

    int[] _d;
    int[] _q;
    int _qh;
    int _qt;
    Edge[] _cur;

    public double GetMaxFlow(int s, int t)
    {
        MaxIdx = Math.Max(MaxIdx, Math.Max(s + 1, t + 1));
        _minV = Math.Min(_minV, Math.Min(s, t));

        _d = new int[MaxIdx];
        _q = new int[MaxIdx];
        _cur = new Edge[MaxIdx];

        double f = 0;

        while (ReLabel(s, t))
        {
            for (int i = 0; i < MaxIdx; i++) _cur[i] = _adj[i];
            f += Augument(s, t, s, double.MaxValue);
        }

        return f;
    }

    bool ReLabel(int s, int t)
    {
        for (int i = 0; i < MaxIdx; i++) _d[i] = Int32.MaxValue;
        _d[_q[_qh = _qt = 0] = t] = 0;
        while (_qh <= _qt)
        {
            var u = _q[_qh++];

            for (var i = _adj[u]; i != null; i = i.N)
            {
                if (i.B.C != 0 && _d[i.V] > _d[u] + 1)
                {
                    _d[i.V] = _d[u] + 1;
                    if ((_q[++_qt] = i.V) == s)
                    {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    double Augument(int s, int t, int u, double e)
    {
        if (u == t) return e;
        double f = 0;

        for (var i = _cur[u]; i != null; i = i.N)
        {
            if (i.C > 0 && _d[u] == _d[i.V] + 1)
            {
                var df = Augument(s, t, i.V, Math.Min(e, i.C));
                if (df > 0)
                {
                    i.C -= df;
                    i.B.C += df;
                    e -= df;
                    f += df;
                }
            }
            if (!(e > 0)) break;
        }

        return f;
    }

    // (S, T)
    public Tuple<List<int>, List<int>> GetStCut(int s)
    {
        var used_flg = new bool[MaxIdx];

        Dfs(s, used_flg);

        var ret_s = new List<int>();
        var ret_t = new List<int>();
        for (int i = _minV; i < MaxIdx; i++)
        {
            if (!used_flg[i])
            {
                ret_t.Add(i);
            }
            else
            {
                ret_s.Add(i);
            }
        }

        return new Tuple<List<int>, List<int>>(ret_s, ret_t);
    }

    void Dfs(int u, bool[] used_flg)
    {
        if (used_flg[u]) return;
        used_flg[u] = true;

        for (var i = _adj[u]; i != null; i = i.N)
        {
            if (i.C > 1e-6) Dfs(i.V, used_flg);
        }
    }
}

2017-03-07

CodinGame - Ghost in the Cell 参加日記

プログラミングコンテストゲームAI

CodinGameのコンテストに初参加してみた。ゲームAIを作ってその強さを競うものなのだが、面倒な環境構築が不要でなかなか楽しかった。対戦動画も観ていて面白い。

https://www.codingame.com/replay/194505045
黄色が私。最終的にCyborgの数が多いほうが勝ち

ランキングはリーグ制。最初はウッドリーグ3部からスタートし、リーグボスを倒すごとにウッド2→ウッド1→ブロンズ→シルバー→ゴールドとランクアップする。また、途中でルールが追加されることもある。

ゲームルール概略

ターン制
マップ上にいくつかの工場がある
工場間は長さの違う道で繋がれている
工場は味方・敵・中立のいずれか
工場は1ターンごと0~3体のCyborgを自動生産する
1ターンごと、味方・敵同時に行動を起こす
自工場からほかの工場にCyborg部隊を送ることができる
敵または中立の工場にCyborg部隊が到着したら戦いが起こる
戦いはCyborg数の多いほう勝利し、数の差分だけ生き残る
戦いに勝ったら工場を占領できる
最終的に相手を全滅させるか、400ターン後にcyborgの多いほうが勝ち
1ターンに複数の部隊を送ることができる*
Cyborgを10消費して、工場のCyborg生産数を増やすことができる（3まで）*
2回まで爆弾を送ることができる*
爆弾を被弾すると、工場のCyborg数が半分、または10まで減る（小さいほう）*

(*はリーグが上がるごとに追加されたルール)

実装
1ターンの制限時間が50msしかないので、深く手を読む方針はとらなかった。基本的に、(1)危ない自工場があったら助ける(2)生産力のある中立工場があったら占領しようとする(3)敵に爆弾を送ってみる(4)敵工場を占領しようとする(4)遊んでる工場があったら前線に兵を送る、の優先順位で手の候補をいくつか作成し、そこから21手くらい先までシミュレートして局面評価がベストのものを採用した。

反省
序盤にいろいろ考えすぎて実装が遅れたのが良くなかった。Topcoderのマラソンマッチと違い途中でルールが変わるし、またリーグが落ちることは（たぶん）ない仕組みなので、軽いコードをどんどん書いてSubmitしていったほうがよさそうだ。シミュレーション中の手や評価関数がまったく詰められなかったのも反省点。

結果はぎりぎりシルバーリーグの103位/311人だった。次回はシルバー上位を目標にしよう。

2017-02-16

HackerRank Ad Infinitum16 参加日記

プログラミングコンテスト数学

始めて参加した。数学関連の問題がでるコンテストらしい。
46位/673人だけど初回参加者用の区分だっただからレベルが低いのかも。

ad Infinitum: 無限に、永久に（ラテン語）

Leonardo's Prime Factors

q個の整数が与えられる。それぞれの整数（nとする）について、集合[1,n]内で、一意な素因数の数が最も多いものを算出し、その数を出力せよ。
1 <= q <= 10^5
1 <= n <= 10^18

素数を小さい順に、nを超えるまでかけていけばよい。素数は50くらいまでしか使わないので、最初に列挙しておくと効率が良い。

var q = Int32.Parse(Console.ReadLine());
while (q > 0)
{
    var n = Int64.Parse(Console.ReadLine());
    var ret = 0;
    BigInteger x = 1;

    foreach (var p in primes) //primesは素数のリスト（昇順）
    {
        x *= p;
        if (x > n) break;
        ret++;
    }
    Console.WriteLine(ret);
    q--;
}

Russian Peasant Exponentiation

q個のクエリが与えられる。それぞれのクエリでは、整数k,m,a,bが与えられる。(a+bi)^kを求めよ（iは虚数単位）。解は、実部と虚部をそれぞれmでModしたものを出力せよ。
大きなべき乗を求める方法は次を参考にせよ
https://www.hackerrank.com/external_redirect?to=http://lafstern.org/matt/col3.pdf
1 <= q <= 10^5
0 <= k <= 10^18
2 <= m <= 10^9
0 <= a, b <= m

「ロシア農民のアルゴリズム」を複素数に応用しろというもの。複素数クラスを作成し、乗算とModを実装すれば、実数と同じコードになる。複素数クラスはNumericsのものだとオーバーフローの危険性がありそうだ。

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

    var q = Int32.Parse(Console.ReadLine());
    while (q > 0)
    {
        //a,b,k,m -> (a + bi)^k mod m
        var str = Console.ReadLine().Split();
        var a = Int64.Parse(str[0]);
        var b = Int64.Parse(str[1]);
        var k = Int64.Parse(str[2]);
        var m = Int64.Parse(str[3]);

        var comp = new MyComplex(a, b);
        var modPow = ModPow(comp, k, m);

        //mod前のmの足し忘れ注意！
        Console.WriteLine(string.Format("{0} {1}", (modPow.Real + m) % m, (modPow.Imaginary + m) % m));
        q--;
    }
    Console.Out.Flush();
}

//ロシア農民のアルゴリズム
static MyComplex ModPow(MyComplex x, Int64 n, Int64 mod)
{
    while ((n & 1) == 0)
    {
        x = (x * x) % mod;
        n >>= 1;
    }
    var ret = x;
    n >>= 1;
    while (n > 0)
    {
        x = (x * x) % mod;
        if ((n & 1) != 0)
            ret = (ret * x) % mod;
        n >>= 1;
    }

    return ret % mod;
}

class MyComplex
{
    public Int64 Real;
    public Int64 Imaginary;

    public MyComplex(Int64 real, Int64 img)
    {
        Real = real;
        Imaginary = img;
    }

    public static MyComplex operator *(MyComplex c1, MyComplex c2)
    {
        return new MyComplex(c1.Real * c2.Real - c1.Imaginary * c2.Imaginary, c1.Real * c2.Imaginary + c1.Imaginary * c2.Real);
    }

    public static MyComplex operator %(MyComplex c1, Int64 mod)
    {
        return new MyComplex((c1.Real) % mod, (c1.Imaginary) % mod);
    }
}

Xrange's Pancakes

正n角形のパンケーキが与えられる。このパンケーキは、①中心と各頂点を通るもの②中心と各頂点の中間点を通るもの、の2種類の軸が存在する（合計n本）。軸は0~n-1の番号が時計回りに連続でついている。
このとき、n個のクエリが与えられる。クエリの種類は２つ：
タイプ１：軸kで裏返す
タイプ２：パンケーキを、(360*k) / n 度だけ時計回りに回転させる
すべてのクエリが終了したときのパンケーキを、タイプ１またはタイプ２を1回だけ適用させて、初期位置に戻したい。このクエリを答えよ。
3 <= n <= 10^6
1 <= m <= 10^6
0 <= k <= n

ややこしく考えると嵌りそうだが、実際は初期に軸0にあった頂点の位置と、裏返されているか否かだけ管理すればよい。

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

var x = 2 * n; //位置（頂点＋頂点間）
var pos = 0;   //初期に軸0にあった頂点の位置
var isFlipped = false;

while (m > 0)
{
    str = Console.ReadLine().Split();
    var k = Int32.Parse(str[1]);
    switch (str[0])
    {
        case "1":   //rotate
            pos = (pos + k * 2) % x;
            break;
        default:    //flip
            pos = (pos + ((k + x - pos) % x) * 2) % x;
            isFlipped = !isFlipped;
            break;
    }
    m--;
}

if (!isFlipped)
{
    Console.WriteLine("1 " + ((x - pos) / 2).ToString());
}
else
{
    Console.WriteLine("2 " + (pos / 2).ToString());
}

Solve Equations

方程式 ${ ax + by = c }$ がｑ個与えられたとき、それぞれ次を満たす最も原点に近い点を求めよ。
・xとyは整数
・xは0より大きい
複数の解があるときは、xのより小さいものを答えよ。
1 <= q <= 10^5
1 <= a <= 10^8
1 <= b <= 10^8
1 <= c <= 10^8
a, b, cは整数

整数解が存在するといことは、cはgcd(a,b)で割り切れる。そして、拡張ユークリッドアルゴリズムを使って一組の(x, y)が計算できたとき、すべての組は次の形で表せる。ベズーの等式 - Wikipedia
${ \left(x+k{\frac {b}{\gcd(a,b)}},\ y-k{\frac {a}{\gcd(a,b)}}\right) }$
ここで、 ${ c_1 = \frac {b}{\gcd(a, b)} }$ 、 ${ c_2 = - \frac {a}{\gcd(a, b)} }$ とすると
${ x_2 = x_1 + c_1 \cdot k }$
${ y_2 = y_1 + c_2 \cdot k }$
と表すことができる。
${ (x_2)^2 + (y_2)^2 }$ を最小化するのが目的なので、上式の展開
${ (x_1 + c_1\cdot k)^2 + (y_1 + c_2 \cdot k)^2 = t^2 \cdot ((c_1)^2 + (c_2)^2) + t \cdot (2 \cdot x_1 \cdot c_1 + 2 \cdot y_1 \cdot c_2) + ( (x_1)^2 + (y_1)^2 ) }$
を最小化すればよい。
${ \alpha = (c_1)^2 + (c_2)^2 }$
${ \beta = 2 \cdot x_1 \cdot c_1 + 2 \cdot y_1 \cdot c_2 }$
${ \gamma = (x_1)^2 + (y_1)^2 }$
とおくと、
${ \alpha \cdot t^2 + \beta \cdot t + \gamma }$
になる。よって答えは以下のようになる。（実装は省略）
１. ${ - \frac{\beta}{ 2 \cdot \alpha } }$ が負のとき
${ t=0 }$ の場合
２. ${ - \frac{\beta}{ 2 \cdot \alpha } }$ が正のとき
${ t= -\frac{\beta}{ 2 \cdot \alpha } }$ または ${ t= -\frac{\beta}{ 2 \cdot \alpha } + 1 }$ の場合

Hyperspace Travel

m次元の超空間にn人が存在している。この人達は、次元のグリッド線上だけを動くことができる。全員の総移動距離が最小になるよう、空間のある地点に集まりたい。この地点を求めよ。
各人の初期位置は、次元0、次元1...の順にx0,x1...の形で与えられる。
1 <= n <= 10^4
1 <= m <= 10^2

10^9 <= xi <= 10^9　（整数のみ）

集合地点の位置は整数

グリッド線上のみ動くことができる（次元間をナナメに移動することはできない）ということは、各次元内で移動が完結しているということになる。よって、次元ごとに集合地点を求めればよい。
ある次元について、移動距離が最小になるのは、真ん中にいる人に集まる場合なので、ソートしてIndexが中点のものが答えになる。

static void Main(string[] args)
{
    var str = Console.ReadLine().Split();
    var n = Int64.Parse(str[0]);
    var m = Int64.Parse(str[1]);

    var friends = new List<List<Int64>>();
    for (int i = 0; i < n; i++)
    {
        friends.Add(Console.ReadLine().Split().Select(v => Int64.Parse(v)).ToList());
    }

    for (int i = 0; i < m; i++)
    {
        Console.Write(Get(i, friends));
        if (i != m - 1) Console.Write(" ");
    }
    Console.WriteLine();
}

static Int64 Get(int dimension, List<List<Int64>> friends)
{
    var values = new List<Int64>();
    foreach (var friend in friends)
    {
        values.Add(friend[dimension]);
    }
    values.Sort();

    return values[(values.Count() - 1) / 2];
}

2017-02-10

イントロソートを安定ソートとして習作(C#)

C#で安定ソートを行うときはLinqのOrderBy()が一般的だが、OrderByはクイックソートなのでワースト計算量がO(N^2)になってしまう。ここでは、これを回避したソートを習作してみる。

ちなみにC++のstable_sort()だと、安定マージソートをつかってこの問題を回避している。配列を再帰的に分割していき、長さが閾値(15)未満になったら挿入ソートに切り替えるようだ。
https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.4/a01347.html#l03409

これをそのまま移植してもOKなのだが、それでは面白くないので、ここではArray.Sort()のイントロソートを強引に安定化することにする。イントロソートは最初はクイックソートを行い、再帰のレベルがある値を超えたらヒープソートに切り替えるといもので、高速なクイックソートの利点を利用しつつ最悪ケースを回避するアルゴリズムだ。基本的にはこの２つのソートを安定版に作り替えればよい。

以下のMS実装を参考にした。

イントロソート（Array.Sort())
https://referencesource.microsoft.com/#mscorlib/system/array.cs,2a2126edd9ca7eb4
クイックソート（Linq）
https://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,1395017e067e5a34

static public void StableSort<T>(List<T> list) where T : IComparable
{
    int[] map = new int[list.Count()];
    for (int i = 0; i < list.Count(); i++) map[i] = i;
    StableSort(list, map, 0, list.Count() - 1, (int)Math.Floor(Math.Log(list.Count(), 2)) * 2);

    var tmp = list.ToArray();
    for (int i = 0; i < list.Count(); i++)
    {
        list[i] = tmp[map[i]];
    }
}

static void StableSort<T>(List<T> list, int[] map, int left, int right, int depthLimit) where T : IComparable
{
    if (left >= right) return;

    //stable heap sort
    if (depthLimit == 0)
    {
        StableSort_HeapSort(list, map, left, right);
        return;
    }

    //stable quick sort
    do
    {
        int i = left;
        int j = right;
        int x = map[i + ((j - i) >> 1)];
        do
        {
            while (i < list.Count() && CompareKeys(list, x, map[i]) > 0) i++;
            while (j >= 0 && CompareKeys(list, x, map[j]) < 0) j--;
            if (i > j) break;
            if (i < j)
            {
                int temp = map[i];
                map[i] = map[j];
                map[j] = temp;
            }
            i++;
            j--;
        } while (i <= j);
        if (j - left <= right - i)
        {
            if (left < j) StableSort(list, map, left, j, depthLimit - 1);
            left = i;
        }
        else
        {
            if (i < right) StableSort(list, map, i, right, depthLimit - 1);
            right = j;
        }
    } while (left < right);
}

static void StableSort_HeapSort<T>(List<T> list, int[] map, int lo, int hi) where T : IComparable
{
    int n = hi - lo + 1;
    for (int i = n / 2; i >= 1; i = i - 1)
    {
        StableSort_HeapSort_DownHeap(list, map, i, n, lo);
    }
    for (int i = n; i > 1; i = i - 1)
    {
        Swap(map, lo, lo + i - 1);
        StableSort_HeapSort_DownHeap(list, map, 1, i - 1, lo);
    }
}

static void StableSort_HeapSort_DownHeap<T>(List<T> list, int[] map, int i, int n, int lo) where T : IComparable
{
    int d = map[lo + i - 1];
    int child;
    while (i <= n / 2)
    {
        child = 2 * i;
        if (child < n && CompareKeys(list, map[lo + child - 1], map[lo + child]) < 0)
        {
            child++;
        }
        if (!(CompareKeys(list, d, map[lo + child - 1]) < 0))
            break;
        map[lo + i - 1] = map[lo + child - 1];
        i = child;
    }
    map[lo + i - 1] = d;
}

static void Swap(int[] map, int i, int j)
{
    var tmp = map[i];
    map[i] = map[j];
    map[j] = tmp;
}

static int CompareKeys<T>(List<T> list, int index1, int index2) where T : IComparable
{
    var c = list[index1].CompareTo(list[index2]);
    if (c == 0)
    {
        return index1 - index2;
    }
    return c;
}

当然、ほとんどの場合でOrderByのほうが少し速い。ワーストケースではこちらのほうが大幅に良いパフォーマンスが出るはず・・・だがうまくテストケースを作れなかった。

2017-02-07

平衡二分探索木を使ったsetとmultisetの実装（C#）

C# アルゴリズム

C++のsetとmultisetに相当するコレクションをC#で実装してみる。

set
順序付けされたデータを重複を排除して保持するもの。C#のSortedSetとほぼ同じだが、lower_bound()とupper_bound()が使える。データの追加・削除・検索いずれもO(logN)。

multiset
順序付けされたデータを重複を許容しながら保持するもの。C#に類似のものはない。setと同じく、lower_bound()とupper_bound()がある。データの追加・削除・検索いずれもO(logN)。

lower_bound()は該当値以上になる最小Indexを、upper_bound()は該当値より大きくなる最小Indexを返す関数で、いずれもO(logN)になる。

どちらも平衡二分探索木で実現できる。平衡二分探索木は二分探索木を、木構造がなるべく偏らないように工夫したものである（偏ると効率が悪くなる＝O(N)に近くなる）。ここではRandomized Binary Search Tree(RBST)と呼ばれる、値を追加するときに、なるべく木の高さの偏りがなくなるよう、追加候補の位置に重みづけをしてランダム選択する方法で実装してみる。

詳細はこちらが参考になった
プログラミングコンテストでのデータ構造 2 ～平衡二分探索木編～

/// <summary>
/// Self-Balancing Binary Search Tree
/// (using Randamized BST)
/// </summary>
public class SB_BinarySearchTree<T> where T : IComparable
{
    public class Node
    {
        public T Value;
        public Node LChild;
        public Node RChild;
        public int Count;     //size of the sub tree

        public Node(T v)
        {
            Value = v;
            Count = 1;
        }
    }

    static Random _rnd = new Random();

    public static int Count(Node t)
    {
        return t == null ? 0 : t.Count;
    }

    static Node Update(Node t)
    {
        t.Count = Count(t.LChild) + Count(t.RChild) + 1;
        return t;
    }

    public static Node Merge(Node l, Node r)
    {
        if (l == null || r == null) return l == null ? r : l;

        if ((double)Count(l) / (double)(Count(l) + Count(r)) > _rnd.NextDouble())
        {
            l.RChild = Merge(l.RChild, r);
            return Update(l);
        }
        else
        {
            r.LChild = Merge(l, r.LChild);
            return Update(r);
        }
    }

    /// <summary>
    /// split as [0, k), [k, n)
    /// </summary>
    public static Tuple<Node, Node> Split(Node t, int k)
    {
        if (t == null) return new Tuple<Node, Node>(null, null);
        if (k <= Count(t.LChild))
        {
            var s = Split(t.LChild, k);
            t.LChild = s.Item2;
            return new Tuple<Node, Node>(s.Item1, Update(t));
        }
        else
        {
            var s = Split(t.RChild, k - Count(t.LChild) - 1);
            t.RChild = s.Item1;
            return new Tuple<Node, Node>(Update(t), s.Item2);
        }
    }

    public static Node Remove(Node t, T v)
    {
        if (Find(t, v) == null) return t;
        return RemoveAt(t, LowerBound(t, v));
    }

    public static Node RemoveAt(Node t, int k)
    {
        var s = Split(t, k);
        var s2 = Split(s.Item2, 1);
        return Merge(s.Item1, s2.Item2);
    }

    public static bool Contains(Node t, T v)
    {
        return Find(t, v) != null;
    }

    public static Node Find(Node t, T v)
    {
        while (t != null)
        {
            var cmp = t.Value.CompareTo(v);
            if (cmp > 0) t = t.LChild;
            else if (cmp < 0) t = t.RChild;
            else break;
        }
        return t;
    }

    public static Node FindByIndex(Node t, int idx)
    {
        if (t == null) return null;

        var currentIdx = Count(t) - Count(t.RChild) - 1;
        while (t != null)
        {
            if (currentIdx == idx) return t;
            if (currentIdx > idx)
            {
                t = t.LChild;
                currentIdx -= (Count(t == null ? null : t.RChild) + 1);
            }
            else
            {
                t = t.RChild;
                currentIdx += (Count(t == null ? null : t.LChild) + 1);
            }
        }

        return null;
    }

    public static int UpperBound(Node t, T v)
    {
        var torg = t;
        if (t == null) return -1;

        var ret = Int32.MaxValue;
        var idx = Count(t) - Count(t.RChild) - 1;
        while (t != null)
        {
            var cmp = t.Value.CompareTo(v);
                
            if (cmp > 0)
            {
                ret = Math.Min(ret, idx);
                t = t.LChild;
                idx -= (Count(t == null ? null : t.RChild) + 1);
            }
            else if (cmp <= 0)
            {
                t = t.RChild;
                idx += (Count(t == null ? null : t.LChild) + 1);
            }
        }
        return ret == Int32.MaxValue ? Count(torg) : ret;
    }

    public static int LowerBound(Node t, T v)
    {
        var torg = t;
        if (t == null) return -1;

        var idx = Count(t) - Count(t.RChild) - 1;
        var ret = Int32.MaxValue;
        while (t != null)
        {
            var cmp = t.Value.CompareTo(v);
            if (cmp >= 0)
            {
                if (cmp == 0) ret = Math.Min(ret, idx);
                t = t.LChild;
                if (t == null) ret = Math.Min(ret, idx);
                idx -= t == null ? 0 : (Count(t.RChild) + 1);
            }
            else if (cmp < 0)
            {
                t = t.RChild;
                idx += (Count(t == null ? null : t.LChild) + 1);
                if (t == null) return idx;
            }
        }
        return ret == Int32.MaxValue ? Count(torg) : ret;
    }

    public static Node Insert(Node t, T v)
    {
        var ub = LowerBound(t, v);
        return InsertByIdx(t, ub, v);
    }

    static Node InsertByIdx(Node t, int k, T v)
    {
        var s = Split(t, k);
        return Merge(Merge(s.Item1, new Node(v)), s.Item2);
    }

    public static IEnumerable<T> Enumerate(Node t)
    {
        var ret = new List<T>();
        Enumerate(t, ret);
        return ret;
    }

    static void Enumerate(Node t, List<T> ret)
    {
        if (t == null) return;
        Enumerate(t.LChild, ret);
        ret.Add(t.Value);
        Enumerate(t.RChild, ret);
    }
}

平衡二分探索木ができてしまえば、setは簡単に作ることができる。

/// <summary>
/// C-like set
/// </summary>
public class Set<T> where T : IComparable
{
    protected SB_BinarySearchTree<T>.Node _root;

    public T this[int idx]{ get { return ElementAt(idx); } }

    public int Count()
    {
        return SB_BinarySearchTree<T>.Count(_root);
    }

    public virtual void Insert(T v)
    {
        if (_root == null) _root = new SB_BinarySearchTree<T>.Node(v);
        else
        {
            if (SB_BinarySearchTree<T>.Find(_root, v) != null) return;
            _root = SB_BinarySearchTree<T>.Insert(_root, v);
        }
    }

    public void Clear()
    {
        _root = null;
    }

    public void Remove(T v)
    {
        _root = SB_BinarySearchTree<T>.Remove(_root, v);
    }

    public bool Contains(T v)
    {
        return SB_BinarySearchTree<T>.Contains(_root, v);
    }

    public T ElementAt(int k)
    {
        var node = SB_BinarySearchTree<T>.FindByIndex(_root, k);
        if (node == null) throw new IndexOutOfRangeException();
        return node.Value;
    }

    public int Count(T v)
    {
        return SB_BinarySearchTree<T>.UpperBound(_root, v) - SB_BinarySearchTree<T>.LowerBound(_root, v);
    }

    public int LowerBound(T v)
    {
        return SB_BinarySearchTree<T>.LowerBound(_root, v);
    }

    public int UpperBound(T v)
    {
        return SB_BinarySearchTree<T>.UpperBound(_root, v);
    }

    public Tuple<int, int> EqualRange(T v)
    {
        if (!Contains(v)) return new Tuple<int, int>(-1, -1);
        return new Tuple<int, int>(SB_BinarySearchTree<T>.LowerBound(_root, v), SB_BinarySearchTree<T>.UpperBound(_root, v) - 1);
    }

    public List<T> ToList()
    {
        return new List<T>(SB_BinarySearchTree<T>.Enumerate(_root));
    }
}

setのInsert()で重複を許容すればmultisetになる。

/// <summary>
/// C-like multiset
/// </summary>
public class MultiSet<T> : Set<T> where T : IComparable
{
    public override void Insert(T v)
    {
        if (_root == null) _root = new SB_BinarySearchTree<T>.Node(v);
        else _root = SB_BinarySearchTree<T>.Insert(_root, v);
    }
}