🐎

【競プロ】C#: 競技プログラミング環境構築 2022年版

2022/02/23に公開

.NET

競技プログラミング

競プロ

tech

以前、Qiita で同様の記事を書いていたのですが、アカウントを削除してまるごと消えてしまったので新たに作り直すことにします。

C# での競技プログラミング環境構築

構築するもの

ローカルで競技プログラミングの実行をできる
AtCoder などのコンテストサイトに投稿する

本記事では上記の2点を構築します。

より便利な環境構築を目指すならば私の使用している環境を参考にされるのも良いかもしれません。

1. ライブラリ不要の問題を提出できるようになるまで

IDE (Visual Studio) をインストール

まずは IDE をインストールします。

競技プログラミングということで非商用利用なはずなので、Visual Studio Community を使います。

Visual Studio Code でもできるとは思いますが、デバッグ実行などで便利なので Visual Studio を推奨します。

プロジェクト作成

Visual Studio をインストールしたら、「新しいプロジェクトを作成」から実行プロジェクトを作成します。

C# の「コンソールアプリ」を選びます。

フレームワークは AtCoder や Codeforces で使用可能な .NET Core 3.1 としておきます。

プロジェクト作成後に F5 キーを押して実行されたならOKです。

問題を解く

これで簡単な問題は解けるはずです。

例として AtCoder の practice contest を解いてみます。

using System;
using System.Linq;

internal class Program
{
    static void Main()
    {
        int a = int.Parse(Console.ReadLine());
        int[] bc = Console.ReadLine().Split().Select(int.Parse).ToArray();
        string s = Console.ReadLine();
        Console.WriteLine($"{a + bc[0] + bc[1]} {s}");
    }
}

ライブラリを使う

AtCoder の問題は AtCoder Library(ACL) を前提としているものも多くあります。

ということで、AtCoder Library Practice Contest の問題を解いて提出する環境を整えます。

NuGetからインストール

まずはプロジェクトにライブラリを追加します。

右のソリューションエクスプローラーで作成したプロジェクトを右クリックして「NuGetパッケージの管理」でNuGet管理画面を開きます。

「参照」タブでインストールしたいライブラリを検索してインストールします。

ここでは下記の2つをインストールします。

ac-library-csharp は ACL の C#移植、SourceExpander は提出用のソースコードを作成するライブラリです。

作成した csproj

<Project Sdk="Microsoft.NET.Sdk">

  <PropertyGroup>
    <OutputType>Exe</OutputType>
    <TargetFramework>netcoreapp3.1</TargetFramework>
  </PropertyGroup>

  <ItemGroup>
    <PackageReference Include="ac-library-csharp" Version="1.9.1" />
    <PackageReference Include="SourceExpander" Version="4.0.2" />
  </ItemGroup>

</Project>

ACL を使って問題を解く

AtCoder Library Practice Contest の問題を ac-library-csharp を使って解いてみましょう。

Program.cs

using AtCoder;
using System;
using System.Linq;

internal class Program
{
    static void Main()
    {
        SourceExpander.Expander.Expand();

        int n, Q;
        var line = Console.ReadLine().Split();
        n = int.Parse(line[0]);
        Q = int.Parse(line[1]);

        var dsu = new DSU(n);

        for (int i = 0; i < Q; i++)
        {
            var query = Console.ReadLine().Split().Select(int.Parse).ToArray();
            if (query[0] == 0)
                dsu.Merge(query[1], query[2]);
            else
                Console.WriteLine(dsu.Same(query[1], query[2]) ? 1 : 0);
        }
    }
}

SourceExpander.Expander.Expand(); によって、実行したファイル(デフォルトのままなら Program.cs)と同じフォルダに Combined.csx というファイルが生成されます。

Combined.csx

