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.
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
が2つあるとコンパイルエラーを起こすので別ファイルに分けておくこと.
##デリゲートを用いた再帰
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#で競技プログラミングをしている人の助けになれば嬉しいです.
間違っているところはこうしたほうがよいというところがあれば指摘していただけると幸いです.
あと標準ライブラリのコレクションが強化されてほしい.