C# で競プロをする話 - うにゅーん、って感じだ

競プロアドベントカレンダー

これは、競プロアドベントカレンダーの6日目の記事です。
adventar.org

ところで、解説アドベントカレンダーというものがありまして、まだまだ全然空きがあるので、皆様どうぞよろしくお願いいたします。
adventar.org

この記事の内容

この記事は、競プロで C# を使っている人の思ったこととか苦労とかをただつらつらと書くもので、読んでもあまり得るものはないかもしれません。
もちろん C# を使っている人、興味がある人に読んでもらいたいですが、C++ 以外の言語をほぼ使わない人にも読んでもらいたいです。
また、自分は C# の言語仕様や関数にそこまで詳しいわけではないので、鉞などあれば twitter までお気軽にお願いします。
あと、この記事内に出てくるコードはほとんどがそれ単体では動かないコードなのでご注意ください。
twitter.com

この記事に類似した記事

これは camypaper さんの記事です。基本的にはこれみたいに進んでいきます。
qiita.com
LINQ は便利。
emkcsharp.hatenablog.com

C# で競プロをするべきか

特に理由がなければ、C++ を使っていれば良いと思います。ただ、C++ はクソなので個人的には C# を使う人が増えてくれると嬉しいです（それによって生まれる弊害に関して、私は一切の責任を負いません）。

C# の推しポイント

Visual Studio

もうこれがあるから C# を使っていると言っても過言ではない超優秀な IDE です。
Visual Studio は C++ でも使えますが、「VC++ は C++ ではない」という過激派がいたりするので Visual Studio + C++ な人は今すぐ C# に乗り換えるべき。

とは言いつつ、今は自分は Visual Studio は使っていません。Mac + Mono（C# コンパイラ） + Visual Studio Code（IDE ではないただのエディタ）という環境で C# を書いています。Visual Studio 以外で C# を書いている競プロer をあまり見たことがないので、いらっしゃいましたら教えてください。一体なんでこんな環境で書いているんだ…。

ところで最近 Visual Studio for Mac とかいうものが出てきましたが、あれは実質 Xamarin Studio なので C++ は使えません。やはり C# を使うべき。ちなみに自分はインストールしたら Macbook Air の容量をバカみたいに食ったので消しました。Xamarin Studio も巻き込まれて消えたのか、30GB くらい空きました。アプリ開発をしたくなったらまた入れます。

LINQ

LINQ とはなんぞや、という話は多分ここがわかりやすいです。
ufcpp.net
（このサイトは C# を書くなら多分めっちゃ見るサイトだと思います。めっちゃ詳しいしわかりやすくておすすめです）

あまり競プロと関係がなさそうにも見えますが、少し煩雑な処理がワンライナーで書けたりするので便利です。
例えば、配列の偶数の和（ただし複数回登場する数は 1 個だけ足す）を求めたいときは、

int sum = arr.Distinct().Where(x => x % 2 == 0).Sum();

で求まります。
愚直に書くのに比べて微妙に遅いのが少し残念ですが、使い慣れるととても強力な武器になります。

ラムダ式

上のコードに出てくる x => x % 2 == 0 のことです。
これは、だいたい以下の関数を表しています。

bool iseven(int x) {
    return x % 2 == 0;
}

もちろん複数引数の関数も定義できますし、返り値の型も自由です。
こちらが詳しいです。
ufcpp.net

ジェネリック

C++ で言う template みたいなものだと思います。ただ、こちらはもっと型に厳格なものです。
この記事がわかりやすいです。
ufcpp.net

配列外参照で RE

これはしてくれない言語の方が良くないと思うのですが、C# ではちゃんと配列外参照するとランタイムエラーになります。
Visual Studio と合わせると、どこで配列外参照してその時のこの変数に格納されている値はいくつ、みたいなのが見れるのでとても便利！（IDE なのでそれはそう）

入力

C++ には cin とかいう強力なやつがいますが、残念ながら C# にはそんな便利なものはありません。それどころか、次のスペースまで読む、ということができず、1文字読むか1行読むかしかできません。
なので、C#er の人々は自分で入出力を書いている人が多いです。

ただ、それは面倒臭いので、自分はラッパーを作るだけにとどめています。
以下で簡単な説明を（一行の文字数の関係で public やら static やらを省略しているので、適宜）

