2023 年の AtCoder 言語アップデートで新しく使えるようになった C# の機能について、競技プログラミングの観点で使えそうなものをピックアップします。
Native AOT
新しいコンパイル方式で、ネイティブのバイナリに変換してくれます。理論上 C++ 並みの実行速度を期待できるので、 C#er にとってはこの上ない福音でしょう。
問題にもよりますが、C++ と C# (JIT) の間くらいの実行時間になります。もちろん、旧来のコンパイル方式 (JIT) も利用可能です。
JIT コンパイルの場合は ML.NET という機械学習用ライブラリが使用可能です。AtCoder で ML.NET がどれくらい輝くかは未知数です。
Generic Math
ジェネリックで四則演算や論理演算 (bitwise XOR なんかも使える) を呼び出すことができます！！！！セグ木、ModInt、行列累乗あたりのライブラリが整備しやすくなります。
ジェネリックとは任意の型に対してクラスやメソッド等を定義できる機能のことです。
ジェネリックにて使う型に特定の機能を持っていてほしい場合は、その機能を示すインターフェースを明示する必要があります。そうすることでインターフェースを実装するクラスのみをジェネリック型に取れます。
しかし、今までの C# には四則演算や論理演算などに対するインターフェースは存在しかったので、そのような演算を抽象化する場合には面倒な書き方を強いられていました。
(たとえば、readonly struct に必要な演算を入れることや、式木 Expression Tree を用いる方法が有名でした。)
.NET 7 / C# 11.0 以降は数値演算のインターフェースが定義できるようになったので、例えば「和を取れる型 T の IEnumerable<T> に対する総和を求める」とか「総和じゃなくて総 XOR を求める」とかも簡単にできるようになります。
ビット演算、和の単位元や積の単位元、果ては三角関数などもあり、至れり尽くせり。
膨大な量のインターフェースが存在しており、詳しく書くと非常に面倒です。調べたときには別記事を書くかもしれません。
Top-level statement
C# 9.0 まではプログラムで最初に実行する文 (エントリーポイント) は Main() 関数でないといけませんでした。
しかし、C# 10.0 以降は Python のようなスクリプト言語かのように、何もないところに処理を突然書けるようになりました。
こういうことが C# のコードとして許されるわけです。
Console.WriteLine("Hello World!");
ABC-A/B くらいの問題ならたった数行で AC できます。意味不明すぎる。もはやスクリプト言語。
var a = Console.ReadLine().Split().Select(p => int.Parse(p)).ToArray();
Console.WriteLine(a[0] * a[1] % 2 == 0 ? "Even" : "Odd");
https://atcoder.jp/contests/language-test-202301/submissions/44839386
Implicit usings というのがあるので基本的な機能なら using もいらないらしいです。
https://ufcpp.net/blog/2021/11/implicitusings/
Priority queue
これが C# では今まで存在しなかった。嘘でしょ？
最小四分ヒープであり、優先度の小さい順に取り出されます。また、 ac-library-csharp と異なり要素を優先度と同一視しない ( ac-library-csharp では要素と優先度が同じ) ので、要素と優先度を必ず指定する必要があります。使い方が異なることに要注意です。
また、優先度は Dequeue() や Peek() によって参照できないので競技プログラミング的には不便かもしれません。
ただし、 TryDequeue() や TryPeek() では取得できるので、ちょっと面倒ですが優先度を見たいときはこっちを使いましょう。
| メソッド | 時間計算量 |
|---|---|
| 要素を事前に与えるコンストラクタ | $O(N)$ |
Enqueue() | $O(\log N)$ |
Dequeue() | $O(\log N)$ |
Peek() | $O(1)$ |
要素を事前に与えるコンストラクタは heapify というアルゴリズムを使用していて、要素を一つ一つ Enqueue() する ($O(N\log N)$) よりも効率が良いです。
また、 EnqueueDequeue() という Enqueue() する直後に Dequeue() する操作を定数倍良く実装するメソッドもあります。
ac-library-csharp
AtCoder Library の C# 移植版です。現在 kzrnm さん が管理されています。
https://github.com/kzrnm/ac-library-csharp にて公開されています。NuGet でもインストールできます。
今回のアップデート以降、AtCoder 上では using AtCoder; を宣言するだけで使えるので便利になりました。
LINQ 新メソッド
.NET 6 で新しく LINQ のメソッドがたくさん追加されました。
https://learn.microsoft.com/ja-jp/dotnet/core/whats-new/dotnet-6#new-linq-apis
TryGetNonEnumeratedCount() 以外は競プロでの用途があると思います。
以下、詳しく各メソッドの解説をします。IEnumerable<T> を指して「配列」と呼んでいますがご容赦ください。
TryGetNonEnumeratedCount()
ご存知の通り、 IEnumerable<T> は遅延評価により LINQ 等のメソッドを評価しています。遅延セグ木と全く同じで、データ変更クエリはデータ参照クエリが来たときに初めて展開・評価する仕組みになっています。
このメソッドでは遅延評価なしに要素数を参照できる (厳密には ICollections<T> を実装する) ならその要素数を取得し、できないならその旨を報告します。
C#/.NET は実行時エラーを避けるためのセーフな関数をたくさん用意するので、納得はできる関数です。でも競技プログラミングではあまり使わなさそう。
Chunk()
配列の要素を一定の個数ごとに分割するのを一発でしてくれるメソッドです。平方分割に使えそう。
MaxBy(), MinBy()
OrderBy() のように、配列の要素からキーへの写像を与えることで、その写像を適用した値を基準にして最大値・最小値を求めることができます。
写像だけでなく、比較するための関数を IComparer<T> で与えることもできます。
これも活用例がたくさん思いつきますね。タプルのリスト List<(int a, int b)> list について、 b が最大値を取る要素の a は list.MaxBy(p => p.b).a で書けます。すごく使えそう。
DistinctBy()
競プロ C#er みんな大好き Distinct() がキー指定できるようになって帰ってきた！
MaxBy(), MinBy() 同様、要素のキーを指定して重複する値を削除するメソッドです。これも便利そうですね。
ExceptBy(), IntersectBy(), UnionBy()
それぞれ差集合、積集合、和集合をキー指定して求められます。
覚えておくとたまに使えそう？
ElementAt(), ElementAtOrDefault()
IEnumerable<T> の index 番目の要素を取得できます。
絶対メソッドチェーン使うマン向けの機能です。
また、 ElementAtOrDefault() は配列外参照したらその型のデフォルト値を返します。競技プログラミングならこれを使わずデバッガーで確認したほうが楽だし、余計にバグの原因になると思います。
FirstOrDefault(), LastOrDefault()
配列の最初の値・最後の値 (または引数で与えた条件を満たす要素のうち最初の値・最後の値) を返す関数です。
元の配列が空、もしくは該当する要素が存在しない場合には型で定められた既定値を返すのですが、指定した値を規定値に設定することができるようになりました。逆に今までなんでなかったんだろう。
SingleOrDefault()
要素数 1 の配列の要素 (または引数で与えた条件を満たす唯一の要素) を返す関数です。先程のメソッドと同様の機能が追加されました。
競技プログラミングだと微妙に使わないかもしれない。
Max(), Min()
IComparer<T> を与えることで好きな比較関数を用いて最大値・最小値を計算できるようになりました。地味に便利。
Take()
配列の start から end 番目の範囲を抜き出すには Take() と Skip() を組み合わせる必要がありましたが、 Take() の引数に Range 構造体を与えることで一発でできるようになりました。
Zip()
今まで 2 つの配列をまとめることしかできませんでしたが、3 つの配列をまとめられるようになります。
ただ、3 つをまとめる場合は現時点では残念ながらタプルにまとめることしかできないようです。
正規表現のパフォーマンス強化
稀に使えるかもしれない。
DateTime のマイクロ秒・ナノ秒サポート
競技プログラミングでも時間を測って実行したい場面があると思います。あるいは乱数のシードにミリ秒まで入れた時刻を入れたいこともあるかと思います。
今まではミリ秒・マイクロ秒を求めるには Ticks プロパティから逐一計算する必要がありましたが、その必要がなくなりました。やった！