C#で競技プロするときの部品集

Competitive Programming (2) Advent Calendar 2018の12/25分の記事です。

C#は良い言語なのですが、競技プログラミングには少し（というか色々）足りないものがあります。ここでは、その不足分を埋める個人ライブラリを紹介します。

この記事にあるコードはすべて自由にご利用くださってかまいません。ただ、不具合等があったら報告をいただけると幸いです。

なお、ほとんどが蟻本を参考にして実装されています。

優先キュー

public class PriorityQueue<T> where T : IComparable
{
    private IComparer<T> _comparer = null;
    private int _type = 0;

    private T[] _heap;
    private int _sz = 0;

    private int _count = 0;

    /// <summary>
    /// Priority Queue with custom comparer
    /// </summary>
    public PriorityQueue(IComparer<T> comparer)
    {
        _heap = new T[128];
        _comparer = comparer;
    }

    /// <summary>
    /// Priority queue
    /// </summary>
    /// <param name="type">0: asc, 1:desc</param>
    public PriorityQueue(int type = 0)
    {
        _heap = new T[128];
        _type = type;
    }

    private int Compare(T x, T y)
    {
        if (_comparer != null) return _comparer.Compare(x, y);
        return _type == 0 ? x.CompareTo(y) : y.CompareTo(x);
    }

    public void Push(T x)
    {
        _count++;
        if (_count > _heap.Length)
        {
            var newheap = new T[_heap.Length * 2];
            for (int n = 0; n < _heap.Length; n++) newheap[n] = _heap[n];
            _heap = newheap;
        }

        //node number
        var i = _sz++;

        while (i > 0)
        {
            //parent node number
            var p = (i - 1) / 2;

            if (Compare(_heap[p], x) <= 0) break;

            _heap[i] = _heap[p];
            i = p;
        }

        _heap[i] = x;
    }

    public T Pop()
    {
        _count--;

        T ret = _heap[0];
        T x = _heap[--_sz];

        int i = 0;
        while (i * 2 + 1 < _sz)
        {
            //children
            int a = i * 2 + 1;
            int b = i * 2 + 2;

            if (b < _sz && Compare(_heap[b], _heap[a]) < 0) a = b;

            if (Compare(_heap[a], x) >= 0) break;

            _heap[i] = _heap[a];
            i = a;
        }

        _heap[i] = x;

        return ret;
    }

    public int Count()
    {
        return _count;
    }

    public T Peek()
    {
        return _heap[0];
    }

    public bool Contains(T x)
    {
        for (int i = 0; i < _sz; i++) if (x.Equals(_heap[i])) return true;
        return false;
    }

    public void Clear()
    {
        while (this.Count() > 0) this.Pop();
    }

    public IEnumerator<T> GetEnumerator()
    {
        var ret = new List<T>();

        while (this.Count() > 0)
        {
            ret.Add(this.Pop());
        }

        foreach (var r in ret)
        {
            this.Push(r);
            yield return r;
        }
    }

    public T[] ToArray()
    {
        T[] array = new T[_sz];
        int i = 0;

        foreach (var r in this)
        {
            array[i++] = r;
        }

        return array;
    }
}

まずは定番の優先キュー（ヒープ）です。C#を競プロで使うときの最大の不満がこれといっても過言ではありません。コンストラクタにIComparerを渡したり、最小/最大のどちらで動かすか設定できたりします。Push()、Pop()のほかに、Peek()、Count()、Contains()、Clear()、ToArray()といった便利メソッドも足してあります。

UnionFind

public class UnionFind
{
    private class Node
    {
        public Node Parent { get; set; }
        public int Rank { get; set; }
    }

    private Dictionary<object, Node> _dict = new Dictionary<object, Node>();

    private Node Root(object data)
    {
        if (!_dict.ContainsKey(data))
        {
            var node = new Node();
            _dict.Add(data, node);
            return node;
        }
        else
        {
            var node = _dict[data];
            return Find(node);
        }
    }

    private Node Find(Node node)
    {
        if (node.Parent == null) return node;
        return node.Parent = Find(node.Parent);
    }

    public void Unite(IComparable x, IComparable y)
    {
        var xRoot = Root(x);
        var yRoot = Root(y);
        if (xRoot == yRoot) return;

        if (xRoot.Rank < yRoot.Rank)
        {
            xRoot.Parent = yRoot;
        }
        else
        {
            yRoot.Parent = xRoot;
            if (xRoot.Rank == yRoot.Rank) yRoot.Rank++;
        }
    }

