この記事は、 MISW 56th Advent Calendar 2021の１日目の記事です。

C#の入門をしたい

はじめましての方ははじめまして、そうでは無い方もはじめまして。どうも、56代~~何もしない研~~プロ研のたまかけと申します。さて今回ですけれども、アドベントカレンダーを立てたはいいものの 何を書けばいいんだ…… となってしまって、それに12月2日、この記事が公開された翌日ですね、に微積のテストが迫っていたもので、軽めに書ける記事をやっていこうと思います。

この記事は、自分のようなC/C++のの基礎文法がわかるよという人が、C#を始めるにあたってちょっと躓いたなというところをまとめてみる、という感じで書いていこうと思います。

C＃の入門をしなきゃいけないらしい

なんやかんやでC#の入門をする必要が出てきてしまったので、早速入門していきます。私が新しい言語の入門をするとき、とりあえずその言語を使ってAtCoderの問題が解ければとりあえずの入門はできるだろと考えているので、今回はAtCoder Beginner Contest 218のA問題からE問題をC#を使って解いて行きます。 AtCoderの問題解けた程度で言語の入門した気になってんじゃねーぞとの声が盛大に聞こえてきますが、そんなことは誰も気にしない。まああとはC#といえばオブジェクト指向のなんとやらがアレでアレらしいので、そこらへんも触っていきます。

環境構築

本来なら早速問題を解いて行きたいところなのですが、やっぱりプログラミング言語の入門にあたって環境構築というものは避けて通れません。~~むしろ環境構築が一番むずかしい~~ ここではAtCoder環境で使えるC# (.NET Core 3.1.201) の環境を作っていきましょう。環境はWSL上に作っていきます。

qiita.com

.NET Coreを使用した開発について
.NET Coreで開発するためには、最低限、.NET Core SDKをインストールすればよい。

↑の記事を参考にしましてWSL上に簡単なC#の実行環境を導入、それでは本編やっていきましょう。

ほんへ

A問題

atcoder.jp

整数Nと文字列Sが与えられるので、SのN文字目がoかxで判定する問題。

▶コード

using System;

namespace main
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            string s = Console.ReadLine();
            if (s[n - 1] == 'o')
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }
}

めちゃめちゃ簡単な問題なのに自動生成のコードが長すぎて泣いちゃった。早速よくわからない概念、using、namespace、classとかが出てきましたね。いそいそと検索をかけると・・・

名前空間 - C# によるプログラミング入門 | ++C++; // 未確認飛行 C クラス - C# によるプログラミング入門 | ++C++; // 未確認飛行 C

namespaceを使ってclassを種類ごとに分けて管理する、またclassを使って機能をまとめて管理することができるんですねぇ～～なるほど namespaceは省略もできるっぽいので、今回の記事では省略する方向で行きましょう。
あと標準入力が

int n = int.Parse(Console.ReadLine());

stringで受け取ってそれぞれの型に変換する感じ、pythonっぽいですね

classとstructは違うんか？？

気になるのはclassとstructの違い。 C++ではclassとstructはほとんど違いの無いものとして扱うことができましたが、C#ではそうもいかないようです。C++では双方ともにstack領域にメモリを確保していましたが、classはメモリがheap領域に、structはメモリがstack領域に積まれるようです。

C#で大規模なデータを高速で処理したいときは、structを使ってデータをstack領域に積むことで値型として扱い高速にアクセスする、とかいうことができるらしいです。ちょっと頭の片隅に入れておきたいですね。

無知なもので詳しいことをあんまり語れないので、詳しく知りたい人は C# のメモリ管理 - C# によるプログラミング入門 | ++C++; // 未確認飛行 C を参照してみてください。

B問題

atcoder.jp

問題は26個の数列Pが与えられて、一般的なアルファベットのi番目の文字がP_i番目になった世界でのアルファベットの順番を出力する、という問題。普通にchar型の配列に指定された順番でアルファベットを詰めていけば解けそうですね。

