AtCoder Beginners Selection 10題をPythonで解くぞ!!!

#はじめに
フロントサイドのエンジニアとして活動していたのですが，最近になってPythonを勉強し始め，競技プログラミングに興味を持ち始めました．
そこで今回は[AtCoder](https://atcoder.jp/)における[AtCoder Beginners Selection](https://atcoder.jp/contests/abs)の10題全問をPythonを使って解きたいと思います！
私はPythonに関しては初心者ですので非難はご容赦頂けますと幸いです．（アドバイスや指摘は大歓迎します．）

#前提として
各問題文の掲載は省略させていただきます．
今後，各問題毎に丁寧に解説するかもしれませんので，その際は問題文も掲載させていただきます．
また，AtCoderでは各問題で様々な入力方法が指定されます．
これが初心者にとっては少し厄介です．
ですが，今回の記事ではアルゴリズムに焦点を当てていますので入力方法については[こちらの記事](https://qiita.com/katsuofukuoka0225/items/7a542f995cb4c7a56284)を参照くださいませ．
それでは早速解いていきましょう！！

#PracticeA-Welcome to AtCoder
最初の問題です．
この問題では入力する値の制約も定められていますが，コード内に陽にそれを示すような条件文は挿入しなくて良さそうです．
今回の問題では無駄な制約文を書いていますが，実際には制約の範囲でコンピュータが入力しますよってことみたいなので，無視して大丈夫でした．
一応，制約を含めた両方のコードを貼っておきます．
これが最低限の（満点をもらえる）コード

```python:practiceA.py
a = int(input(""))
b,c = map(int, input().split())
s = input("")

print(a+b+c, s)
```

これが制約をつけたコード

```python:practiceA_ver2.py
a = int(input(""))
b,c = map(int, input().split())
s = input("")

if 1 <= a <= 1000 and 1 <= b <= 1000 and 1 <= c <= 1000 :
    print(a+b+c, s)
else:
    print("a,b,c should be input between 1 and 1000")
```


#ABC086A-Product
シカのAtCoDeerくんは・・・から始まるユーモアを含んだ問題です．
奇数と偶数は言わずもがな2で割って余りが出るか否かで判定可能です．
自身がC言語を勉強した際に頻繁に出現した条件です．
コードの書き方的にも一問目の方が難しい気がします．

```python:ABC086A.py
a,b = map(int, input().split())
result = a * b

if(result % 2 == 0):
    print("Even")
else:
    print("Odd")
```

#ABC081A-Placing Marbles
簡単に言うと入力した3つの値の内，1がいくつあるかをカウントする問題です．
競技プログラミングでは問題文から意図を汲み取り，抽象的に何が行われているのかを考えることが重要そうですね．
小難しい書き方をしている文を良く噛み砕きましょう．

```python:ABC081A.py
s1,s2,s3 = map(int, input())
count = 0

if s1==1:
    count += 1
if s2==1:
    count += 1
if s3==1:
    count += 1

print(count)
```

#ABC081B-Shift only
この問題からふと関数を使いたいと思い，コードの書き方を変えました．
関数を定義してからコードに直接呼び出し文を書いています．
また，入力された一連の値A1~ANをリスト化してnum_listに代入しており，各要素を取り出して2で割理きれるかを判定していきます．
もし，2で割り切れるなら2で割った値を各要素に再代入していきます．
num_list全ての要素が2で割り切れるとプラス1カウントされます．
それを2で割り切れない要素にヒットするまで繰り返します．

```python:ABC081B.py
n = int(input())
num_list = list(map(int, input().split()))

countor = 0

def count(num_list):
    count = 0
    count2 = 0

    for num in num_list:
        if(num % 2 == 0):
            num_list[count2] = int(num / 2)
            count2 +=1
            if(count2 == n):
                return True
        else:
            return False

while count(num_list) != False:
    countor += 1

print(countor)
```
上記のようなコードになりました．
が，ここまで記事を書いていて思いましたが一題一題，もう少し複数の書き方で書くなど丁寧に解説する必要があるなと感じました．
追って記事を作成しようと思います，すみません．

#ABC087B-Coins
この問題をみて初めて，手が止まりました．
これまでは，問題をみ終わったタイミングでコードを書き始めていたのですが．
流石は配点200．
これ以降は，アルゴリズムを考える時間>コードを書く時間になっております．

```python:ABC087B.py
A = int(input())
B = int(input())
C = int(input())
X = int(input())

def cal(A,B,C,X):
    a = 0
    b = 0
    c = 0
    count = 0

    while a <= A:
        while b <= B:
            while c <=C:
                if (500 * a) + (100 * b) + (50 * c) == X:
                    count += 1
                c += 1
            b += 1
            c = 0
        a += 1
        b = 0

    return count

result = cal(A,B,C,X)
print(result)
```
普通に総当たりで試してみました．
while文の入れ子構造が激しいですね．
A,B,C = (0,0,0),(0,0,1),(0,0,2)~(1,2,1),(1,2,2)...のように全てで正誤を判定しています．
計算量多そうな気がしますが，数の定義域（制約）の中では素早く動いてくれます．

#ABC083B-Some Sums
初心者の私には一度読んだだけでは意味が理解できない問題でした．
美味しいと言ったら過言という気がしないでもない訳ではない的な文章．
とはいえ頑張るしかない．
1~Nの整数の内，ある条件に当てはまる物の総和を求めよということですね．
条件というのが各桁の値を足した値（15であれば1+5=6）が任意の範囲に含まれるか否か．
1桁の場合とそれ以上の桁の場合で条件分岐できそうです．

```python:ABC083B.py
N,A,B = map(int, input().split())

def cal(N,A,B):
    result = 0
    total = 0
    num = 0

    while num <= N:
        length = len(str(num))
        if length = 1:
            if A <= num and num <= B:
                result += num
        else:
            count = -1
            while count >= length * -1:
                total += int(str(num)[count])
                count -= 1
            if A <= total and total <= B:
                result += num
            total = 0
        num += 1

    return result

result = cal(N,A,B)
print(result)
```
ここで全くもって取得方法がわからなかったのが各桁の数の取得方法です．
いろいろ調べた末

```python
str(num[-1])
```

が一の位を表すそうです．
なぜインデックスがマイナスなのかというのは，リストは前から0,1,2,3とインデックスがふられているのですが，後ろから順にも-1,-2,-3と同様にインデックスが用意されているからです．
そのような理由から理由からコードではcount=-1から始めています．
コード上では完全にマジックナンバーになりますね，すみません．
そもそも一桁の数字の判定とを分ける必要があるのかという疑問が生じましたので，計算量の比較も踏まえて今後より見やすいコードを記事で投稿できたらと思います．

#ABC088B-Card Game for Two
この世で一番面白くないゲームの問題です．
各プレイヤーのスコアとターンを関数内で変数として定義しています．
Aliceから先にカードを取り，次にBobがカードを取ります．
すなわちAliceは1,3,5,7...ターン目にカードを取る．
つまり，ターンが奇数の時は場の最大のカードをAliceが取り，偶数の時は場の最大のカードをBobが取るということですね．

```python:ABC088B.py
N = int(input())
a = list(map(int, input().split()))

def score(N,a):
    A_score = 0
    B_score = 0
    turn = 1

    while turn <= N:
        index = 0
        max_score = 0

        while index < len(a):
            if max_score < a[index]:
                max_score = a[index]
            index += 1
        a.remove(max_score)

        if turn % 2 != 0:
            A_score += max_score
        else:
            B_score += max_score

        turn += 1
    return A_score - B_score

result = score(N,a)
print(result)
```
場の最大のカードの判定方法はN枚目のカードとN+1枚目のカードと比較し，大きい方を保存というのを繰り返す方法です．
この判定方法はいくつもある思います．
今後余裕があるときにクイックソートやバブルソートなどの探索アルゴリズムをPythonで書こうかなと思いましたね．

#ABC085B-Kagami Mochi
最初こそ試行錯誤していたものの，冷静に考えるとめちゃくちゃ簡単でした．
入力された値のうち，重なりを排除した残りの数，つまり入力した値の種類が答えになります．
種類が違うということは大きさが違う，大きさが違うということはもちを重ねることができるということですもんね．

```python:ABC085B.py
N = int(input())
d = [int(input()) for i in range(N)]

def mochi(d):
    d = list(set(d))
    return len(d)

result = mochi(d)
print(result)
```
正直，一番難しいのは入力欄の出力の仕方でしたね．
ちなみにset()で配列内の重複を消せます．

#ABC085C-Otoshidama
これが全ての問題で一番時間がかかりました．
先に言っておきますが，下記の2つのコードの内最初の物はAtCoder上で不正解判定になります．
アルゴリズムとしては合っていますが，計算時間が規定の2sを超えるケースが発生します．
ここからは計算量も視野に入れないといけません．（本当は常に意識しないといけない）

一つ目のコードでは無我夢中で変数x，y，zを使って総当たり判定をしています．

```python:ABC085.py
N,Y = map(int, input().split())

def judge(N,Y):
    x = 0
    y = 0
    z = 0
    result = ""

    while x <= N:
        if result == "":
            y = 0
            while y <= N:
                if result == "":
                    z = 0
                    while z <= N:
                        if N == (x + y + z) and result == "":
                            if (Y - (10000 * x + 5000 * y + 1000 * z)) == 0:
                                result = "Truth"
                                break
                        z += 1
                    if result == "":
                        y += 1
                else :
                    break
            if result == "":
                x += 1
        else :
            break

    if result != "Truth":
        x = -1
        y = -1
        z = -1

    return x,y,z

x,y,z = judge(N,Y)
print(x,y,z)
```
とここまでが，時間超過を叩き出したうんコードであります．
どうしたものかと思いましたが，変数を減らせば計算時間が減るよねってことで．zにz=N-x-yを代入してzを定数にしたものがこちら．

```python:ABC085_ver2.py
N,Y = map(int, input().split())

def judge(N,Y):
    x = 0
    result = ""

    while x <= N:
        if result == "":
            y = 0
            while y <= N:
                z = N - (x + y)
                if result == "" and z >= 0:
                    total = Y - (10000 * x + 5000 * y + 1000 * z)
                    if total == 0 :
                        result = "Truth"
                        break
                    y += 1
                else :
                    break

            if result == "":
                x += 1
        else :
            z = N - (x + y)
            break

    if result != "Truth":
        x = -1
        y = -1
        z = -1

    return x,y,z

x,y,z = judge(N,Y)
print(x,y,z)
```
無事に満点を叩き出しました．
ちなみに最後に各変数に-1を代入してからreturnしてるのは問題文で指定しているからです．

#ABC049C-白昼夢
白昼夢：真昼に夢を見ているような、非現実的な空想 らしいです．
なぜこの問題だけ漢字なのでしょうか．
非常に良くできた問題で，解いてて一番楽しかったです．
入力した文字の最初の文字がdream,dreamer,erase,eraser,それ以外のどれで始まるのかで場合分けしました．
ここで気をつけて欲しいのがif文の定義順序です．
可能性が多分にあるものから順に狭めていかなければ面倒なことになりそうです．
dreamerから始まる場合は文字通りdreamerの場合とdream + (erase or erasear)の頭文字の可能性がありますよね，そのように場合分けします．
どの単語から始まるのか確定した段階でリストから単語を削除し，また条件に当てはめて判定します．
単語がリストから削除された時点でリストが空であれば，その文字列は問題の意にそぐうと言うことです．

```python:ABC049C.py
S = list(input())

def judge(S):
    while len(S) >= 5:

        if S[0:7] == ["d","r","e","a","m","e","r"]:
            if len(S) == 7 or (len(S) >=8 and S[7] != "a"):
                del S[0:7]

            else :
                del S[0:5]

        elif S[0:5] == ["d","r","e","a","m"]:
            del S[0:5]

        elif S[0:6] == ["e","r","a","s","e","r"]:
            del S[0:6]

        elif S[0:5] == ["e","r","a","s","e"]:
            del S[0:5]

        else :
            break

    if len(S) == 0:
        print("YES")
    else :
        print("NO")

judge(S)
```

#ABC086C-Traveling
ついに最後の問題です．
再び登場，AtCoDeerくん．
しか（鹿）も二次元平面上で旅行しようとしてます．
なんやねんそれ．
急に数学チックな問題，座標問題ですね．
ポイントはどのような条件の時にその座標に立って居られる可能性があるかということです．
1秒でx座標かy座標のどちらかで1進む（戻る）ことしか（鹿）できないので，x座標とy座標の絶対値の合計が経過秒tより大きかったら不可能な訳です．（ex 3秒時点で(2,3)には到達できない（2+3=5なので））
逆に言えば,x+y>=tが成り立つなら実現可能．
また，経過秒数が遥かに大きくても(x,y)=(0,0)にいることだって可能な訳です．
同じ座標軸上で行って戻ってをワンセットすれば動き的には0な訳です．
つまり(t-(x+y))%2==0でも問題ないと言う訳です．（一気に飛ばしすぎました？？）

```python:ABC086C.py
N = int(input())
points = [map(int, input().split()) for i in range(N)]

def judge(N,points):
    t = 0
    x = 0
    y = 0
    index = 0
    result = "Yes"

    while index < N:
        point_info = list(points[index])
        t = point_info[0] - t
        x = point_info[1] - x
        y = point_info[2] - y

        if x < 0:
            x *= -1
        if y < 0:
            y *= -1

        if t >= (x + y) and (t - (x + y)) % 2 == 0 :
            pass
        else :
            result = "No"
            break

        index += 1

    print(result)

judge(N,points)
```
最終的な返り値の初期値を"Yes"にしておき，不可能なプランが発生した時点で"No"を代入するようなプログラムを書いております．


#最後に
ここまで読んでみてくださった皆様，ありがとうございます．
上級者の方にとっては非効率で冗長部分が多いコードだったかもしれません．（アドバイスやご指摘お待ちしてます！）
今回は自分より初心者の方々の力になれればと思いこの記事を書かせて頂きました．
僕自身も勉強を始めたばかりなので，これから一緒に頑張っていきましょう！
それでは！