C#で競技プログラミングをしていて思ったことや手に入れた知識(バッドノウハウ含む)をまとめておく．
C#で競技プログラミングをする上で基本的な知識はEmkさんの競技プログラミングのための C# （4.0 以降） の Tips 詰め合わせが非常によくまとまっているので，そちらの記事には載っていないことを中心に書いていく．
C#で競技プログラミングをはじめるべきか
もしC#であることにこだわりがないのならば，C++かJavaにした方が無難．使用人数が桁違いだし，多くのオンラインジャッジで使用可能．
入出力
Codeforces対策
CodeforcesでC#を使う際には注意点があって，CultureInfoがロシアのものになっているため小数点の点が'.'ではなく','になる．対策としてはSystem.Globalization名前空間にあるCultureInfoクラスにあるInvariantCultureというプロパティを使えば大丈夫．
var value = Double.Parse(1.0,System.Globalization.CultureInfo.InvariantCulture);
Console.WriteLine(value.ToString(System.Globalization.CultureInfo.InvariantCulture));
毎回こう書くのはだるいので，入出力をサポートするクラスやメソッドを用意しておいた方がよい．特に出力はTextWriter.FormatProviderがInvariantCultureを返すようにしておくのがよい．これは読取り専用のプロパティなのでStreamWriterを継承したクラスのFormatProviderをオーバーライドしてやるのが楽．
class Printer : StreamWriter
{
public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } }
public Printer(Stream stream) : base(stream, new UTF8Encoding(false, true)) { }
public Printer(Stream stream, Encoding encoding) : base(stream, encoding) { }
}
Console.WriteLineを使いたければこれをConsole.SetOut(new Printer(Console.OpenStandardOutput()));してやればよい．
入出力の高速化
最速を目指すならばDllImportを使用してlibc.dllなどからCの関数を呼び出すのが最も速い．
しかしながら，ジャッジの環境に依存するので，どの環境でも使えるわけでもない．
そもそもそこまで入出力がボトルネックになることは少ないためC#の範囲内だけで十分事足りると思う．
入力の高速化
int.Parseはそこまで遅くないので，それほど実行時間が劇的に変化することはない．
それでも高速化を狙うならばConsole.ReadLineなどを使わず，自前のクラスなどでストリームからの読み込みとパースを行うのがよい．
以下は使用しているものをベースにちょっとだけいじったもの．int[]として読み込んだりとかに対応していなかったり，ストリームの末尾を超えて読み込もうとした場合に例外を飛ばすようにしてある．
public class StreamScanner
{
public StreamScanner(Stream stream) { str = stream; }
private readonly Stream str;
private readonly byte[] buf = new byte[1024];
private int len, ptr;
public bool isEof = false;
public bool IsEndOfStream { get { return isEof; } }
private byte read()
{
if (isEof) throw new EndOfStreamException();
if (ptr >= len) {
ptr = 0;
if ((len = str.Read(buf, 0, 1024)) <= 0)
{
isEof = true;
return 0;
}
}
return buf[ptr++];
}
public char Char()
{
byte b = 0;
do b = read();
while (b < 33 || 126 < b);
return (char)b;
}
public string Scan()
{
var sb = new StringBuilder();
for (var b = Char(); b >= 33 && b <= 126; b = (char)read())
sb.Append(b);
return sb.ToString();
}
public long Long()
{
long ret = 0; byte b = 0; var ng = false;
do b = read();
while (b != '-' && (b < '0' || '9' < b));
if (b == '-') { ng = true; b = read(); }
for (; true; b = read())
{
if (b < '0' || '9' < b)
return ng ? -ret : ret;
else ret = ret * 10 + b - '0';
}
}
public int Integer() { return (int)Long(); }
public double Double() { return double.Parse(Scan(), CultureInfo.InvariantCulture); }
}
Codeforcesでも小数点を気にしなくていいようにしてある．
(後日手元でパフォーマンス計測を行った結果を追記します．)
出力の高速化
Console.WriteLineをそのまま使うと遅い．これはAutoFlushがtrueになっているためなので，falseにしてやって最後にFlushしてやればよい．Console.Outの型はTextWriterであるため，AutoFlushは直接いじれないので下記のようにする．
var sw = new StreamWriter(Console.OpenStandardOutput()){AutoFlush = false};
Console.SetOut(sw);
/*何らかの出力処理*/
Console.Out.Flush();
他にもStringBuilderに突っ込んでいって最後にConsole.WriteLine(stringBuilder.ToString())するという方法もあるが，MLEの危険性もあるのでおすすめできない．
$10^5$回程度出力する場合にはAtCoder上で大体500msぐらい早くなるので，間違いなくやった方がよい．(後日手元でパフォーマンス計測を行った結果も追記します．)
文字列の結合
C#でもJavaと同様，文字列の結合に'+'を使うことができる．
p_shiki37さんのJava競技プログラミングメモにも書かれているが大量に結合する場合にはC#でも同様にStringBuilderを使った方がよい．
出力の整形
"1 2 3 4 5"のように数をスペース区切りで出力する必要があることは比較的多い．
Console.Writeを複数回繰り返しても良いが以下のようにすると楽．
int[] a = {1,2,3,4,5};
var str = string.Join(" ", a);//"1 2 3 4 5";
Console.WriteLine(str);
拡張メソッドを用いると
static class Ex
{
static public string AsJoinedString<T>(this IEnumerable<T> ie, string st = " ")
{
return string.Join(st, ie);
}
}
Console.WriteLine(a.AsJoindString());
みたいに書けて個人的には便利(だけど，あまりおすすめはできない)．
var a = new char[20];
/*何らかの処理*/
Console.WriteLine("{0} {1} ,....., {20}",a);
みたいに書きたいことがある．しかし，このままでは実行時に例外を起こしてしまう．
その理由はConsole.WriteLine(format, params object[] args)にnew object[]{a}を渡しているような状態になっているため．これを解決するには以下のようにすればよい．
var a = new char[20];
/*何らかの処理*/
Console.WriteLine("{0} {1} ,....., {20}",a.OfType<object>().ToArray());
こうしてやるとaがchar[]からobject[]になるため，想定したように動作する．
これもバッドノウハウっぽいけど便利ではある．
コレクション
C#のコレクションはC++,Javaと比べて若干貧弱．
なんといっても優先度付キューがないのが厳しい．
他にも両端キューやC++でいうmultiset<T>やmultimap<K,V>がない．
SortedSet<T>を優先度付キューの代替として使用するテク
SortedSet<T>は重複した値を持てない．逆にいうとすべての値がユニークならば優先度付キューとして使える．
KeyValuePair<Key,Value>などを使って，値と一意に定まるキーを持たせてやればよい．
プログラミングコンテストで使用する要素は多くの場合$10^5$個程度なので，int型に十分収まるはず．
var pq = new SortedSet<KeyValuePair<int,long>>((l,r)=>
{
var cmp = l.Value.CompareTo(r.Value);
return (cmp!=0)?cmp:l.Key.CompareTo(r.Key);
})
int[] a = {4,1,5,3,2};
for(int i=0;i<5;i++)
pq.Add(new KeyValuePair<int,long>(i,a[i]));
while(pq.Any())
{
var p = pq.Min();
pq.Remove(p);
/*何らかの処理*/
}
SortedSet<T>は平衡二分探索木によって実装されているため，定数倍が非常に重い．
余裕があればライブラリに二分ヒープなどを用意しておいた方がよい．
以下に二分ヒープによる優先度付キューのソースコードを置いておく(蟻本に書いてあった二分ヒープをベースに実装したもの．)．
class PriorityQueue<T>
{
private readonly List<T> heap;
private readonly Comparison<T> compare;
private int size;
public PriorityQueue() : this(Comparer<T>.Default) {}
public PriorityQueue(IComparer<T> comparer) : this(16, comparer.Compare) { }
public PriorityQueue(Comparison<T> comparison) : this(16, comparison) { }
public PriorityQueue(int capacity, Comparison<T> comparison)
{
this.heap = new List<T>(capacity);
this.compare = comparison;
}
public void Enqueue(T item)
{
this.heap.Add(item);
var i = size++;
while (i > 0)
{
var p = (i - 1) >> 1;
if (compare(this.heap[p], item) <= 0)
break;
this.heap[i] = heap[p];
i = p;
}
this.heap[i] = item;
}
public T Dequeue()
{
var ret = this.heap[0];
var x = this.heap[--size];
var i = 0;
while ((i << 1) + 1 < size)
{
var a = (i << 1) + 1;
var b = (i << 1) + 2;
if (b < size && compare(heap[b], heap[a]) < 0) a = b;
if (compare(heap[a], x) >= 0)
break;
heap[i] = heap[a];
i = a;
}
heap[i] = x;
heap.RemoveAt(size);
return ret;
}
public T Peek() { return heap[0]; }
public int Count { get { return size; } }
public bool Any() { return size > 0; }
}
使い方は標準ライブラリのQueue<T>とほぼ同様のはず．SortedSet<T>みたいにIComparer<T>やComparison<T>とかをコンストラクタに渡してやればよい．
Linqは非対応(けどLinqを使いたい場面はまずないはず)．
(一応テスト済みのはずですが，間違っていたら指摘頂けると嬉しいです．)
SortedSet<T>
SortedSetはC++のset<T>やJavaのTreeSet<T>に相当するが，致命的な欠点がある．
set<T>のlower_boundやtreeSet<T>のlowerに相当する機能がない(SortedSet<T>のGetViewBetweenは$O(N)$で動作するため使いものにならない)．
この機能はsky58さんの競技プログラミングでたまに使われる名前の付いてないテクニックについてでも触れられており，非常に有用な機能なので，これを行えるような平衡二分探索木ライブラリを作っておくのがよい．
MultiSet<T>,MultiMap<K,V>
そんなものはないので平衡二分探索木を実装しよう．
Deque<T>
そんなものはない．スライド最小値をやるときに使う．
以下に実装したものをおいておく．
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]; }
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;
}
public T[] Items//デバッグ時に中身を調べるためのプロパティ
{
get
{
var a = new T[count];
for (int i = 0; i < count; i++)
a[i] = this[i];
return a;
}
}
}
基本的な操作には対応してるはず．Linqは非対応．
(一応テスト済みのはずですが，間違っていたら指摘頂けると嬉しいです．)
Dictionary<K,V>
Dictionary<K,V>は存在しないキーにアクセスした際，KeyNotFoundExceptionを発生させる．
これは普通にプログラムを書いている上では嬉しいが，競技プログラミング中には非常に面倒．
これを避けるにはContainsKey(key)を使って調べればよい．
var dic = new Dictionary<int,int>();
dic[0] = 1;//ok
dic[0]++; //ok
dic[0]+=2;//ok
dic[1]++;dic[1]+=2//throw KeyNotFoundException;
if(dic.ContainsKey(1))
dic[1]++; //ok
else dic[1]=1; //ok
var val = dic[2] //throw KeyNotFoundException;
int x;
if(dic.TryGetValue(2,out x))
Console.WriteLine(x);//ok
しかし，これは非常に面倒なので以下のようなクラスを作ると非常に便利．
class HashMap<K, V> : Dictionary<K, V>
{
new public V this[K i]
{
get
{
V v;
return TryGetValue(i, out v) ? v : base[i] = default(V);
}
set { base[i] = value; }
}
}
これは存在しないキーにアクセスした場合にdefault(V)を返す(Vが構造体ならばnew V()，参照型ならばnull)．
これを少しいじってdefault(V)以外の値を返すようにしても便利．
例えばジェネリックの型制約にwhere V:new()を追加してやればdefault(V)の代わりにnew V()とか書けてHashMap<int,List<int>>みたいなのを作るときに便利．
バッドノウハウなので，競技プログラミング用以外のコードで使うのはやめたほうがよい．
その他の知識
DPするときの配列の使い回し
2つの配列を使ってSwapしながらdpみたいなの、C#だと、 Array.Clear(next, ...) して Swap(dp, next) するより、 next = new[] ... してdp = next の方が速いなあ
— えいたほ (@eitaho) 2015, 1月 30
前者がTLEで、後者はACだった http://t.co/EqGi7HxUEB http://t.co/l8x0xw7Sg1 (diff)http://t.co/dP0av6zJhj
— えいたほ (@eitaho) 2015, 1月 30
らしい．理由が分かる人に解説をお願いしたい．
Enumerable.OrderByを使う際の注意
Linqは非常に便利だが，OrderByを使うときには注意が必要．
最悪ケースでソートに$O(N^2)$かかるっぽい($10^5$要素のソートでTLEした)．
対策としてはsource.OrderBy(x=>rand.Next()).OrderBy(x=>x)のように一度シャッフルするか，Array.Sortを使用する(こちらは最悪ケースにおいても$O(NlogN)$1※これは.NET4.5からのようです．ジャッジの環境が分からないときもシャッフルしたほうが安全かもしれません)．
List<T>のSortも最悪ケースで$O(N^2)$らしいとドキュメントにはあるので注意が必要2(内部的にはArray.Sortしているだけなので.NET4.5では$NlogN$のはず...？)．
OrderByはThenByと組み合わせられる利点があるので一概に使うべきではないとはいえないが，要素数が多いときはArray.Sortを使うのがよい．
ローカル環境とジャッジ環境でエントリポイントを変える
C#はエントリポイントを選ぶことができるので，ローカル環境でのみ何らかの処理を行うということができる．
より詳細にいえばコンパイルオプションでMainが存在するクラスであって，エントリポイントとして使いたいクラスを指定してやればよい．VisualStudioを使用している場合にはプロジェクトのプロパティ->アプリケーション->スタートアップから変更が行える．
以下のようにしてやることでローカル環境でのみ別の処理を行うことができる．
class Solver
{
public void Solve()
{
Console.WriteLine("Hello World");
}
static void Main()
{
var solver = new Solver();
solver.Solve();
}
}
class Local
{
static void Main()
{
var sw = new StopWatch();
sw.Start();
Console.SetIn(new StreamReader("input.in"));
var solver = new Solver();
solver.Solve();
Console.WriteLine("{0}ms",sw.ElapsedMilliseconds);
}
}
みたいにしてやればローカル環境でのみ標準入力をファイルから読み込んだり実行時間の計測したりできる．
プリプロセッサで#if Localとかやるのに比べたら便利だと思う．
コードを提出する際にMainが２つあるとコンパイルエラーを起こすので別ファイルに分けておくこと．
デリゲートを用いた再帰
FuncやActionなどのジェネリックデリゲートを用いた再帰の記述方法．以下のように書きたいが，コンパイルエラーが起こる．
Func<int,int> fib = i => (i<=1) ? 1 : fib(i-1) + fib(i-2);
これはfibに代入する時点ではfibが未定義の変数であるため．なので以下のようにすればよい．
Func<int,int> fib = null;
fib = i => (i<=1) ? 1 : fib(i-1) + fib(i-2);
しかし，実際のところ
public int fib(int i)
{
return (i<=1) ? 1 : fib(i-1) + fib(i-2);
}
と書かない理由はあまりない．ちなみにTopCoder ArenaではActionを使うとコンパイルエラーを起こすのでFuncを使ってnullなどのどうでもいい値を返すか，メソッドとして実装するかしてやる必要がある．
(ちなみにこの関数fibは当然のことながらメモ化再帰にした方がよい)
おわりに
入出力とコレクションに関してばかり書いた気もする．
競技プログラミングにおけるC#人口の増加やC#で競技プログラミングをしている人の助けになれば嬉しいです．
間違っているところはこうしたほうがよいというところがあれば指摘していただけると幸いです．
あと標準ライブラリのコレクションが強化されてほしい．