C#で競技プログラミングをし続ける人のためのTips

C#で競技プログラミングをしていて思ったことや手に入れた知識(バッドノウハウ含む)をまとめておく．
C#で競技プログラミングをする上で基本的な知識はEmkさんの[競技プログラミングのための C# （4.0 以降） の Tips 詰め合わせ](http://emkcsharp.hatenablog.com/entry/2013/Advent)が非常によくまとまっているので，そちらの記事には載っていないことを中心に書いていく．

#C#で競技プログラミングをはじめるべきか
もしC#であることにこだわりがないのならば，C++かJavaにした方が無難．使用人数が桁違いだし，多くのオンラインジャッジで使用可能．

#入出力
##Codeforces対策
[Codeforces](http://codeforces.com/)でC#を使う際には注意点があって，CultureInfoがロシアのものになっているため小数点の点が'.'ではなく','になる．対策としてはSystem.Globalization名前空間にある`CultureInfo`クラスにある`InvariantCulture`というプロパティを使えば大丈夫．

```csharp
var value = Double.Parse(1.0,System.Globalization.CultureInfo.InvariantCulture);
Console.WriteLine(value.ToString(System.Globalization.CultureInfo.InvariantCulture));

```
毎回こう書くのはだるいので，入出力をサポートするクラスやメソッドを用意しておいた方がよい．特に出力は`TextWriter.FormatProvider`が`InvariantCulture`を返すようにしておくのがよい．これは読取り専用のプロパティなので`StreamWriter`を継承したクラスの`FormatProvider`をオーバーライドしてやるのが楽．

```csharp
    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[]`として読み込んだりとかに対応していなかったり，ストリームの末尾を超えて読み込もうとした場合に例外を飛ばすようにしてある．

```csharp
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`は直接いじれないので下記のようにする．

```csharp
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競技プログラミングメモ](http://qiita.com/p_shiki37/items/65c18f88f4d24b2c528b#%E6%96%87%E5%AD%97%E5%88%97%E7%B5%90%E5%90%88)にも書かれているが大量に結合する場合にはC#でも同様に`StringBuilder`を使った方がよい．

##出力の整形
"1 2 3 4 5"のように数をスペース区切りで出力する必要があることは比較的多い．
`Console.Write`を複数回繰り返しても良いが以下のようにすると楽．

```csharp
int[] a = {1,2,3,4,5};
var str = string.Join(" ", a);//"1 2 3 4 5";
Console.WriteLine(str);
```

拡張メソッドを用いると

```csharp
static class Ex
{
    static public string AsJoinedString<T>(this IEnumerable<T> ie, string st = " ") 
    {
        return string.Join(st, ie);
    }
}
Console.WriteLine(a.AsJoindString());
```
みたいに書けて個人的には便利(だけど，あまりおすすめはできない)．


他にも[Bayan Bus](http://codeforces.com/problemset/problem/475/A)や[ボーリングゲーム](http://code-formula-2014-quala.contest.atcoder.jp/tasks/code_formula_2014_qualA_b)のように

```csharp
var a = new char[20];
/*何らかの処理*/
Console.WriteLine("{0} {1} ,....., {20}",a);
```

みたいに書きたいことがある．しかし，このままでは実行時に例外を起こしてしまう．
その理由は`Console.WriteLine(format, params object[] args)`に`new object[]{a}`を渡しているような状態になっているため．これを解決するには以下のようにすればよい．

```csharp
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`型に十分収まるはず．

```csharp
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>`は平衡二分探索木によって実装されているため，定数倍が非常に重い．
余裕があればライブラリに二分ヒープなどを用意しておいた方がよい．
以下に二分ヒープによる優先度付キューのソースコードを置いておく(蟻本に書いてあった二分ヒープをベースに実装したもの．)．

```csharp
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<T>はC++の`set<T>`やJavaの`TreeSet<T>`に相当するが，致命的な欠点がある．
`set<T>`の`lower_bound`や`treeSet<T>`の`lower`に相当する機能がない(`SortedSet<T>`の`GetViewBetween`は$O(N)$で動作するため使いものにならない)．
この機能はsky58さんの[競技プログラミングでたまに使われる名前の付いてないテクニックについて](http://topcoder.g.hatena.ne.jp/skyaozora/20141216)でも触れられており，非常に有用な機能なので，これを行えるような平衡二分探索木ライブラリを作っておくのがよい．

##`MultiSet<T>,MultiMap<K,V>`
そんなものはないので平衡二分探索木を実装しよう．

##`Deque<T>`
そんなものはない．スライド最小値をやるときに使う．
以下に実装したものをおいておく．

```csharp
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)`を使って調べればよい．

```csharp
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
```
しかし，これは非常に面倒なので以下のようなクラスを作ると非常に便利．

```csharp
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するときの配列の使い回し
<blockquote class="twitter-tweet" lang="ja"><p>2つの配列を使ってSwapしながらdpみたいなの、C#だと、&#10;Array.Clear(next, ...) して Swap(dp, next) するより、&#10;next = new[] ... してdp = next の方が速いなあ</p>&mdash; えいたほ (@eitaho) <a href="https://twitter.com/eitaho/status/561150668832915456">2015, 1月 30</a></blockquote>
<script async src="//platform.twitter.com/widgets.js" charset="utf-8"></script>
<blockquote class="twitter-tweet" lang="ja"><p>前者がTLEで、後者はACだった&#10;<a href="http://t.co/EqGi7HxUEB">http://t.co/EqGi7HxUEB</a>&#10;<a href="http://t.co/l8x0xw7Sg1">http://t.co/l8x0xw7Sg1</a>&#10;(diff)<a href="http://t.co/dP0av6zJhj">http://t.co/dP0av6zJhj</a></p>&mdash; えいたほ (@eitaho) <a href="https://twitter.com/eitaho/status/561150867194142722">2015, 1月 30</a></blockquote>
<script async src="//platform.twitter.com/widgets.js" charset="utf-8"></script>
らしい．理由が分かる人に解説をお願いしたい．

##`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を使用している場合にはプロジェクトのプロパティ->アプリケーション->スタートアップから変更が行える．
以下のようにしてやることでローカル環境でのみ別の処理を行うことができる．

```csharp:solver.cs
class Solver
{
    public void Solve()
    {
        Console.WriteLine("Hello World");
    }
    static void Main()
    {
        var solver = new Solver();
        solver.Solve();
    }
}
```

```csharp:local.cs
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`などのジェネリックデリゲートを用いた再帰の記述方法．以下のように書きたいが，コンパイルエラーが起こる．

```csharp
Func<int,int> fib = i => (i<=1) ? 1 : fib(i-1) + fib(i-2); 
```
これは`fib`に代入する時点では`fib`が未定義の変数であるため．なので以下のようにすればよい．

```csharp
Func<int,int> fib = null;
fib = i => (i<=1) ? 1 : fib(i-1) + fib(i-2); 
```

しかし，実際のところ

```csharp
public int fib(int i)
{
    return (i<=1) ? 1 : fib(i-1) + fib(i-2);
}
```
と書かない理由はあまりない．ちなみにTopCoder Arenaでは`Action`を使うとコンパイルエラーを起こすので`Func`を使って`null`などのどうでもいい値を返すか，メソッドとして実装するかしてやる必要がある．
(ちなみにこの関数`fib`は当然のことながらメモ化再帰にした方がよい)

#おわりに
入出力とコレクションに関してばかり書いた気もする．
競技プログラミングにおけるC#人口の増加やC#で競技プログラミングをしている人の助けになれば嬉しいです．
間違っているところはこうしたほうがよいというところがあれば指摘していただけると幸いです．
**あと標準ライブラリのコレクションが強化されてほしい．**

-----
[^1]: [MSDN Array.Sort<T> Method (T[])](https://msdn.microsoft.com/ja-jp/library/kwx6zbd4%28v=vs.110%29.aspx)
[^2]: [MSDN List<T>.Sort Method](https://msdn.microsoft.com/ja-jp/library/b0zbh7b6%28v=vs.110%29.aspx)