▶コード

using System;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        int[] S = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();

        char[] ans = new char[26];
        for (int i = 0; i < 26; i++)
        {
            ans[i] = (char)('a' + S[i] - 1);
        }

        for (int i = 0; i < 26; i++)
        {
            Console.Write(ans[i]);
        }
        Console.WriteLine();
    }
}

配列を宣言するときにC++とかには無い文法、newが出てきました。C++では変数の宣言と同時にインスタンスが作成されていましたが、C#ではそうでは無いようです。

例えばint misw[];としたとき、確保されるのはstack領域のみであり、misw = int[334];として初めてheap領域に実際の値を格納するメモリを確保します。

これC++のように変数の宣言と同時にインスタンスを作成するようにしなかったのはなんでなんでしょうかね……？

ところでB問題では普通の配列を使いましたが動的配列、Listを使う際は

List<int> S = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToList();

と、配列とほとんど同じ要領で書くことができるようです。

C問題

atcoder.jp

▶コード・長い読む価値なし

文字列の配列が2つ与えられるので、2つの文字列配列の#で表された部分に関して回転、平行移動によって重ね合わせられるか、という問題。アルゴリズム的に難しいことは特になくて、上をごりごり実装していく。

using System;
using System.Linq;
using System.Collections.Generic;

class Program
{

    public static List<string> Trim(List<string> s)
    {
        int u = 0, d = s.Count - 1, l = 0, r = s.Count - 1;
        int n = s.Count;
        bool flag = false;

        for (; u < n; u++)
        {
            flag = false;
            for (int i = 0; i < n; i++) if (s[u][i] == '#') flag = true;
            if (flag) break;
        }

        for (; d >= 0; d--)
        {
            flag = false;
            for (int i = 0; i < n; i++) if (s[d][i] == '#') flag = true;
            if (flag) break;
        }

        for (; l < n; l++)
        {
            flag = false;
            for (int i = 0; i < n; i++) if (s[i][l] == '#') flag = true;
            if (flag) break;
        }

        for (; r >= 0; r--)
        {
            flag = false;
            for (int i = 0; i < n; i++) if (s[i][r] == '#') flag = true;
            if (flag) break;
        }

        List<string> res = new List<string>();
        for (int i = 0; i < d - u + 1; i++)
        {
            res.Add(s[u + i].Substring(l, r - l + 1));
        }

        return res;
    }

    public static List<string> Rotate(List<string> s)
    {
        int h = s.Count, w = s[0].Length;
        List<string> res = new List<string>();
        for (int i = 0; i < w; i++)
        {
            char[] tmp = new char[h];
            for (int j = 0; j < h; j++)
            {
                tmp[h - j - 1] = s[j][i];
            }
            res.Add(new string(tmp));
        }

        return res;
    }

    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());

        List<string> S = new List<string>();
        for (int i = 0; i < n; i++)
        {
            S.Add(Console.ReadLine());
        }

        List<string> T = new List<string>();
        for (int i = 0; i < n; i++)
        {
            T.Add(Console.ReadLine());
        }

        S = Program.Trim(S);
        T = Program.Trim(T);

        bool flag = false;
        for (int i = 0; i < 4; i++)
        {
            if (S.SequenceEqual(T))
            {
                flag = true;
            }
            S = Program.Rotate(S);
        }

        if (flag) Console.WriteLine("Yes");
        else Console.WriteLine("No");
    }
}

C#のstring型は要素が変更不可なので、下の画像のように要素変更することができないんですね。 {{

}}
なので、文字列の要素を一部だけ変更するには、

string phrase = "hanshin"
char[] phraseAsChars = phrase.ToCharArray();
phraseAsChars[2] = '4';

みたいに、一旦char型の配列に直す必要があります。ここは競プロをする上で非常にめんどくさpointですね。まあ文字列をこまこま処理するなんてことは競プロ以外ではほとんどやらないでしょうから、（やるにしても単語、文単位の置き換えくらいなもの？）これで困ることはあまりないでしょう。

