C# で競技プログラミングを戦う

2020年1月14日

Code Jam、TopCoder、AtCoder といったプログラミングコンテストの世界では、主要なプログラミング言語から好きなものを選んで戦うことができますが、ほとんどの参加者が選ぶのは C++ か Java のどちらかで、この二つが全体の90%ほどを占めています。C# を使っている人を見かけることはほとんどなく、参加者の割合でいうと5%にも満たないほどです。

C# は戦えない言語なのでしょうか? 今までコンテストで C# を使い続けてきた私の経験から言うと、そんなことはありません。

遅さは否めない

コンテストで C++ や Java が好まれる最大の理由は、その速度です。その点 C# がどうかというと、やはり少し遅いことは認めざるを得ません。C++ のおよそ10倍遅いというのが目安です。

10倍という数字にはインパクトがあるかもしれませんが、コンテストでこれが致命的になることは滅多にありません。実行時間の制限が2秒だとして、C# の場合、ビッグオー記法の中身が1000万を超えると要注意ですが、通常1000万越えの計算量が要求されることはまずないからです。主催者側も、言語による有利不利はできるだけ設けたくないと考えているのです。

手元に置いておきたい自前ライブラリ6選

C++ に比べると、C# はライブラリの充実度でやや不利に感じることがあります。ですが、レッドコーダーを目指すのでもない限り、次の6つのアルゴリズムを自前で携えておくだけで十分戦えます。

  1. 最大公約数
  2. 剰余演算
  3. Union-Find 木
  4. 順列
  5. 優先度付きキュー
  6. 平衡二分木

ここからは、これらアルゴリズムの C# の実装例を示していきます。

1. 最大公約数

コンテストでは演算の過程で最大公約数を求めなければならない場面がよくあります。ユークリッドの互除法という簡単なアルゴリズムで求まりますが、本番でこれを間違えずにサッと書き切るのは意外と難しいものです。短いコードなので、手元に置いていつでも取り出せるようにしておくと少しだけ有利になります。コード例を示しておきます。

static long Gcd(long a, long b)
{
    var v = new[] { a, b };
    while (v[1] != 0) { v = new[] { v[1], v[0] % v[1] }; }
    return v[0];
}

static long Lcm(long a, long b)
{
    return a / Gcd(a, b) * b;
}

最大公約数 Gcd を応用して最小公倍数 Lcm も求められますが、実装時の演算順序にはご注意ください。除算を先に持ってこないと、必要のないオーバーフローの原因となります。

2. 剰余演算

コンテストでよくある言い回しに、「答えを 1,000,000,007 で割った余りを出力せよ」というものがあります。剰余演算の法則を知らないと対応できない「初見殺し」です。

入門者は次第に、こういった問題では単に演算の過程で余りを取り続ければよいということを学びます。しかし、これが通用するのは加算・減算・乗算までです。

Mが素数のとき、フェルマーの小定理から次の式が導かれます(ちなみに 1,000,000,007 は素数です)。除算の場合にはこれを用いなければなりません。

$$a \div b \equiv a \times b^{M-2} \pmod M$$

そして、累乗の計算には繰り返し二乗法と呼ばれる高速化のアルゴリズムが必須です。これらを真面目に組んでいると、それだけでコンテストの時間が終わってしまいます。手元に持っておきましょう。コード例です。

class Modular
{
    private const int M = 1000000007;
    private long value;
    public Modular(long value) { this.value = value; }
    public static implicit operator Modular(long a)
    {
        var m = a % M;
        return new Modular((m < 0) ? m + M : m);
    }
    public static Modular operator +(Modular a, Modular b)
    {
        return a.value + b.value;
    }
    public static Modular operator -(Modular a, Modular b)
    {
        return a.value - b.value;
    }
    public static Modular operator *(Modular a, Modular b)
    {
        return a.value * b.value;
    }
    private static Modular Pow(Modular a, int n)
    {
        switch (n)
        {
        case 0:
            return 1;
        case 1:
            return a;
        default:
            var p = Pow(a, n / 2);
            return p * p * Pow(a, n % 2);
        }
    }
    public static Modular operator /(Modular a, Modular b)
    {
        return a * Pow(b, M - 2);
    }
    private static readonly List<int> facs = new List<int> { 1 };
    private static Modular Fac(int n)
    {
        for (int i = facs.Count; i <= n; ++i)
        {
            facs.Add((int)(Math.BigMul(facs.Last(), i) % M));
        }
        return facs[n];
    }
    public static Modular Ncr(int n, int r)
    {
        return (n < r)  ? 0
             : (n == r) ? 1
                        : Fac(n) / (Fac(r) * Fac(n - r));
    }
    public static explicit operator int(Modular a)
    {
        return (int)a.value;
    }
}

