競技プログラミングのための 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 が利用できるオンラインジャッジ

• TopCoder
• CodeForces
• AtCoder

標準ライブラリにあるデータ構造系のクラス

基本的に 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> に相当

System.Numerics が使用できる環境（TopCoder)では多倍長整数や複素数が利用できます。

例外でオーバーフローチェック

整数同士の演算にオーバーフローが発生したとき、そのまま処理が続行されて全く違うところでエラーが発生するよりは、オーバーフロー発生時で例外が発生したほうが便利です。

そこで C♯ には、オーバーフローが発生したときに OverflowException を発生させる checked キーワードがあります。

• checked (C# リファレンス)

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 を使用するとデフォルトでコード全域のオーバーフローチェックが有効になります。

• /checked (C# コンパイラ オプション)

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 のメソッドを使うと簡潔に書けます。

• C# の LINQ の概要
• Enumerable クラス (System.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 （空の場合は例外を投げるのではなくその型の初期値を返す）

/* 最初の要素（長さが１でない場合は例外を投げる） */
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 の危険があります。

http://ideone.com/839gvs

上記のコードは

• 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 を使うより２，３倍速いので速度を重視する場合に使います。

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>> と混同して、縦（１次元目）の長さを求めるのに 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

文字列配列を全て結合して１つの文字列にする

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 の４種類のみです。

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)

まとめ

大半が LINQ 関係になりましたが、それだけ LINQ は強力な道具ということです。

TopCoder SRM にて C♯で LINQ を使っている人は現在半数もいないので、C♯参加者の皆さんはどんどん LINQ を使いましょう。