staticとはなんぞや？？

staticは、クラス自身が変数やメソッドを持てるようにする機能のことのようです。

ではC問題のコードの中でTrim関数、Rotate関数を宣言する際に付いているstaticを除いて実行してみるとどうなるでしょう。 Program.cs(85,13): error CS0120: An object reference is required for the non-static field, method, or property 'Program.Trim(List<string>)' [/home/tamacake39/ppcpp/main/main.csproj] とエラーが発生して実効することができません。

調べてみると

shirakamisauto.hatenablog.com

こういうことらしい

クラス内のメンバーはクラスのインスタンスを生成して初めて使用可能（メモリ展開される）となります。しかし上記例のStaticMethodはstaticなメソッドなので、インスタンス化せず使用できます。（メモリが最初から確保されている）ところが、上記例のようにそのメソッド内にインスタンス化しなければ使えない変数objが含まれていると、メソッドを呼び出した際に、使用不可能な（メモリ上に存在しない）変数objにアクセスすることになり、正常な処理ができなくなります。

なるほど。main関数のようなstaticメソッドからインスタンスメソッドを呼び出そうとすると存在しないメモリへアクセスしてしまうことになるんですね。

ではどうコードを書けばよかったのかというと、staticを除いていた場合は例えば

Program Trimer = new Program();
S = Trimer.Trim(S);
T = Trimer.Trim(T);

とインスタンス化してあげる必要があります。しかし上でいうTrimインスタンスはデータに対して定まった一つのデータを返すいわば「関数」のため、そもそも複数のインスタンスが存在する必要がありません。そこで唯一存在するstaticメソッドとして宣言することで効率よくデータを処理することができるわけですね。（※ここ少し勘違いが入っている可能性があります。間違いがあったら指摘お願いします。）

D問題

atcoder.jp

たくさん点が与えられるので、そのうち4つを選んで長方形を作れるかという問題。長方形は対角線の2点が分かれば決定できるので、連想配列などを使って2点選んだときにもう2点が存在するかを判定すればOK

▶コード

using System;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        Dictionary<Tuple<int, int>, bool> map = new Dictionary<Tuple<int, int>, bool>();
        List<Tuple<int, int>> input = new List<Tuple<int, int>>();
        for (int i = 0; i < n; i++)
        {
            var values = Console.ReadLine().Split().Select(int.Parse).ToArray();
            input.Add(new Tuple<int, int>(values[0], values[1]));
            map[new Tuple<int, int>(values[0], values[1])] = true;
        }
        int ans = 0;
        for (int i = 0; i < n; i++)
        {

            for (int j = i + 1; j < n; j++)
            {
                if (input[i].Item1 == input[j].Item1 || input[i].Item2 == input[j].Item2) continue;
                if (map.ContainsKey(new Tuple<int, int>(input[i].Item1, input[j].Item2)) &&
                    map.ContainsKey(new Tuple<int, int>(input[j].Item1, input[i].Item2)))
                {
                    ans++;
                }
            }
        }
        Console.WriteLine(ans / 2);
    }
}

qiita.com

連想配列と一概に言えど、何個かあるらしい。違いはわからないけれど、要素の検索に関して、ListがO(n)であるのに対して、DictionaryとHashSetがO(1)（？！？！これマジ？！？！）、SortedDictionaryとSortedSetがO(log n)なことを覚えておけば良さそう。

あと上のコード内でmapからtupleの要素を検索する際に map.ContainsKey(new Tuple<int, int>(input[j].Item1, input[i].Item2))) としているのですが、これは毎回newをする必要があるのでしょうか。コンストラクタの無用な作成はプログラムの低速化の元だと聞いたので、解決策があればぜひ教えていただきたいです。

E問題

atcoder.jp

典型最小全域木の問題親の顔より見たUnionFindを使って解いていきましょう。

