AtCoderをC#で始めてみたよ　-AtCoder Beginners Selection-

こんにちはYamayouです．早稲田の機械専攻とかいうところに生息しております．
はてなブログでコードとかのブログを書こうと思ったけど絶対Qiitaの方がいいじゃんと思ってこちらにしました．いちおう[はてなブログの方](https://yamayounoblog.hatenablog.com/)も載せとく



# 0．はじめに

競プロに興味あったのではじめてみました．初心者です．[AtCoder Beginners Selection](https://atcoder.jp/contests/abs)から始めてみようと思います．研究でちょっとC#を使っていたので，C#で進めていきます．備忘録って感じで残していくので気楽に見ていってね．




## 第1問 [ABC 086 A - Product](https://atcoder.jp/contests/abs/tasks/abc086_a)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3817552/07e28da0-d350-1b14-63db-d45092ef0900.png)

### コメント

掛け算して2で割ったあまりで条件分岐でいいのかな．2つの数字それぞれの偶奇が分かれば掛け算はしなくても判断できるけどまあこのくらいの計算量ならかけちゃった方がいいっぽいな
```C#
using System;
class Program
{
    static void Main(String[] args){
        string[] input = Console.ReadLine().Split(' ');
        int a = int.Parse(input[0]);
        int b = int.Parse(input[1]);
        if(a*b%2 == 0){
            Console.WriteLine("Even");
        }else{
            Console.WriteLine("Odd");
        }
    }
}
```

## 第2問 [ABC 081 A - Placing Marbles](https://atcoder.jp/contests/abs/tasks/abc081_a)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3817552/3b6c0af5-7eed-94e4-2f8c-419a0e5a22d8.png)

### コメント

要は，0と1からなる3桁の数(例:101)が与えられるから1が何個あるか数えてねって感じだな．なんかA問題はfor使わなくても解けるっぽいけど最初に思い付いたfor使うことにするわ．とりあえず一の位だけ判定します．10で割った余りが1かどうかを判定して，1だったらansを＋１していく感じでやるか．

　次はa=a/10を挟んで数字を右にずらすとさっきまで十の位にあった数が一の位にあるのでこれを繰り返せばいいかな．
```C#
using System;
class Program
{
    static void Main(String[] args){
        int a = int.Parse(Console.ReadLine());
        int ans = 0;

        for(int i = 0;i<3;i++){
            if(a%10==1){
                ans++;
            }
            a = a/10;
        }  
        
        Console.WriteLine(ans);
    }
}
```

for使わない方も一応書いとく，こっちの方が無難か．
```C#
using System;
class project1
{
    static void Main(String[] args)
    {
        string input = Console.ReadLine();
        int ans = 0;

        if (input[0] == '1') ans++;
        if (input[1] == '1') ans++;
        if (input[2] == '1') ans++;

        Console.WriteLine(ans);
    }  
}
```




## 第3問 [ABC 081 B - Shift Only](https://atcoder.jp/contests/abs/tasks/abc081_b)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3817552/0feb4375-a6fd-e27d-8d30-6276a89f8cca.png)




### コメント

「すぬけ君」．．．？まあいいか．．．これはシンプルに全部2で割っていけばいいのかな，なんかもっといい方法ある気がするけど思いつかないのでごり押ししていく．途中で2で割った余りが1になったらflagをtrueにしてwhileから抜け出す感じで
```C#
using System;
using System.Linq;
class project1
{
    static int N = 0;
    static int ans = 0;
    static int[] A = new int[210]; //一応200より多めにとっておく

    static void Main(String[] args)
    {
        N = int.Parse(Console.ReadLine());
        A = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

        while (true)
        {
            bool flag = false;
            for(int i = 0; i < N; i++)
            {
                if (A[i] % 2 == 1) flag = true;
                A[i] = A[i] / 2;
            }

            if (flag == true) break;
            ans++;
        }

        Console.WriteLine(ans);
    }  
}
```

## 第4問 [ABC 087 B - Coins](https://atcoder.jp/contests/abs/tasks/abc087_b)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3817552/503a5576-fee4-62ad-f2f6-b165d6ff51ca.png)


### コメント

3重でfor文回して全部探索するだけ．．．？なんかもっといい方法ないのかな
```C#
using System;
class Program
{
    static int A,B,C,X,ans;

    static void Main(String[] args)
    {
        A = int.Parse(Console.ReadLine());
        B = int.Parse(Console.ReadLine());
        C = int.Parse(Console.ReadLine());
        X = int.Parse(Console.ReadLine());


        for(int i = 0; i <= A; i++)
        {
            for(int j = 0; j <= B; j++)
            {
                for(int k = 0; k <= C; k++)
                {
                    int sum = 500 * i + 100 * j + 50 * k;
                    if (sum == X) ans++;
                }
            }
        }

        Console.WriteLine(ans);

    }
}
```

## 第5問 [ABC 083 B - Some Sums](https://atcoder.jp/contests/abs/tasks/abc083_b)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3817552/41f88ccd-eef5-f019-e7e9-84021041ef61.png)


### コメント

各位の和を出すプログラムを書いてねってことね．CalculateSumOfDigits関数の中に処理を書いていく．totalにnumを10で割ったあまり（一の位）を代入して，numを10で割って一の位を消して各桁を右にずらす．これをnumが0になるまで繰り返したらいいのかな．
```C#
using System;
class Program
{
    static int N, A, B, ans;

    static int CalculateSumOfDigits(int num)
    {
        int total = 0;
        while (num > 0)
        {
            total += (num % 10);
            num /= 10;
        }
        return total;
    }

    static void Main(String[] args)
    {
        string[] input = Console.ReadLine().Split(' ');
        N = int.Parse(input[0]);
        A = int.Parse(input[1]);
        B = int.Parse(input[2]);
        ans = 0;

        for (int i = 1; i <= N; i++)
        {
            int total = CalculateSumOfDigits(i);
            if (A <= total & total <= B) ans += i;
        }

        Console.WriteLine(ans);

    }
}
```

## 第6問 [ABC 088 B - Card Game for Two](https://atcoder.jp/contests/abs/tasks/abc088_b)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3817552/cff65f6f-6eab-bf6a-7674-1a0e5efe8e60.png)

### コメント

ソートしてでかい順に，AさんとBさんにもっていってもらえばよさそう．ソートはArray.Sortを使ったけど昇順になっちゃうのでReverseしとく．
```C#
using System;
using System.Linq;
class Program
{
    static int N = 0;
    static int[] A = new int[110]; //一応100より多めにとっておく
    static int scoreA = 0;
    static int scoreB = 0;

    static void Main(String[] args)
    {
        N = int.Parse(Console.ReadLine());
        A = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

        Array.Sort(A);
        Array.Reverse(A);

        for(int i = 0; i < N; i++)
        {
            if (i % 2 == 0) scoreA += A[i];
            if (i % 2 == 1) scoreB += A[i];
        }

        Console.WriteLine(scoreA - scoreB);
        
    }
}
```

## 第7問 [ABC 085 B -Kagami Mochi](https://atcoder.jp/contests/abs/tasks/abc085_b)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3817552/72360241-8184-f3ab-ce5e-0647884b682e.png)

### コメント

大きい順に並べて前から数の要素数だけカウントしていけばいいかな．
```C#
using System;
class Program
{
    static int N, ans;
    static int[] d = new int[110];

    static void Main(String[] args)
    {
        N = int.Parse(Console.ReadLine());
        for(int i = 0; i < N; i++)
        {
            d[i] = int.Parse(Console.ReadLine());
        }

        Array.Sort(d);
        Array.Reverse(d);

        int nowD = d[0];
        int preD = 110; //少し大きめの数を入れとく

        for(int i = 0; i < N; i++)
        {
            nowD = d[i];
            if (nowD != preD) ans++;
            preD = nowD;
        }

        Console.WriteLine(ans);

    }
}
```

これでもうまくいったけど世の中にはバケット法なるものがあるらしい．．．書き直してみるか
```C#
using System;
class Program
{
    static int N, ans;
    static int[] d = new int[110];

    static void Main(String[] args)
    {
        N = int.Parse(Console.ReadLine());
        for(int i = 0; i < N; i++) d[i] = int.Parse(Console.ReadLine());
        ans = 0;

        int[] num = new int[110];
        for (int i = 0; i < N; i++) num[i] = 0;

        for (int i = 0; i < N; i++) num[d[i]]++;

        for(int i = 1; i <= 100; i++)
        {
            if (num[i] > 0) ans++;
        }

        Console.WriteLine(ans);

    }
}
```

Distinct().ToArray()を使うと重複した要素をすべて消してくれるらしい，これを使うと行数はもっと短くなるな
```C#
using System;
using System.Linq;
class Program
{
    static int N;
    static int[] d = new int[110];

    static void Main(String[] args)
    {
        N = int.Parse(Console.ReadLine());
        for(int i = 0; i < N; i++) d[i] = int.Parse(Console.ReadLine());
        int[] value = d.Distinct().ToArray();
        Console.WriteLine(value.Length-1);

    }
}
```


## 第8問 [ABC 085 C -Otoshidama](https://atcoder.jp/contests/abs/tasks/abc085_c)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3817552/01e460a5-ab9d-fee6-11e4-e9840c2354bc.png)


### コメント

初めてのC問題．お札をN枚使ってちょうどY円となるような組み合わせを見つける問題．10000円札をi枚，5000円をj枚つかったとすれば1000円札は自然とN-i-j枚となるので２回for文を回したらいけそうだな．
```C#
using System;
class Program
{
    static void Main(String[] args)
    {
        string[] input = Console.ReadLine().Split(' ');
        int N = int.Parse(input[0]);
        int Y = int.Parse(input[1]);

        int[] ans ={ -1, -1, -1 };

        for(int i = 0; i <= N; i++)
        {
            for(int j = 0; j <= N - i; j++)
            {
                int sum = 10000 * i + 5000 * j + 1000 * (N - i - j);
                if(sum == Y)
                {
                    ans[0] = i;
                    ans[1] = j;
                    ans[2] = N - i - j;
                }
            }
        }

        Console.WriteLine(ans[0] + " " + ans[1] + " " + ans[2]);

    }
}
```
## 第9問 [ABC 049 C -Daydream](https://atcoder.jp/contests/abs/tasks/arc065_a)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3817552/b83796d6-cba4-818c-1248-7fddd8cf013d.png)

### コメント

んーー難しい．．．結構悩んだけど分からなかったので解答見ながら微調整．dreamer含む4つの単語を後ろから見れば被ることがないっていうのは目から鱗！こういう発想も大事なのね．．．
```C#
using System;
using System.Linq;
class Program
{
    static string[] divide = {"dreamer","dream","erase","eraser"};

    static void Main(String[] args)
    {
        string S = Console.ReadLine();
        string revS = new string(S.Reverse().ToArray());
        string[] revDivide = new string[4];
        for (int i = 0; i < 4; i++) revDivide[i] = new string(divide[i].Reverse().ToArray());
        bool check1 = true;

        for(int i = 0; i < revS.Length;)
        {
            bool check2 = false;
            for(int j = 0; j < 4; j++)
            {
                string d = revDivide[j];
                if (i+d.Length<=revS.Length)
                {
                    if(revS.Substring(i, d.Length) == d)
                    {
                        i += d.Length;
                        check2 = true;
                    }
                }
            }

            if (!check2)
            {
                check1 = false;
                break;
            }

        }

        if (check1) Console.WriteLine("YES");
        else Console.WriteLine("NO");

    }
}
```


## 第10問 [ABC 086C - Traveling](https://atcoder.jp/contests/abs/tasks/arc089_a)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3817552/cc4e27de-3c60-3be5-997d-59e5f4ef6294.png)

### コメント

最後の問題．これは結構簡単だった．時刻tiからt(i+1)になったときに実行可能かどうかは次の2点を満たせばよい．

①時間の間隔＞移動量

②時間の間隔―移動量が偶数

①移動量は（Xの差）＋（Yの差）で出していて，最低でもこの数より時間の間隔の方が大きくないと移動できない．

②最速で次の予定地についた時あとはうろちょろして時間稼ぎをすればよい．そのとき偶数であれば行って戻ってこれるので偶数判定を行う．
```C#
using System;
using System.Linq;
class Program
{
    static int N;
    static int[] nowPos = new int[3];

    static void Main(String[] args)
    {
        N = int.Parse(Console.ReadLine());
        int[] prePos = new int[3] {0,0,0};
        bool check = true;

        for (int i = 0; i < N; i++)
        {
            nowPos = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            int distance = Math.Abs(nowPos[1] - prePos[1]) + Math.Abs(nowPos[2] - prePos[2]);
            int interval = nowPos[0] - prePos[0];
            if (interval < distance | (interval - distance) % 2 == 1)
            {
                check = false;
                break;
            }
            prePos = nowPos;
        }

        if (check) Console.WriteLine("Yes");
        else Console.Write("No");

    }
}
```






# 最後に

とりあえずBeginners Selectionが終わったのでよかった．早速コンテスト的なのに参加していきたい．