Mを法とする除算、累乗、階乗、nCr にまで対応しています。私はこのコードに何度も助けられました。

3. Union-Find 木

AさんとBさんは友達です。CさんとEさんは友達です。このような情報がすべて与えられます。「友達の友達は友達」だと考えると、友達グループはいくつ存在するでしょうか?

これは Union-Find 木を必要とする典型的な問題です。なんとなく二重ループをぐるぐる回せば解けそうにも思えますが、これは特殊なアルゴリズムでないと解けないのです。このような問題は、Union-Find を知っていることはもちろんですが、コードを持っているか持っていないかが決定的な差を分けます。コード例を示します。

class Node<T>
{
    private int m_height;
    private Node<T> m_parent;
    public T Item { get; private set; }
    public Node(T item)
    {
        m_height = 0;
        m_parent = this;
        Item = item;
    }
    public Node<T> Find()
    {
        if (m_parent == this) { return this; }

        Node<T> parent = m_parent.Find();
        m_parent = parent;
        return parent;
    }
    public static void Unite(Node<T> a, Node<T> b)
    {
        Node<T> p = a.Find();
        Node<T> q = b.Find();
        if (p.m_height < q.m_height)
        {
            p.m_parent = q;
            q.m_height = Math.Max(p.m_height + 1, q.m_height);
        }
        else
        {
            q.m_parent = p;
            p.m_height = Math.Max(q.m_height + 1, p.m_height);
        }
    }
}

4. 順列

たとえば 1, 2, 3 という数列があったとき、これを並べる順序のすべてのパターンを列挙することを考えます。この場合であれば、

  • 1, 2, 3
  • 1, 3, 2
  • 2, 1, 3
  • 2, 3, 1
  • 3, 1, 2
  • 3, 2, 1

の6パターンですね。C++ にはこれをサポートする std::next_permutation という関数がありますが(なぜ?)、C# にはありません。

これを必要とする問題に出くわすことはそうそうありませんが、備えなく遭遇してしまうと手も足も出ません。コード例を示します。

static class Permutation<T>
{
    private static void Search(List<T[]> perms, Stack<T> stack, T[] a)
    {
        int N = a.Length;
        if (N == 0)
        {
            perms.Add(stack.Reverse().ToArray());
        }
        else
        {
            var b = new T[N - 1];
            Array.Copy(a, 1, b, 0, N - 1);
            for (int i = 0; i < a.Length; ++i)
            {
                stack.Push(a[i]);
                Search(perms, stack, b);
                if (i < b.Length) { b[i] = a[i]; }
                stack.Pop();
            }
        }
    }
    public static IEnumerable<T[]> All(IEnumerable<T> src)
    {
        var perms = new List<T[]>();
        Search(perms, new Stack<T>(), src.ToArray());
        return perms;
    }
}

5. 優先度付きキュー

優先度付きキューとは、簡単に言うと「常に中身がソートされているキュー」です。値を突っ込むときは O(log n)、取り出すときは O(1) の計算量であることが期待されます。

C# の .Net ライブラリには SortedSet やら SortedList といったそれっぽい名前のコンテナがあるものの、この計算量を実現するものがありそうでないのです。歯痒い。自前で用意するならば、次のようになります。