▶コード・長い読む価値なし

当然C#のdsuライブラリは持っていないので、ACLを参考に書いていきます。基本的なところはC++と変わらないので特に難しいことは無いです。（むしろ闇の言語C++の方が意味不明……）

using System;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        var nm = Console.ReadLine().Split().Select(int.Parse).ToArray();
        int n = nm[0], m = nm[1];
        List<Tuple<int, int, int>> cab = new List<Tuple<int, int, int>>();
        for (int i = 0; i < m; i++)
        {
            var input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            cab.Add(new Tuple<int, int, int>(input[2], input[0] - 1, input[1] - 1));
        }
        cab.Sort();

        long ans = 0;
        dsu uf = new dsu(n);
        for (int i = 0; i < m; i++)
        {
            if (!uf.merge(cab[i].Item2, cab[i].Item3))
            {
                ans += cab[i].Item1 > 0 ? cab[i].Item1 : 0;
            }
        }
        Console.WriteLine(ans);
    }
}

class dsu
{
    public dsu() { }
    public dsu(int n)
    {
        _n = n;
        parent_or_size = new List<int>();
        for (int i = 0; i < n; i++) parent_or_size.Add(-1);
    }
    public bool merge(int a, int b)
    {
        int x = leader(a), y = leader(b);
        if (x == y) return false;
        if (-parent_or_size[x] < -parent_or_size[y]) Swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return true;
    }
    public bool same(int a, int b)
    {
        return leader(a) == leader(b);
    }
    public int leader(int a)
    {
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }
    public int size(int a)
    {
        return -parent_or_size[leader(a)];
    }
    void Swap<T>(T a, T b)
    {
        var t = a;
        a = b;
        b = t;
    }
    private int _n;
    private List<int> parent_or_size;
}

ところでC#には標準でSwap関数が用意されてないのは驚きました。別に無くても何も困らないけど……

classを作成してその中にメソッドを定義しているわけですが、各メソッドの前にはpublicとprivateが記述されています。これはアクセスを制御するための機能で、これを用いると別のクラスから各メソッドに対するアクセスを自由に許可したり禁止したりすることができます。

これがあると何が嬉しいのかというと、外部から使って欲しいメソッドと使われたくないメソッドを明確に分けることで、メソッドが想定されていない使い方をされることによる予期せぬ動作を防止できたり、プログラムが複雑になっても使われたい機能を明確にすることができます。非常にバグらせにくくコードを書くことができる便利な機能ですね。

感想

C#……難しい……これを初心者向け言語として紹介してる人はどういう考えなんでしょうか…… まあ確かにunityやwindowsのGUIアプリには欠かせない言語ですから、遅かれ早かれ入門しないといけない言語というのは確かですね。あと、JavaやC#はインタープリターを介して実行するから遅いので競プロには向かないという定説があるようですが、今回入門した限りではあまりその遅さを感じなかったのは意外でした。

なんというかC#、至るところで型のことを意識させてくれるので、C++でクソコードばかり錬成している自分に突き刺さりました。C++では暗黙の型変換をしまくってしまうのですが、意識的にキャストする必要があるC#ではバグらせにくい？のでしょうか。

蛇足

これから25日間続く（はず）アドベントカレンダー、後続の記事もぜひよろしくおねがいします！明日は森くんの「ク　ソ　記　事　！　！　！　！」だそうです。森のことですからクソ記事といいながらなかなかクオリティの高い記事を書いてくるはずです。ワクワクですね。

C#の入門をしたい

C＃の入門をしなきゃいけないらしい

環境構築

.NET Coreを使用した開発について.NET Coreで開発するためには、最低限、.NET Core SDKをインストールすればよい。

ほんへ

A問題

classとstructは違うんか？？

B問題

C問題

staticとはなんぞや？？

D問題

E問題

感想

蛇足

.NET Coreを使用した開発について
.NET Coreで開発するためには、最低限、.NET Core SDKをインストールすればよい。