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

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. 最大公約数

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

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

2. 剰余演算

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

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

Mが素数のとき、フェルマーの小定理から次の式が導かれます(ちなみに 1,000,000,007 は素数です)。除算の場合にはこれを用いなければなりません。
$$a \div b \equiv a \times b^{M-2} \pmod M$$
そして、累乗の計算には繰り返し二乗法と呼ばれる高速化のアルゴリズムが必須です。これらを真面目に組んでいると、それだけでコンテストの時間が終わってしまいます。手元に持っておきましょう。コード例です。

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

3. Union-Find 木

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

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

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# にはありません。

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

5. 優先度付きキュー

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

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

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

6. 平衡二分木

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

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

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

ソフトウェアの設計・実装がうまく行かなくてお困りではありませんか? 組込屋にお任せください。リモート案件は、常駐の半額でお受けしています。

コメントを残す

メールアドレスが公開されることはありません。

日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)