AtCoderに登録したら解くべき精選過去問 10 問を C# で解いてみた

# はじめに
drkenさんの[AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～](https://qiita.com/drken/items/fd4e5e3630d0f5859067#%E7%AC%AC-10-%E5%95%8F--abc-086-c---traveling-300-%E7%82%B9)で紹介されていた問題をC#で解いてみました。
[AtCoder Beginners Selection コンテストページ](https://beta.atcoder.jp/contests/abs)

なお、こちらの[AtCoderに登録したら解くべき精選過去問10問をRustで解いてみた](https://qiita.com/tubo28/items/e6076e9040da57368845)の二番煎じとなっております。

私は、競技プログラミングは好きなのですが得意ではなく、簡潔なコードで実装していないかもしれません。
"こうした方がいい"という点がありましたら指摘していただけると嬉しいです。

また、本記事中のコードは、以下に記述するコードのSolve関数の部分のみ記載します。

```c#
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));
        }

        public void Solve(ConsoleInput cin)
        {
            // 解答はココに書く
        }
    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); }}
        public int ReadInt { get { return int.Parse(Read); }}
        public long ReadLong { get { return long.Parse(Read); }}
        public double ReadDouble { get { return double.Parse(Read); }}
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret;}
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret;}
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret;}
    }
}

```

# 問題と提出コード
## 0問目 PracticeA - はじめてのあっとこーだー（Welcome to AtCoder）
3つの整数値と文字列を1つ受け取り、整数値の和と文字列を一行に出力する問題です。
C#では、変数の型を`var`とすることで、静的に型が決まります。
また、出力のフォーマット指定は$文字を用いて行います。

```c#
        public void Solve(ConsoleInput cin)
        {
            var a = cin.ReadInt;
            var b = cin.ReadInt;
            var c = cin.ReadInt;
            var s = cin.Read;
            WriteLine($"{a + b + c} {s}");
        }
```

## 1問目 ABC086A - Product
2つの整数値を受け取り、その積が2の倍数かを判定する問題です。
三項演算子を用いてこのように書けます。

```c#
        public void Solve(ConsoleInput cin)
        {
            var a = cin.ReadInt;
            var b = cin.ReadInt;
            WriteLine(a * b % 2 == 0 ? "Even" : "Odd");
        }
```

## 2問目 ABC081A - Placing Marbles
文字列を受け取り、1の個数をカウントする問題です。
LINQを用いてこのように書くことが出来ます。LINQについてはこちらの記事がおすすめです。[はじめてのLINQ](https://qiita.com/nskydiving/items/c9c47c1e48ea365f8995)
簡単に説明すると、文字列を1文字ずつに分割した配列から、'1'であるものだけを残し、その個数を数えています。

```c#
        public void Solve(ConsoleInput cin)
        {
            var s = cin.Read;
            WriteLine(s.Count(x => x == '1'));
        }
```

## 3問目 ABC081B - Shift only
N個の整数値を受け取り、一度の操作ですべての数を2で割る。割り切れなくなるまで割っていった時、何回割ることが出来るか？
整数値を２進数で表したとき、右から何個0が続いているか？を調べることで、その数を何回2で割り切ることが出来るか？が分かります。

```c#
        public void Solve(ConsoleInput cin)
        {
            var min = 30; // 今回はceil(log2(最大値))なら何でもいいです

            var N = cin.ReadInt;
            for (int i = 0; i < N; ++i)
            {
                var A = cin.ReadInt;
                var c = 0;
                while (A % 2 == 0 && A != 0) { A >>= 1; ++c; }
                min = Min(min, c);
            }
            WriteLine(min);
        }
```
ちなみにLINQを使って次のように書くことも出来ます。

```c#
        public void Solve(ConsoleInput cin)
        {
            var N = cin.ReadInt;
            var ans = cin.ReadIntArray(N).Min(x => {
                        var c = 0;
                        while (x % 2 == 0 && x != 0) { x >>= 1; ++c; }
                        return c;
                    });
            WriteLine(ans);
        }
```

## 4問目 ABC087B - Coins
500円玉をA枚、100円玉をB枚、50円玉をC枚持っているとき、これらの硬貨の中から何枚かを選び、合計金額をちょうどX円にする組み合わせを求める問題です。
これは、多重ループを用いて解くことができます。

```c#
        public void Solve(ConsoleInput cin)
        {
            var A = cin.ReadInt;
            var B = cin.ReadInt;
            var C = cin.ReadInt;
            var X = cin.ReadInt;
            var ans = 0;
            for (int i = 0; i <= A; ++i)
                for (int j = 0; j <= B; ++j)
                    for (int k = 0; k <= C; ++k)
                        if (500 * i + 100 * j + 50 * k == X)
                            ans++;
            WriteLine(ans);
        }
```
LINQのSelectMany関数を用いて、A,B,Cの組合せを列挙して解くことは出来ますが、ゴチャゴチャしてしまってあまり好きではありません。

```c#
        public void Solve(ConsoleInput cin)
        {
            var A = Enumerable.Range(0, cin.ReadInt + 1);
            var B = Enumerable.Range(0, cin.ReadInt + 1);
            var C = Enumerable.Range(0, cin.ReadInt + 1);
            var X = cin.ReadInt;
            var ans = A.SelectMany(_ => B, (a, b) => 500 * a + 100 * b).SelectMany(_ => C, (s, c) => s + 50 * c).Count(x => x == X);
            WriteLine(ans);
        }
```

## 5問目 ABC083B - Some Sums
1以上N以下の整数のうち、10進法での各桁の和がA以上B以下であるものの総和を求める問題です。
これは、1~Nまでの整数を一度文字列に変換し、各桁を足し合わせると簡単に求めることが可能です。

```c
        public void Solve(ConsoleInput cin)
        {
            var N = cin.ReadInt;
            var A = cin.ReadInt;
            var B = cin.ReadInt;
            var ans = 0;
            for (int i = 1; i <= N; ++i)
            {
                var sum = 0;
                foreach (var c in i.ToString())
                    sum += (int)(c - '0');
                if (A <= sum && sum <= B)
                    ans += i;
            }
            WriteLine(ans);
        }
```
LINQを用いるとこのように書けます。

```c#
        public void Solve(ConsoleInput cin)
        {
            var N = cin.ReadInt;
            var A = cin.ReadInt;
            var B = cin.ReadInt;
            var ans = Enumerable.Range(1, N).Where(n => {
                        var sum = n.ToString().Sum(c => (int)(c - '0'));
                        return A <= sum && sum <= B;
            }).Sum();
            WriteLine(ans);
        }
```

## 6問目 ABC088B - Card Game for Two
N枚のカードを二人で交互に取っていき、カードに書かれている数字の和の差を求める問題。
カードを降順ソート(大きい順に並べ替え)をして、交互に数字を足していけば良いです。

```c#
        public void Solve(ConsoleInput cin)
        {
            var N = cin.ReadInt;
            var a = cin.ReadIntArray(N);
            Array.Sort(a); Array.Reverse(a); // Array.Sortは昇順ソートを行います
            var alice = 0;
            var bob = 0;
            for (int i = 0; i < N; ++i)
            {
                if (i % 2 == 0) alice += a[i];
                else bob += a[i];
            }
            WriteLine(alice - bob);
        }
```

## 7問目 ABC085B - Kagami Mochi
N枚の整数値が与えられ、それらの重複しない要素の数を数える問題です。
このような場合にはHashSet(集合)のデータ構造を用いると簡単に求めることが出来ます。

```c#
        public void Solve(ConsoleInput cin)
        {
            var N = cin.ReadInt;
            var set = new HashSet<int>();
            for (int i = 0; i < N; ++i)
                set.Add(cin.ReadInt);
            WriteLine(set.Count());
        }
```
入力を受け取り、Enumerable<T>.Distinct関数で重複を削除するという方法もあります。

```c#
        public void Solve(ConsoleInput cin)
        {
            var N = cin.ReadInt;
            var d = cin.ReadIntArray(N).Distinct();
            WriteLine(d.Count());
        }
```

## 8問目 ABC085C - Otoshidama
10000円札と、5000円札と、1000円札が合計でN枚あって、合計金額がY円であった。このような条件を満たす各金額の札の枚数の組を1つ求める問題です。
本来、各お札についてループを行うところを、for文を工夫し、2つのお札のループだけで解くことにより計算量を削減することが出来ます。

```c#
        public void Solve(ConsoleInput cin)
        {
            var N = cin.ReadInt;
            var Y = cin.ReadInt;
            for (int i = 0; i <= N; ++i)
            {
                for (int j = 0; j <= N - i; ++j)
                {
                    var k = N - i - j;
                    var sum = 10000 * i + 5000 * j + 1000 * k;
                    if (sum == Y)
                    {
                        WriteLine($"{i} {j} {k}");
                        return;
                    }
                }
            }
            WriteLine("-1 -1 -1");
        }
```

## 9問目 ABC049C - 白昼夢 / Daydream
文字列Sが与えられ、始め空の文字列Tの末尾に "dream", "dreamer", "erase", "eraser"を追加する処理を行って、S=Tにできるか判定する問題です。
一見簡単そうに見えますが、先頭から見ていくと、dreamerase....となっているとき、dreamで切っていいのかの判定が大変です。
そこで、後方から見ていくことにより簡単に解くことが出来ます。
今回、文字列の反転を行うために次のクラスを追加し、stringに対する拡張メソッドを定義しています。

```c#
    public static class Extensions
    {
        public static string Reverse(this string sourse)
        {
            char[] chrAry = sourse.ToCharArray();
            Array.Reverse(chrAry);
            return new string(chrAry);
        }
    }
```
```c#
        public void Solve(ConsoleInput cin)
        {
            var S = cin.Read.Reverse();
            // 問題文にある文字列を逆にしたもの
            var words = new string[] { "maerd", "remaerd", "esare", "resare" };
            var flag = true;
            for (int i = 0; i < S.Length;)
            {
                var flag2 = false;
                foreach (var x in words)
                    if (S.Length - i < x.Length) continue;
                    else if (S.Substring(i, x.Length) == x) { flag2 = true; i += x.Length; }
                if (!flag2) { flag = false; break; }
            }
            if (flag) WriteLine("YES");
            else WriteLine("NO");
        }
```

## 10問目 ABC086C - Traveling
時刻0のとき、平面上の(0, 0)にいます。平面上のN箇所の点を、ある時刻に移動できるかという問題です(雑)。
同じ点にとどまることは出来ませんが、目的の点→隣に移動する→目的の点というような移動は許されています。
また、移動時間より移動距離(二点間のマンハッタン距離)が大きければ移動できません。

```c#
        public void Solve(ConsoleInput cin)
        {
            var N = cin.ReadInt;
            // 初期状態をt[0], x[0], y[0]とすることで便利になります
            var t = new int[N + 1];
            var x = new int[N + 1];
            var y = new int[N + 1];
            y[0] = x[0] = y[0] = 0;
            for (int i = 1; i <= N; ++i)
            {
                t[i] = cin.ReadInt;
                x[i] = cin.ReadInt;
                y[i] = cin.ReadInt;
            }

            var flag = true;
            for (int i = 0; i < N; ++i)
            {
                var time = t[i + 1] - t[i];
                var dist = Abs(x[i + 1] - x[i]) + Abs(y[i + 1] - y[i]);
                if (time < dist) flag = false;
                if (Abs(time - dist) % 2 != 0) flag = false;
            }

            if (flag) WriteLine("Yes");
            else WriteLine("No");
        }
```

# さいごに
C#は、C++に実行速度等劣るものの、LINQなどSequenceに対する処理が書きやすく、またVisual Studioを始めとする強力な開発環境があることからオススメします！

時間があるときに、類題も解きたいです。