    public bool IsSameGroup(IComparable x, IComparable y)
    {
        return Root(x) == Root(y);
    }
}

つぎはこれも定番のUnionFind。多少速度は犠牲にしていますが、なるべく汎用的に使えるようにIComparableなら何でも受け付けるようにしてます。Unite()のほかに、IsSameGroup()も用意してます。

比較できるタプル（ペア）

public class ComparablePair<T, U> : IComparable where T : IComparable<T>
{
    public readonly T Item1;
    public readonly U Item2;

    public int CompareTo(object obj)
    {
        ComparablePair<T, U> castedObj = (ComparablePair<T, U>)obj;
        return this.Item1.CompareTo(castedObj.Item1);
    }

    public ComparablePair(T t, U u)
    {
        Item1 = t;
        Item2 = u;
    }
}

C#のTupleは比較できないので。まあたまに便利です。

平衡二分探索木

// <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 int Sum;       //sum of the value of the sub tree

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

    static Random _rnd = new Random();

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

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

    static Node Update(Node t)
    {
        t.Count = Count(t.LChild) + Count(t.RChild) + 1;
        //            t.Sum = Sum(t.LChild) + Sum(t.RChild) + t.Value;
        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())
        //            if ((double)Count(l) / (double)(Count(l) + Count(r)) > 0.5)   //debug
        {
            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);
    }

    // debug
    public static int GetDepth(Node t)
    {
        return t == null ? 0 : Math.Max(GetDepth(t.LChild), GetDepth(t.RChild)) + 1;
    }
}

Randomized BSTを使って自動バランスするようにがんばりました。平衡二分探索木です。Insert()のほかに、Remove()、RemoveAt()、Contains()、Find()、UpperBound()、LowerBound()などがあります。
これ単体だとあんまり便利ではないかもしれませんが、次のSetとMultiSetの実装に必要です。

C言語ぽいSetとMultiSet

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));
    }
}

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);
    }
}

平衡二分探索木を使ったSetとMultiSetです。LowerBound()とUpperBound()があるのが強み（というかそのために作った）。

Deque

public class Deque<T>
{
    T[] buf;
    int offset, count, capacity;
    public int Count { get { return count; } }
    public Deque(int cap) { buf = new T[capacity = cap]; }
    public Deque() { buf = new T[capacity = 16]; }

    // for debug
    public T[] Items
    {
        get
        {
            var a = new T[count];
            for (int i = 0; i < count; i++)
            {
                a[i] = this[i];
            }
            return a;
        }
    }

    public void Init()
    {
        count = 0;
    }

    public T this[int index]
    {
        get { return buf[getIndex(index)]; }
        set { buf[getIndex(index)] = value; }
    }
    private int getIndex(int index)
    {
        if (index >= capacity)
            throw new IndexOutOfRangeException("out of range");
        var ret = index + offset;
        if (ret >= capacity)
            ret -= capacity;
        return ret;
    }
    public void PushFront(T item)
    {
        if (count == capacity) Extend();
        if (--offset < 0) offset += buf.Length;
        buf[offset] = item;
        ++count;
    }
    public T PopFront()
    {
        if (count == 0)
            throw new InvalidOperationException("collection is empty");
        --count;
        var ret = buf[offset++];
        if (offset >= capacity) offset -= capacity;
        return ret;
    }
    public void PushBack(T item)
    {
        if (count == capacity) Extend();
        var id = count++ + offset;
        if (id >= capacity) id -= capacity;
        buf[id] = item;
    }
    public T PopBack()
    {
        if (count == 0)
            throw new InvalidOperationException("collection is empty");
        return buf[getIndex(--count)];
    }
    public void Insert(int index, T item)
    {
        if (index > count) throw new IndexOutOfRangeException();
        this.PushFront(item);
        for (int i = 0; i < index; i++)
            this[i] = this[i + 1];
        this[index] = item;
    }
    public T RemoveAt(int index)
    {
        if (index < 0 || index >= count) throw new IndexOutOfRangeException();
        var ret = this[index];
        for (int i = index; i > 0; i--)
            this[i] = this[i - 1];
        this.PopFront();
        return ret;
    }
    private void Extend()
    {
        T[] newBuffer = new T[capacity << 1];
        if (offset > capacity - count)
        {
            var len = buf.Length - offset;
            Array.Copy(buf, offset, newBuffer, 0, len);
            Array.Copy(buf, 0, newBuffer, len, count - len);
        }
        else Array.Copy(buf, offset, newBuffer, 0, count);
        buf = newBuffer;
        offset = 0;
        capacity <<= 1;
    }
}

