TERRYのブログ

最近は競技プログラミングにお熱。

Sponsored Link

トップ > 競プロ > AtCoderで使えそうなC# 7.0～8.0の新機能

AtCoderで使えそうなC# 7.0～8.0の新機能

競プロ C# .NET Core

先日4/12のABC162からAtCoderのジャッジシステムが更新され、以前のMono 4.6.2（C# 6.0）に代えて.NET Core 3.1.2（C# 8.0）が使えるようになりました。*1 atcoder.jp

せっかく最新のC#が使えるので、競プロに便利かなーと思われる機能をピックアップして紹介していきます。それぞれサラッとしか触れないので、詳しく知りたい方は++C++;さんとかをご参照いただければ。

Tuple （C#7.0）

個人的に一番嬉しいのがTuple（ValueTuple構造体）の導入です。*2 ufcpp.net

匿名型とかに似てるんですが、(int sum, int count)みたいな形で値の組を手軽に作ったりバラしたりすることができます。

static void TupleTest()
{
    var (sum, count) = GetSumAndCount(new[] { 1, 2, 3, 4, 5 });
    Console.WriteLine(sum);    // 15
    Console.WriteLine(count);  // 5
}

static (int sum, int count) GetSumAndCount(IEnumerable<int> collection)
{
    var sum = collection.Sum();
    var count = collection.Count();
    return (sum, count);
}

また、よくあるswap処理をしたいときはわざわざ一時変数を使わずともこんな感じに。

var a = 1;
var b = 2;
(a, b) = (b, a);
System.Console.WriteLine($"a={a}, b={b}");

あとは入力の時に便利かなと。AtCoderだとよくスペース区切りで以下のような入力が与えられることがあるかと思います。

10000 abc

例えば以下のような拡張メソッドを作成しておいて、

using System.IO;

public static class TextReaderExtensions
{
    public static T1 ReadValues<T1>(this TextReader reader) => (T1)Convert.ChangeType(reader.ReadLine(), typeof(T1));

    // 標準入力（Console.In）とかから文字列を読んでSplit()してTuple<T1, T2>にして返す
    public static (T1, T2) ReadValues<T1, T2>(this TextReader reader, char separator = ' ')
    {
        var inputs = reader.ReadLine().Split(separator);
        var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));
        var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));
        return (v1, v2);
    }

    public static (T1, T2, T3) ReadValues<T1, T2, T3>(this TextReader reader, char separator = ' ')
    {
        var inputs = reader.ReadLine().Split(separator);
        var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));
        var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));
        var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3));
        return (v1, v2, v3);
    }
}

こんな感じでまとめて値を読み取ってあげることができます。

var (n, s) = Console.In.ReadValues<int, string>();
Console.WriteLine(n);   // 10000
Console.WriteLine(s);   // abc

なお、「片方いらない」みたいなときは_で受け取ると値の破棄が可能です。

static void TupleTest()
{
    var (n, _) = Console.In.ReadValue<int, string>();
    Console.WriteLine(n);
    var (_, count) = GetSumAndCount(new[] { 1, 2, 3, 4, 5 });   // _は何度でも使える
    Console.WriteLine(count);
}

static (int sum, int count) GetSumAndCount(IEnumerable<int> collection)
    => (collection.Sum(), collection.Count());

Span （C# 7.2）

次はC# 7.2で追加されたSpan<T>構造体です。配列とか文字列のような、「連続したデータの並び」を全部ひっくるめて参照する型です。「安全なポインター」と言っても良いかもしれません。 ufcpp.net

配列に対して

Span<T>を使うと、配列の一部分だけ読み書きするような処理がやりやすくなります。配列に関してはAsSpan拡張メソッドが用意されているので、それを使ってSpan<T>に変換することができます。

int[] array = new[] { 1, 2, 3, 4, 5 };
Span<int> span = array.AsSpan().Slice(1, 3);  // 1番目から3個分の要素を切り出し

for (int i = 0; i < span.Length; i++)
{
    span[i] = 0;    // 切り出した部分を書き換え
}

foreach (int element in array)
{
    Console.WriteLine(element); // 1,0,0,0,5が出力される
}

Sliceメソッドは、Span<T>の一部分を切り出すメソッドです。int offsetみたいなのを持ってarray[offset + i]のようにすることもできますが、Span<T>を使うと以下のようなメリットがあるかなと思います。

  • 添え字の範囲で悩まなくてよくなる
  • offset + iの計算が発生しないので速い
  • for (int i = 0; i < span.Length; i++)の部分でコンパイラの最適化がかかり、範囲チェックがなくなるため速い
    • array[offset + i]だとoffset + iが配列からはみ出してないか毎回範囲チェックがかかる

もっとも競技プログラミングでそこまでギリギリを攻めた速度を求められることは少ないでしょうが、unsafeを使わずとも手軽に速く読みやすくなるのは嬉しいです。後ろに示すIndexやRangeと組み合わせて使うのもおすすめです。

一方で、以下のような制限もあるので、そこは注意が必要です。

  • IEnumerable<T>を実装していないのでLINQは使えない
    • foreachはOK
  • スタック上にしか確保できず、クラスのメンバーにできない
    • yield returnやawaitのあるメソッド内での使用も、コンパイラが暗黙的にクラスを生成するためNG
    • 代わりにMemory<T>を使えば回避可能

文字列に対して

文字列に対しても使えます。C#のstring型は読み取り専用のデータ列なので、AsSpanメソッドで得られるのは読み取り専用のReadOnlySpan<char>型になります。

string atcoder = "AtCoder";
ReadOnlySpan<char> code = atcoder.AsSpan(2, 4);  // atcoder.AsSpan().Slice(2, 4)と同じ
foreach (var c in code)
{
    Console.Write(c);   // "Code" が出力される
}