1行に 1入力

1行に 1入力であれば、普通に入力を取れます。

int Int => int.Parse(Str);
long Long => long.Parse(Str);
double Double => double.Parse(Str);
string Str => Console.ReadLine().Trim();

Trim は先頭末尾の空白を除去するというもので、時々サンプルをコピーしてくると入力の先頭末尾に空白が入っているクソ問題があったりするのでついています。

1行に複数入力（配列で取得）

int[] IntArr => StrArr.Select(int.Parse).ToArray();
long[] LongArr => StrArr.Select(long.Parse).ToArray();
double[] DoubleArr => StrArr.Select(double.Parse).ToArray();
string[] StrArr => Str.Split(new []{' '}, System.StringSplitOptions.RemoveEmptyEntries);

LINQ の Select というメソッドが Python でいう map のようなもので、それを使ってまとめて変換ができます。
Split は引数なしで空白区切りにしてくれるのですが、返される要素から空の要素を除去するオプションを念のため。
String.Split メソッド (String[], StringSplitOptions) (System)

1行に複数入力（個数分の変数に格納）

C++ の cin みたいな便利なのが欲しいと思って作りました（打つ文字数はどうしても多くなるので完全に cin みたいな使い勝手を実現できているとは言い難いですが…）。

bool eq<T, U>() => typeof(T).Equals(typeof(U));
T ct<T, U>(U a) => (T)Convert.ChangeType(a, typeof(T));
T cv<T>(string s) => eq<T, int>()    ? ct<T, int>(int.Parse(s))
                   : eq<T, long>()   ? ct<T, long>(long.Parse(s))
                   : eq<T, double>() ? ct<T, double>(double.Parse(s))
                   : eq<T, char>()   ? ct<T, char>(s[0])
                                     : ct<T, string>(s);
void Multi<T>(out T a) => a = cv<T>(Str);
void Multi<T, U>(out T a, out U b) {
var ar = StrArr; a = cv<T>(ar[0]); b = cv<U>(ar[1]);
}
void Multi<T, U, V>(out T a, out U b, out V c) {
var ar = StrArr; a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]);
}

このように使います。

int a; char b; string c;
Multi(out a, out b, out c);
// 100 A qwerty  みたいな入力を受け取れる

out キーワードはどうしても省略できなさそうで、つらい気持ちになっています（言語的には絶対に省略できてほしくないですが）。
あと、入力の数を可変にする方法を探しているのですが、out + params は使えないらしく、今は一つ一つ書いてあります。
ここには引数 3 つまでしか書いてないですが、自分のソースには 6 つまで書いてあります。
f:id:riantkb:20171206013110p:plain

意外と1行で色々な型の入力を受け取らなければいけないケースはわりと多いので、多分便利な方だと思います。

出力

camypaper さんの記事の方にもありますが、毎回 Flush して遅いので AutoFlush を false にしようという話があります。
自分の場合は大体こんな感じです。

static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
static void Main() {
    sw.WriteLine("Hello, World!");
    sw.Flush();
}

また、下のような関数が欲しかったので、ラッパーを作りました。

static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
static void Main() {
    int a = 10;
    string b = "qwerty";
    // 引数で与えたやつを空白区切りで出力してほしい
    Prt(a, b);
    // 10 qwerty

    int[] arr = { 1, 1, 4, 5, 1 };
    // 配列の中身を空白区切りで出力してほしい
    Prt(arr)
    // 1 1 4 5 1
    sw.Flush();
}
static void Prt(string a) => sw.WriteLine(a);
static void Prt<T>(IEnumerable<T> a) => Prt(string.Join(" ", a));
static void Prt(params object[] a) => Prt(string.Join(" ", a));

params によって可変長引数が取れ、それを空白区切りで結合してます。
確か string の配列を引数に渡すとコンパイルが通らないのですが、理由がよくわからないのと困ることが全然ないので今のところは放置しています。
それによりいわゆるフォーマット出力がやりづらくなりましたが、C# 6 でこんなものが追加されたので問題なし。
ufcpp.net

色々 C# にないもの

long double

そんなものはないです。諦めましょう。
ちなみに多倍長整数はあります。
BigInteger 構造体 (System.Numerics)

UpperBound/LowerBound