class PriorityQueue<T>
{
    private readonly List<T> m_list;
    private readonly Func<T, T, int> m_compare;
    private int m_count;
    public PriorityQueue(int capacity, Func<T, T, int> compare)
    {
        m_list = new List<T>(capacity);
        m_compare = compare;
        m_count = 0;
    }
    private int Add(T value)
    {
        if (m_count == m_list.Count)
        {
            m_list.Add(value);
        }
        else
        {
            m_list[m_count] = value;
        }
        return m_count++;
    }
    private void Swap(int a, int b)
    {
        T tmp = m_list[a];
        m_list[a] = m_list[b];
        m_list[b] = tmp;
    }
    public void Enqueue(T value)
    {
        int c = Add(value);
        while (c > 0)
        {
            int p = (c - 1) / 2;
            if (m_compare(m_list[c], m_list[p]) < 0) { Swap(p, c); } else { break; }
            c = p;
        }
    }
    public T Dequeue()
    {
        T value = m_list[0];
        m_list[0] = m_list[--m_count];
        int p = 0;
        while (true)
        {
            int c1 = p * 2 + 1;
            int c2 = p * 2 + 2;
            if (c1 >= m_count) { break; }
            int c = (c2 >= m_count || m_compare(m_list[c1], m_list[c2]) < 0) ? c1 : c2;
            if (m_compare(m_list[c], m_list[p]) < 0) { Swap(p, c); } else { break; }
            p = c;
        }
        return value;
    }
}

Enqueue と Dequeue にだけ注目すれば使えます。オブジェクト生成時に、コンストラクタで比較関数を一度与えてください。

6. 平衡二分木

平衡二分木も常に中身がソートされていることが期待されるコンテナですが、優先度付きキューと違うのは、値を取り出すのではなく、任意の値を閾値とする最大値や最小値を高速に参照したい点です。これも .Net ライブラリの組み合わせでできそうなのにできない。

私は自前で書きました。Treap というアルゴリズムを使っています。長いです。

class Treap<T> where T : IComparable
{
    private class Node
    {
        private static Random g_rand = new Random();
        private readonly int m_rank = g_rand.Next();
        private readonly T m_value;
        private Node m_lch;
        private Node m_rch;
        private int m_count;

        public Node(T value)
        {
            m_value = value;
            m_count = 1;
        }

        private static int Count(Node node)
        {
            return (node != null) ? node.m_count : 0;
        }

        private Node Update()
        {
            m_count = Count(m_lch) + Count(m_rch) + 1;
            return this;
        }

        public static Node Merge(Node a, Node b)
        {
            if (a == null) { return b; }
            if (b == null) { return a; }

            if (a.m_rank < b.m_rank)
            {
                a.m_rch = Merge(a.m_rch, b);
                return a.Update();
            }
            else
            {
                b.m_lch = Merge(a, b.m_lch);
                return b.Update();
            }
        }

        public static Tuple<Node, Node> Split(Node t, int k)
        {
            if (t == null) { return new Tuple<Node, Node>(null, null); }

            if (k <= Count(t.m_lch))
            {
                var pair = Split(t.m_lch, k);
                t.m_lch = pair.Item2;
                return new Tuple<Node, Node>(pair.Item1, t.Update());
            }
            else
            {
                var pair = Split(t.m_rch, k - Count(t.m_lch) - 1);
                t.m_rch = pair.Item1;
                return new Tuple<Node, Node>(t.Update(), pair.Item2);
            }
        }

        public int FindIndex(T value)
        {
            int L = Count(m_lch);
            if (value.CompareTo(m_value) < 0)
            {
                return (m_lch != null) ? m_lch.FindIndex(value) : 0;
            }
            else if (value.CompareTo(m_value) > 0)
            {
                return (m_rch != null) ? m_rch.FindIndex(value) + L + 1 : L + 1;
            }
            else
            {
                return L;
            }
        }

        public T this[int i]
        {
            get
            {
                int L = Count(m_lch);
                if (i < L)
                {
                    return m_lch[i];
                }
                else if (i > L)
                {
                    return m_rch[i - L - 1];
                }
                else
                {
                    return m_value;
                }
            }
        }
    }

    private Node node;

    public void Insert(T value)
    {
        if (node != null)
        {
            int k = node.FindIndex(value);
            var pair = Node.Split(node, k);
            node = Node.Merge(Node.Merge(pair.Item1, new Node(value)), pair.Item2);
        }
        else
        {
            node = new Node(value);
        }
    }

    public int FindIndex(T value)
    {
        return node.FindIndex(value);
    }

    public T this[int i]
    {
        get
        {
            return node[i];
        }
    }
}

長いですが、外から見えるのは Insert と FindIndex とインデクサ [ ] だけです。いずれも O(log n) で動きます。