競技プログラミングのための C# (4.0 以降) の Tips 詰め合わせ
この記事は、Competitive Programming Advent Calendar Div2013 - PARTAKE の10日目の記事です。
はじめに
長い年月を経て、ついにTopCoderの C# 環境が、.NET Framework 2.0 から .NET Framework 4.0 へとアップグレードされました。
そこでさっそく TopCoder の 本番 SRM で使用する言語を C++ から C# へと変更しました。また、それまで競技プログラミングで早解き系のコンテストで C# を使ったことがほとんどなかったため、備忘録として本ブログでSRMの過去問を C# 4.0 で解くようにしました。
本記事では、過去問を解く過程で得た、競技プログラミング向けの簡単な C♯ の小技をまとめています。
C♯4.0 が利用できるオンラインジャッジ
標準ライブラリにあるデータ構造系のクラス
基本的に System.Collections.Generic
で定義されているジェネリックコレクションクラスを使います。
System.Collections
に定義されているArrayList
などの非ジェネリッククラスは過去の遺物のため使いません。
// ダブルリンクリスト System.Collections.Generic.LinkedList<T> // STLの list に相当 // リスト System.Collections.Generic.List<T> // STLの vector に相当 // キュー System.Collections.Generic.Queue<T> // STLの queue に相当 // スタック System.Collections.Generic.Stack<T> // STLの stack に相当 // 辞書 System.Collections.Generic.SortedDictionary<TKey,TValue> // STLの map に相当 System.Collections.Generic.Dictionary<TKey,TValue> // キーで並び替えされないが SortedDictionary より高速 // 集合 System.Collections.Generic.SortedSet<T> // STLの set に相当 System.Collections.Generic.HashSet<T> // キーで並び替えされないが SortedSet より高速 // 多倍長整数 System.Numerics.BigInteger // 複素数 System.Numerics.Complex // STLの complex<double> に相当
例外でオーバーフローチェック
整数同士の演算にオーバーフローが発生したとき、そのまま処理が続行されて全く違うところでエラーが発生するよりは、オーバーフロー発生時で例外が発生したほうが便利です。
そこで C♯ には、オーバーフローが発生したときに OverflowException
を発生させる checked キーワードがあります。
int x = int.MaxValue; int y = checked(x + 1); // → OverFlowException
ただし、関数の内部でのオーバーフローについては検知しません。
static int overflow() { int x = int.MaxValue; return x + 1; } static void Main(string[] args){ int y = checked(overflow()); // overflow関数内でオーバーフローしても例外は発生しない。 }
また、この checked キーワードを使わなくても、コンパイルオプションの /checked
を使用するとデフォルトでコード全域のオーバーフローチェックが有効になります。
Visual Studio 2012 を使っている場合は、
プロジェクトのプロパティ→「ビルド」タブ→詳細設定ボタン→「演算のオーバーフローおよびアンダーフローのチェック」にチェックを入れると有効になります。
実際にオーバーフローさせて、例外が発生したときの標準エラー出力が以下のようになります。どこでオーバーフローが起きるいるのか一目瞭然ですね。
ハンドルされていない例外: System.OverflowException: 算術演算の結果オーバーフローが発生しました。 場所 LittleElephantAndString.getNumber(String A, String B) 場所 d:\Topcoder\LittleElephantAndString.cs:行 41 場所 LittleElephantAndStringHarness.runTestCase(Int32 casenum__) 場所 d:\Topcoder\LittleElephantAndString.cs:行 117 場所 LittleElephantAndStringHarness.run_test(Int32 casenum) 場所 d:\Topcoder\LittleElephantAndString.cs:行 70 場所 LittleElephantAndString.Main(String[] args) 場所 d:\Topcoder\LittleElephantAndString.cs:行 49
ただし浮動小数点型の場合はオーバーフロー例外が発生しないので注意してください。
LINQ
配列に対する簡単な操作や集計については、LINQ のメソッドを使うと簡潔に書けます。
これらのメソッドは、IEnumerable<T> に対して定義されているため、それを実装している
List<T>
Queue<T>
Stack<T>
SortedDictionary<TKey,TValue>
Dictionary<TKey,TValue>
SortedSet<T>
HashSet<T>
String
などからも使用することができます。
// using System.Linq; しておくこと var empty = new int[] {}; var a1533 = new int[] { 1, 5, 3, 3 }; /* 最大値 */ a1533.Max(); // → 5 empty.Max(); // → InvalidOperationException empty.DefaultIfEmpty(-1).Max(); // → -1 (空の場合は -1 を返す) /* 最小値 */ a1533.Min(); // → 1 empty.Min(); // → InvalidOperationException empty.DefaultIfEmpty(-1).Min(); // → -1 (空の場合は -1 を返す) /* 合計値 */ a1533.Sum(); // → 12 empty.Sum(); // → 0 /* 平均 */ a1533.Average(); // → 3.0 empty.Average(); // → InvalidOperationException empty.DefaultIfEmpty(-1).Average(); // → -1 (空の場合は -1 を返す) /* 逆順 */ a1533.Reverse().ToArray(); // → { 3, 3, 5, 1 } /* フィルタ */ a1533.Where(s => s < 4).ToArray(); → // { 1, 3, 3 } /* 写像(map) */ a1533.Select(s => s * 2).ToArray(); // → { 2, 10, 6, 6 } /* 写像&平坦化 (concatMap) */ a1533.SelectMany(s => new[] { s, s }).ToArray(); // → { 1, 1, 5, 5, 3, 3, 3, 3 } /* マージ */ a1533.Zip(new int[] { 1, 2, 1, 2 }, (a, b) => a + b).ToArray(); // { 2, 7, 4, 5} /* 重複削除 */ a1533.Distinct().ToArray(); // → { 1, 5, 3 } /* 最初の要素 */ a1533.First(); // → 1 empty.First(); // → InvalidOperationException empty.FirstOrDefault(); // → 0 (空の場合は例外を投げるのではなくその型の初期値を返す) /* 最後の要素 */ a1533.Last(); // → 3 empty.Last(); // → InvalidOperationException empty.LastOrDefault(); // → 0 (空の場合は例外を投げるのではなくその型の初期値を返す) /* 最初の要素(長さが1でない場合は例外を投げる) */ a1533.Single(); // → InvalidOperationException empty.Single(); // → InvalidOperationException a1533.SingleOrDefault(); // → InvalidOperationException empty.SingleOrDefault(); // → 0 (空の場合は例外を投げるのではなくその型の初期値を返す) /* X 番目の要素 */ a1533.ElementAt(1); // 5 a1533.ElementAt(99); // → ArgumentOutOfRangeException a1533.ElementAtOrDefault(99); // → 0(範囲外の場合は例外を投げるのではなくその型の初期値を返す) /* 先頭から要素を取得 */ a1533.Take(1).ToArray(); // → { 1 } /* 先頭から要素をスキップ */ a1533.Skip(1).ToArray(); // → { 5, 3, 3 } /* 先頭から条件を満たす要素を取得 */ a1533.TakeWhile(s => s == 1).ToArray(); // → { 1 } /* 先頭から条件を満たす要素をスキップ */ a1533.SkipWhile(s => s == 1).ToArray(); // → { 5, 3, 3 } /* 安定ソート */ a1533.OrderBy(s => s).ToArray(); // → { 1, 3, 3, 5} a1533.OrderByDescending(s => s).ToArray(); // → { 5, 3, 3, 1} /* 要素が全て条件を満たしているかを判定 */ a1533.All(s => s % 2 == 1); // → true /* 条件を満たす要素が存在するかを判定 */ a1533.Any(s => s % 2 == 0); // → false /* 条件を満たす要素の個数 */ a1533.Where(s => s == 3).Count(); // → 2 a1533.Count(s => s == 3); // → 2 /* 配列が空ではないかを判定 */ a1533.Any(); // → true empty.Any(); // → false
LINQ についてはクエリ構文や遅延読み込みなど、他にも知るべき知識があるのですが、ここでは深追いしません。
何度も実行される箇所では LINQ メソッド は使用しない
LINQ で定義されている関数 はとても便利ですが、ナイーブに書くよりもだいぶ速度が遅いので注意する必要があります。
高々 100000 回呼ぶだけなら、特に問題ないのですが 1000000回あたりを超えると TLE の危険があります。
上記のコードは
Math.Max
を 1000万回実行したときにかかる時間Enumerable.Max
を 1000万回実行したときにかかる時間Array.Length
を 1000万回実行したときにかかる時間Enumerable.Count
を 1000万回実行したときにかかる時間
を計るベンチマークです。
Math.Max : 24ms Enumerable.Max : 1363ms Array.Length : 8ms Enumerable.Count: 218ms
これを見て分かるとおり、単純な処理でも何度も呼び出されると時間が非常にかかることがわかります。
特に TopCoder では 1億回を超えるとまず TLE です。
目安として 100万回以上呼ばれうる箇所では LINQ を使用しないようにしましょう。
配列の初期化
// 標準的な配列生成 var array = new int[] {0, 3, 5}; // [0,1...] の配列を生成する var array = Enumerable.Range(0, 4).ToArray(); // {0, 1, 2, 3} // 初期値が全て同じ配列を生成する var array = Enumerable.Repeat(-1, 4).ToArray(); // → { -1, -1, -1, -1}
複数のキーでソートする
OrderBy / OrderByDescending
と ThenBy / ThenByDescending
と併用することで、複数のキーでソートすることができます。
以下は、x の昇順にソートして、 x が同じ座標については y の降順でソートしています。
int[] xs = { 1 , 1, 3, 2, 5, 5 }; int[] ys = { 2, -1, 1, 2, 5, 3 }; var xy = xs.Zip(ys, (x, y) => new { x, y }) .OrderBy(p => p.x) .ThenByDescending(p => p.y) .ToArray(); // [(x,y)]={(1,2),(1,-1),(2,2),(3,1),(5,5),(5,3)}
Array.Sort
を使用する場合は以下のように書きます。
Array.Sort
は OrderBy
を使うより2,3倍速いので速度を重視する場合に使います。
var xy = xs.Zip(ys, (x, y) => new { x, y }).ToArray(); Array.Sort(xy, (a, b) => { if (a.x != b.x) return a.x.CompareTo(b.x); return -a.y.CompareTo(b.y); });
i番目とi+1番目の要素を使った処理
Skip と Zip を組み合わせます。
以下は、 |array[i] - array[i+1]|
の合計を求める例です。
var array = new[] { 0, 2, 1, 3 }; var totalDiff = array.Zip(array.Skip(1), (a0, a1) => Math.Abs(a0 - a1)).Sum(); // → 5
範囲外アクセスの心配をする必要がないのがありがたいです。
座標圧縮
ToDictionary
を使うと、{値→index}のハッシュが簡単に生成できます。
int[] x1 = new[] { 100, 10, 1, 10000 }; int[] x2 = new[] { 10, 10000, -555 }; var indexFromValueTable = Enumerable.Concat(x1, x2).Distinct() .OrderBy(v => v) .Select((value, index) => new { value, index }) .ToDictionary(p => p.value, p => p.index); x1 = x1.Select(v => indexFromValueTable[v]).ToArray(); // {3,2,1,4} x2 = x2.Select(v => indexFromValueTable[v]).ToArray(); // {2,4,0}
メモ付き探索
null許容型の配列にメモることで、配列の要素を初期化する手間が省けます。
int?[,] memo = new int?[50, 50]; public int choose(int s, int t) { if (!memo[s, t].HasValue) { if (t == 0 || t == s) return 1; memo[s, t] = choose(s - 1, t - 1) + choose(s - 1, t); } return memo[s, t].Value; }
二次元ジャグ配列を生成する
Java では jag = new int[h][w]
と一行で書けるのですが、C♯では以下のように書く必要があります。
var jag = new int[h][]; for (int i = 0; i < h; i++) { jag[i] = new int[w]; }
Enumerable.Repeat
を使うと簡単に書けそうですが、これだと同一配列のインスタンスから構成されるジャグ配列になってしまいます。
// 間違った生成方法 int[][] jag = Enumerable.Repeat(new int[w], h).ToArray(); // jag[0][0] = 1; とすると jag[1][0] == 1 になる。
代わりにSelect
を利用することで正しく生成できるようになります。
int[][] jag = Enumerable.Range(0, h).Select(_ => new int[w]).ToArray();
多次元配列のサイズを求める
C++ の vector<vector<T>>
と混同して、縦(1次元目)の長さを求めるのに Length を使うのは間違いです。GetLength
を使います。
int[,] array = new int[3,4]; array.Length; // → 12 array.GetLength(0); // → 3 array.GetLength(1); // → 4
多次元配列で LINQ を使う
多次元配列は IEnumerable
を実装していますが、IEnumerable<T>
を実装していないため、LINQ のメソッドを使うことができません。
そこでCast<T>()
を使って IEnumerable<T>
に変換することで、LINQ メソッドを使用できるようになります。
int[,] grid = new int[,] { { 0, 1, 2 }, { 3, 4, 5 }, { 6, 7, 8 } }; var sequence = grid.Cast<int>().ToArray(); // → { 0, 1, 2, 3, 4, 5, 6, 7, 8} var maxValue = grid.Cast<int>().Max(); // → 8 var sumValue = grid.Cast<int>().Sum(); // → 36
文字列配列を全て結合して1つの文字列にする
TopCoderでよくある前処理の一つですが、String.Concat
を使えば一発です。
String.Concat(new String[] { "u" , "na" , "gi"}); // -> "unagi"
区切り文字を入れたい場合は、String.Join
を使います。
String.Join(",", new[] { "u", "na", "gi" }); // → "u,na,gi"
スペース区切りの数値からなる文字列を int の配列にする
String.Split
と LINQ の Select
を組み合わせます。
var s = "11 22 44"; s.Split().Select(s => int.Parse(s)).ToArray(); // -> new int[] {11,22,44} s.Split().Select(int.Parse).ToArray(); // delegate を直接渡すこともできます
文字列同士をASCIIの辞書順で比較する
文字列を比較する関数に String.Compare
やString.CompareTo
がありますが、この関数ではASCII辞書順比較になりません。
これは実行環境のカルチャを元に、その国の自然言語に応じた比較を行う仕様だからです。( .NET Framework で文字列を使用するためのベスト プラクティス
if('A'.CompareTo('a') < 0) // → true if("A".CompareTo("a") < 0) // → false // char型での比較(ASCII)と結果が違う!!
ASCII辞書順で文字列比較したい場合は、代わりにString.CompareOrdinal
を使います。
if(String.CompareOrdinal("A","a") < 0) // → true
同様の理由で、Array.Sort
やOrderBy
でのソートもASCII辞書順になりません。
/* ASCII辞書順比較ではないソート */ var array = new[] { "a-b", "ab", "-ab", "a-c", "ac", "-ac" }; Array.Sort(array); // → array = { "ab","a-b","-ab","ac","a-c","-ac" } array = array.OrderBy(c => c).ToArray(); // → array = { "ab","a-b","-ab","ac","a-c","-ac" }
ソート系の関数には、大抵引数に IComparer を渡せるので、そこに StringComparer.Ordinal
を渡すと、String.CompareOrdinal
で比較してくれます。
/* ASCII辞書順比較のソート */ var array = new[] { "a-b", "ab", "-ab", "a-c", "ac", "-ac" }; Array.Sort(array, StringComparer.Ordinal); // → array = { "-ab","-ac","a-b","a-c","ab","ac" } array = array.OrderBy(c => c, StringComparer.Ordinal).ToArray(); // → array = { "-ab","-ac","a-b","a-c","ab","ac" }
文字列で i 番目の文字を変更する
String は不変オブジェクトのため、添字アクセスで要素を更新することができません。
そのため、一旦 Char 配列にしてから編集します。
string s = "unagi"; //s[1] = 's'; ビルドエラー! Char[] array = s.ToCharArray(); // Char[] に変換 array[1] = 's'; new String(array); // 文字列に変換 → "usagi"
基数変換
数値から文字列への変換は Convert.ToString
、文字列から数値への変換は、Convert.ToInt32
, Convert.ToInt64
を使用します。
ただし、指定できる基数は 2, 8, 10, 16 の4種類のみです。
Convert.ToString(254, 2); // "11111110" Convert.ToString(254, 8); // "376" Convert.ToString(254, 16); // "fe" Convert.ToInt32("1111", 2); // 15 Convert.ToInt32("10", 8); // 8 Convert.ToInt32("ff", 16); // 255
関数内関数
言語仕様として関数内関数やマクロ関数はサポートされていませんが、デリゲート型+ラムダ式で同じようなことができます。
var g = new int[50, 50]; int n = 10; Func<int,int> IN = x => x; Func<int,int> OUT = x => x + n; Action<int,int,int> addEdge = (from, to, cost) => { g[from, to] = cost; }; addEdge(IN(0), OUT(1), 5);
残念ながら、TopCoderでは Action
が制限されて使えないので、Func
を代わりに使う必要が有ります。
標準ライブラリにはないもの
以下については、自前で実装しておく必要があります。
swap / rotate
lower_bound / upper_bound / equal_range
next_permutation / prev_permutation
deque / priority_queue / multiset / multimap
__builtin_popcount / Integer.BitCount (Java)
Scanner (Java)