ないと稀によく困るデックです。PushFront()、PushBack()、PopFront()、PosBack()、Insert()、RemoveAt()を用意してます。

GCD、ExtGCD

public static Int64 Gcd(Int64 a, Int64 b)
{
    if (a < b)
    {
        var tmp = a;
        a = b;
        b = tmp;
    }
    if (b == 0) return a;
    var p = a > b ? a : b;
    return Gcd(b, p % b);
}

public static Int64 ExtGcd(Int64 a, Int64 b, ref Int64 x, ref Int64 y)
{
    Int64 d = a;
    if (b != 0)
    {
        d = ExtGcd(b, a % b, ref y, ref x);
        y -= (a / b) * x;
    }
    else
    {
        x = 1;
        y = 0;
    }
    return d;
}

これは定番ですね。C#ではなくとも、みんな自前ライブラリで持ってると思われます。

組み合わせ系

// m種類から重複なくn個を選ぶ組み合わせ
public static Int64 GetMcn(int m, int n)
{
    Int64 val;
    if (m < n) return 0;
    n = Math.Min(n, m - n);
    if (n == 0) val = 1;
    else val = GetMcn(m - 1, n - 1) * m / n;
    return val;
}

// m種類から重複なくn個を選んで並べる組み合わせ
public static Int64 GetMpn(int m, int n)
{
    if (n > m) return 0L;
    Int64 ret = m;
    for (int i = 0; i < n - 1; i++)
    {
        ret *= (m - i - 1);
    }
    return ret;
}

// m種類から重複を許してn個を選ぶ組み合わせ（順番は無視）
public static Int64 GetMhn(int m, int n)
{
    return GetMcn(m + n - 1, n);
}

static Int64[] fact = new Int64[500005];
static Int64[] inv = new Int64[500005];

/// <summary>
/// FOR TEST - mCn % p (p should be prime number)
/// </summary>
public static Int64 GetMcn_p_Simple(Int64 m, Int64 n, Int64 p)
{
    // m! / ( n! ( m - n )! )
    return fact[m] * inv[m - n] % p * inv[n] % p;
}

/// <summary>
///  mCn % p (p should be prime number)
///  use Lucas's theorem
///   - need pre-calculation using the mod
/// </summary>
public static Int64 GetMcn_p(Int64 m, Int64 n, Int64 p)
{
    if (!(0 <= n && n <= m)) return 0;
    Int64 ret = 1;
    for (; n > 0; m /= p, n /= p)
    {
        Int64 n0 = m % p, k0 = n % p;
        if (n0 < k0) return 0;
        ret = ret * GetMcn_p_Simple(n0, k0, p);
        ret %= p;
    }
    return ret;
}

/// <summary>
///  mCn % p (p should be prime number)
///  use Lucas's theorem (No pre-calculation needed)
/// </summary>
public static Int64 GetMcn_p_NoPrecalc(int m, int n, int p)
{
    if (p < 2) return GetMcn(m, n);

    var dm1 = m / p;
    var dm2 = m % p;
    var dn1 = n / p;
    var dn2 = n % p;

    if ((dm2 < dn2) || (dm1 < dn1)) return 0;

    return GetMcn(dm1, dn1) * GetMcn(dm2, dn2) % p;
}

public static Int64 ModInv(Int64 a, Int64 m)
{
    Int64 x = 0, y = 0;
    ExtGcd(a, m, ref x, ref y);
    if (x < 0) x += m; //modInv will never be negative
    return x;
}

public static void Precal_FactAndInv(Int64 mod)
{
    fact[0] = 1;
    inv[0] = ModInv(1, mod);

    for (Int64 i = 1; i < 500005; i++)
    {
        fact[i] = (fact[i - 1] * i) % mod;
        inv[i] = ModInv(fact[i], mod);
    }
}

組み合わせ系のライブラリ。これらも、C#でなくともみんな自前で用意してます。いくつかの関数は、Precal_FactAndInv()を呼んでから使ってください。