string.Substringに似ているんですが、Substringは文字列の一部分をコピーして新しい文字列を作成する一方、AsSpanの方は元の文字列への参照を作成するだけなのでとても速いです。BenchmarkDotNetで適当に両者の速度を比較してみました（各種設定はデフォルト）。

メソッド 平均(ms) 標準偏差(ms)
string.Substring 3448.312 36.844
AsSpan 0.146 0.002
空のfor文 0.024 0.000

さすがにコピーが発生しない分AsSpanが圧倒的に速いですね。テスト部分のコードを以下に貼っておきます。

public class SubStringBenchmark
{
    const int N = 100000;
    // 100000文字の文字列
    const string s = "01234567890123456789..";

    [Benchmark]
    public string SubString()
    {
        string output = null;
        for (int i = 0; i < N; i++)
        {
            output = s.Substring(i, N - i);
        }
        return output;
    }

    [Benchmark]
    public string AsSpan()
    {
        ReadOnlySpan<char> output = null;
        for (int i = 0; i < N; i++)
        {
            output = s.AsSpan(i, N - i);
        }
        return output.ToString();
    }

    [Benchmark]
    public string OnlyFor()
    {
        int i = 0;
        for (i = 0; i < N; i++) {}
        return i.ToString();
    }
}

ref foreach （C# 7.3）

foreachのループ変数を参照として受け取ることができるようになりました（普通の配列等は現時点で対応していないため、標準ライブラリ内だとほぼSpan<T>専用の機能です）。 ufcpp.net

上のSpan<T>のサンプルコードは、以下のように書き換えることができます。配列の添え字でごちゃごちゃしなくなるのが嬉しいです。

int[] array = new[] { 1, 2, 3, 4, 5 };
Span<int> span = array.AsSpan().Slice(1, 3);  // 1番目から3個分の要素を切り出し

foreach (ref var element in span)
{
    element = 0;    // spanの参照先を書き換え
}

foreach (int element in array)
{
    Console.WriteLine(element); // 1,0,0,0,5が出力される
}

Index, Range （C# 8.0）

配列やSpan<T>等に対して、「後ろからi番目」や「iからj番目まで」といった書き方ができるようになりました。配列の添え字って個人的に混乱しやすくて苦手なのでありがたいです。 ufcpp.net

Index

「後ろからi番目」をarray[^i]という形で書くことができます。インデックスは1始まりで、配列の最後の要素を参照するときはarray[^0]ではなくarray[^1]と書く必要があることにだけ注意しましょう。array[array.Length - i]と同義と考えると覚えやすいかも？++C++;さんの説明が詳しいです（丸投げ）。

int[] array = new[] { 1, 2, 3, 4, 5 };
Console.WriteLine(array[0]);    // 1が出力される
Console.WriteLine(array[^1]);   // 後ろから1番目（前からLength - 1番目）である5が出力される

Range

「iからj番目まで（ただしjは含まない）」をarray[i..j]という形で書くことができます。もちろん、上のIndex型と絡めてarray[i..^k]という形で書くこともできます。

Span<int> array = new[] { 1, 2, 3, 4, 5 }.AsSpan(); // 配列のコピーを避けるためSpan<T>にしておくとよい

foreach (var element in array[1..3]) // 1番目から2番目（3番目の手前まで）を切り出し（≒Slice）
{
    Console.WriteLine(element); // 2,3が出力される
}

foreach (var element in array[2..^1]) // 2番目から^2番目（^1番目の手前まで）を切り出し
{
    Console.WriteLine(element); // 3,4が出力される
}

Range range = 2..^0;    // Range構造体という扱い。これは2番目から^0番目（最後の要素）まで。
range = 2..;            // 「最初から」または「最後まで」のとき、片方は省略可能（2..^0と同じ意味）
var (offset, length) = range.GetOffsetAndLength(array.Length);
Console.WriteLine(offset);  // 2
Console.WriteLine(length);  // 4

if文内のis演算子（C# 7.0, 8.0）

本来switch文とかも含めたそこそこ大きい機能なんですが、一部分だけつまみ食い。 ufcpp.net

if文内の中でis演算子を使い、型チェック＋nullチェック＋変数宣言を同時にできるようになりました。int?[]とかで宣言した配列について、nullでないときだけ処理したいみたいな場合に使えるかなと思います。ただしvarで受けると型チェックはもちろんnullチェックもされないので注意。

var array = new int?[] { 1, 2, null, 4, null} ;
foreach (var value in array)
{
    if (value is int n) // nullでない場合のみnで受ける
    {
        Console.WriteLine(n); // 1,2,4が出力される
    }
}

最後に

C# 7.0～8.0の新機能のうち、AtCoderで使えそうなものを紹介してみました。他にもswitch文／式のパターンマッチングやパフォーマンス向上に使えるreadonly structおよびin引数、2進数リテラル、ローカル関数、throw式等々たくさんの機能がありますが、とりあえず上に書いたものを覚えておけば不便することはないかなと思います。

4/18日現在、AtCoderの過去問は新ジャッジシステムが適用されていませんが、公式生放送によると遅くとも5月上旬頃には対応できそうとのこと。過去問も気持ち良く書けるようになりそうで楽しみです。

それでは、素敵なC#競プロライフを！

*1:Monoについてはコンパイラがmcs 6.8.0（C# 7.2相当？C# 7.3とか8.0は使えなさそう）に更新されたほか、.NET Coreと同じRoslyn版コンパイラであるcsc 3.5.0（こちらはC# 8.0が使えそう）も使えるようになりました。

*2:Tupleクラス？知らない子ですね……。