そんなものはないので自分で実装しましょう。

swap

ないはずですがさすがにこれくらいは必要だったら実装をすれば良いと思います。

Priority Queue

そんなものはないので実装しましょう。
自分はこの記事のサンプルソースを自己流に改変したものを使っています。
ufcpp.net

ググればいっぱい実装が出てきますし、最初に紹介した camypaper さんの記事にもあるので適当に拝借すれば良いでしょう。

どんな実害があるかというと、Dijkstra を実装するのにまず Priority Queue の実装から入る羽目になったりします。

deque

そんなものはないので自分で実装しましょう。ところで私は持っていません。
この前 deque を使う問題が出た時はなんか stack を組み合わせて解いた気がします。

set/map の upperbound/lowerbound

そんなものはないので平衡二分探索木を実装しましょう。ところで私は持っていません。
C++ と Java にはあるので当然どんな言語にもあるのだろうとか言っていつかのコード祭り予選 D 問題にそれが必要な問題が出て、クソかよと言ったこともあります。

ちなみに最近自分の取っている解決方法としては、諦めて C++ を書く、です。
（さすがにそろそろ庭に平衡二分探索木を植えなければならない）

multiset/multimap

そんなものはないので平衡二分探索木を実装しましょう。ところで私は持っていません。

next_permutation

そんなものはないので自分で実装しましょう。ところで私は持っていません。
どうしても必要な時は C++ を書きますが、なかなかそんなことはないです。

pair

普通に pair みたいな型は Tuple だったり KeyValuePair だったりがあったりしますが、比較が定義されていないので実装をしましょう。
ついでに make_pair も実装しましょう。
（自分の環境では using static util しています）

class pair<T, U> : IComparable<pair<T, U>> where T : IComparable<T> where U : IComparable<U>
{
    public T v1;
    public U v2;
    public pair(T v1, U v2) {
        this.v1 = v1;
        this.v2 = v2;
    }
    public int CompareTo(pair<T, U> a) => v1.CompareTo(a.v1) != 0 ? v1.CompareTo(a.v1) : v2.CompareTo(a.v2);
    public override string ToString() => v1 + " " + v2;
}
static class util
{
    public static pair<T, U> make_pair<T, U>(T v1, U v2) where T : IComparable<T> where U : IComparable<U> => new pair<T, U>(v1, v2);
}

#define

そんなものはないです。マクロいくない。
typedef に近いものはあります。

数値であることを表す interface

何が言いたいかと言うと、こういうことです。
C#のジェネリクスでできないこと - Qiita

それを解決する方法として、式木 (expression tree) を使うという方法があります。
ここはもうよくわからんなので、詳しくは以下を参照してください（自分はこのページの一番上にあるコードを利用しています）。
ufcpp.net

C# のつらいポイント

すでに上の C# にないもののコーナーで十分つらくはなりましたが……。

ICPC

C# が使えないコンテストは少ないながらいくつかありますが、その中で最も影響が大きいのが ICPC です（Java は使えるのに…）。
今年は C++ の練習を積んでから行ったのでまだどうにかなりましたが、去年までは本当に vector の sort すらできない有様でした。

他にはハル研のマラソン（あれはコードを用意する手間があるので致し方ない）や、C# が使えないのに VB が使えるとかいうわけのわからないコンテストがあったりしました。

AOJ

Aizu Online Judge の C#(mono) のバージョンがとても古く（おそらく AOJ_tutorial.pdf にある mono 2.10 から変更がない）、普段書いているコードがコンパイルを通りません。アロー演算子がダメなのはまだ良いのですが、string.Join の引数が string の配列しか許容されないのが本当にアレなので、最近は AOJ で問題を解く時はほとんど C++ で書いています（そもそも ICPC の練習で解くことが多いというのもある）。

配列などの初期化

基本的には、色々な参照型は new で初期化してあげる必要があるので、2 次元配列や List の配列などはすべて初期化して回らなければなりません。
一応 LINQ で回せばワンライナーにはできます。

var arr = new int[10][];
var lis = new List<int>[10];
// この時点で arr[0][0] = 1 や lis[0].Add(1) などをすることはできない

for (int i = 0; i < 10; ++i) {
    arr[i] = new int[20];
    lis[i] = new List<int>();
}