using AtCoder;
using AtCoder.Internal;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.CompilerServices;
internal class Program
{
    static void Main()
    {
        SourceExpander.Expander.Expand();

        int n, Q;
        var line = Console.ReadLine().Split();
        n = int.Parse(line[0]);
        Q = int.Parse(line[1]);

        var dsu = new DSU(n);

        for (int i = 0; i < Q; i++)
        {
            var query = Console.ReadLine().Split().Select(int.Parse).ToArray();
            if (query[0] == 0)
            {
                dsu.Merge(query[1], query[2]);
            }
            else
            {
                Console.WriteLine(dsu.Same(query[1], query[2]) ? 1 : 0);
            }
        }
    }
}
#region Expanded by https://github.com/kzrnm/SourceExpander
namespace AtCoder{public class DSU{internal readonly int _n;public readonly int[]_parentOrSize;public DSU(int n){_n=n;_parentOrSize=new int[n];_parentOrSize.AsSpan().Fill(-1);}public int Merge(int a,int b){int x=Leader(a),y=Leader(b);if(x==y)return x;if(-_parentOrSize[x]<-_parentOrSize[y])(x,y)=(y,x);_parentOrSize[x]+=_parentOrSize[y];_parentOrSize[y]=x;return x;}public bool Same(int a,int b){return Leader(a)==Leader(b);}public int Leader(int a){if(_parentOrSize[a]<0)return a;while(0<=_parentOrSize[_parentOrSize[a]]){(a,_parentOrSize[a])=(_parentOrSize[a],_parentOrSize[_parentOrSize[a]]);}return _parentOrSize[a];}public int Size(int a){return-_parentOrSize[Leader(a)];}public int[][]Groups(){int[]leaderBuf=new int[_n];int[]id=new int[_n];var resultList=new SimpleList<int[]>(_n);for(int i=0;i<leaderBuf.Length;i++){leaderBuf[i]=Leader(i);if(i==leaderBuf[i]){id[i]=resultList.Count;resultList.Add(new int[-_parentOrSize[i]]);}}var result=resultList.ToArray();int[]ind=new int[result.Length];for(int i=0;i<leaderBuf.Length;i++){var leaderID=id[leaderBuf[i]];result[leaderID][ind[leaderID]]=i;ind[leaderID]++;}return result;}}}
namespace AtCoder.Internal{public class SimpleList<T>:IList<T>,IReadOnlyList<T>{private T[]data;private const int DefaultCapacity=2;public SimpleList(){data=new T[DefaultCapacity];}public SimpleList(int capacity){data=new T[Math.Max(capacity,DefaultCapacity)];}public SimpleList(IEnumerable<T>collection){if(collection is ICollection<T>col){data=new T[col.Count];col.CopyTo(data,0);Count=col.Count;}else{data=new T[DefaultCapacity];foreach(var item in collection)Add(item);}}public Memory<T>AsMemory()=>new Memory<T>(data,0,Count);public Span<T>AsSpan()=>new Span<T>(data,0,Count);public ref T this[int index]{[MethodImpl(MethodImplOptions.AggressiveInlining)]get{if((uint)index>=(uint)Count)ThrowIndexOutOfRangeException();return ref data[index];}}public int Count{get;private set;}public void Add(T item){if((uint)Count>=(uint)data.Length)Array.Resize(ref data,data.Length<<1);data[Count++]=item;}public void RemoveLast(){if( --Count<0)ThrowIndexOutOfRangeException();}public SimpleList<T>Reverse(){Array.Reverse(data,0,Count);return this;}public SimpleList<T>Reverse(int index,int count){Array.Reverse(data,index,count);return this;}public SimpleList<T>Sort(){Array.Sort(data,0,Count);return this;}public SimpleList<T>Sort(IComparer<T>comparer){Array.Sort(data,0,Count,comparer);return this;}public SimpleList<T>Sort(int index,int count,IComparer<T>comparer){Array.Sort(data,index,count,comparer);return this;}public void Clear()=>Count=0;public bool Contains(T item)=>IndexOf(item)>=0;public int IndexOf(T item)=>Array.IndexOf(data,item,0,Count);public void CopyTo(T[]array,int arrayIndex)=>Array.Copy(data,0,array,arrayIndex,Count);public T[]ToArray()=>AsSpan().ToArray();bool ICollection<T>.IsReadOnly=>false;T IList<T>.this[int index]{get=>data[index];set=>data[index]=value;}T IReadOnlyList<T>.this[int index]{get=>data[index];}void IList<T>.Insert(int index,T item)=>throw new NotSupportedException();bool ICollection<T>.Remove(T item)=>throw new NotSupportedException();void IList<T>.RemoveAt(int index)=>throw new NotSupportedException();IEnumerator IEnumerable.GetEnumerator()=>((IEnumerable<T>)this).GetEnumerator();IEnumerator<T>IEnumerable<T>.GetEnumerator(){for(int i=0;i<Count;i++)yield return data[i];}public Span<T>.Enumerator GetEnumerator()=>AsSpan().GetEnumerator();private static void ThrowIndexOutOfRangeException()=>throw new IndexOutOfRangeException();}}
namespace SourceExpander{public class Expander{[Conditional("EXP")]public static void Expand(string inputFilePath=null,string outputFilePath=null,bool ignoreAnyError=true){}public static string ExpandString(string inputFilePath=null,bool ignoreAnyError=true){return "";}}}
#endregion Expanded by https://github.com/kzrnm/SourceExpander

Combined.csx に ac-library-csharp のコードも埋め込まれています。これをまるごと提出すればOKです。
ダミーのメソッドが埋め込まれるので提出時には影響ありません。

提出例

Competitive.IO

Console.ReadLine や Console.WriteLine は数が多いと非常に遅くなってしまうので TLE してしまうことがあります。

大量の入出力で高速化を図った Competitive.IO というライブラリを作成しているので良かったら使ってください。
もちろん SourceExpander に対応しています。

ライブラリを作る

競プロをやっていると自作ライブラリを作りたくなるかと思います。

ソリューションエクスプローラーでソリューションを右クリックして、「追加」→「新しいプロジェクト」でライブラリ用のプロジェクトを作成しましょう。

注意: 実行プロジェクトにライブラリを作成した場合は SourceExpander が動作しません。仕様上の制約からライブラリは実行プロジェクトと別でなければならないためです。

作成したライブラリに SourceExpander.Embedder の参照を追加すれば、自動で展開されます。

自作ライブラリで ac-library-csharp を使いたければ、ac-library-csharp の参照を追加すればOKです。

自作ライブラリの例

最大公約数を求める関数を使ってみます。

ライブラリ

namespace CompetitiveKaisetsu.Library
{
    public static class MathLibEx
    {
        /// <summary>
        /// 最大公約数
        /// </summary>
        public static int Gcd(int a, int b) => b > a ? Gcd(b, a) : (b == 0 ? a : Gcd(b, a % b));
        /// <summary>
        /// 最大公約数
        /// </summary>
        public static long Gcd(long a, long b) => b > a ? Gcd(b, a) : (b == 0 ? a : Gcd(b, a % b));
    }
}

実行側

internal class Program
{
    static void Main()
    {
        SourceExpander.Expander.Expand();
        CompetitiveKaisetsu.Library.MathLibEx.Gcd(22, 7);
    }
}