AtCoderに登録したら解くべき精選過去問10問の類題をPythonで解く

題通りです。<del>解いているのは類題なのでご注意下さい。</del>
精選問題もついでに解いています。解答はすべてACになることを確認しています。
<a href="https://qiita.com/drken/items/fd4e5e3630d0f5859067"_blank>AtCoderに登録したら解くべき精選過去問10問</a>

精選問題10問の解答は下記記事をご参照下さい。
<a href="https://qiita.com/KoyanagiHitoshi/items/c5e82841b8d0f750851d"_blank>AtCoderに登録したら解くべき精選過去問10問をPythonで解いてみた</a>

解答のポイントも自分なりにですが記載しています。変な書き方や間違いに気づかれた方はご指摘いただけると嬉しいです。

毎日少しずつ解いているので随時更新します。(2020/02/12)


# 第 1 問: [ABC 086 A - Product](https://atcoder.jp/contests/abc086/tasks/abc086_a)
```python:Product.py
a,b = map(int,input().split())
if a*b%2 == 0:
  print("Even")
else:
  print("Odd")
```
## 第1問類題

<a href="https://atcoder.jp/contests/abc064/tasks/abc064_a"_blank>ABC 064 A - RGB Cards</a>

```python:RGBCards.py
r,g,b = map(int,input().split())
 
if (100*r + 10*g + b)%4 == 0:
    print("YES")
else:
    print("NO")
```

<a href="https://atcoder.jp/contests/abc088/tasks/abc088_a"_blank>ABC 088 A - Infinite Coins</a>

```python:InfiniteCoins.py
N = int(input())
A = int(input())
 
if (N%500) <= A:
    print("Yes")
else:
    print("No")
```

<a href="https://atcoder.jp/contests/abc082/tasks/abc082_a"_blank>ABC 082 A - Round Up the Mean</a>

```python:RoundUptheMean.py
a,b = map(float,input().split())

if (a+b)%2 == 1:
    print(int((a+b)/2)+1)
else:
    print(int((a+b)/2))
```




# 第 2 問: [ABC 081 A - Placing Marbles](https://atcoder.jp/contests/abc081/tasks/abc081_a)
```python:PlacingMarbles.py
S = input()
count = 0
for s in S:
  if s == "0":
    count += 1
print(count)
```
## 第2問 類題

・[ABC 095 A - Something on It](https://atcoder.jp/contests/abc095/tasks/abc095_a)

```python:PlacingMarbles.py
a,b = map(float,input().split())

if (a+b)%2 == 1:
    print(int((a+b)/2)+1)
else:
    print(int((a+b)/2))
```

・[ABC 085 A - Already 2018](https://atcoder.jp/contests/abc085/tasks/abc085_a)

```python:Already.py
s = input()
 
print(s.replace("2017","2018"))
```

・[ABC 069 B - i18n](https://atcoder.jp/contests/abc069/tasks/abc069_b)

```python:i18n.py
s = input()
 
print(s[0] + str(len(s)-2) + s[-1])
```

・[ABC 082 B - Two Anagrams](https://atcoder.jp/contests/abc082/tasks/abc082_b)

```python:TwoAnagrams.py
s = sorted(input())
t = sorted(input(),reverse = True)
 
if s < t:
    print("Yes")
else:
    print("No")
```



# 第 3 問: [ABC 081 B - Shift Only](https://atcoder.jp/contests/abc081/tasks/abc081_b)
```python:ShiftOnly.py
N = int(input())
A = list(map(int,input().split()))
 
flag = True
count = 0
while(flag):
  for i in range(N):
    if A[i]%2:
      flag = False
      break
    else:
      A[i] /= 2
  if flag:
    count += 1
print(count)
```

## 第3問類題
・[ABC 068 B - Break Number](https://atcoder.jp/contests/abc068/tasks/abc068_b)

```python:BreakNumber.py
N = int(input())
 
count = [0 for __ in range(N)]
Nl = [i for i in range(1,N+1)]
for i,n in enumerate(Nl):
    while n%2==0:
        n /= 2
        count[i] += 1
idx = count.index(max(count))
print(Nl[idx])
```

・[ABC 102 B - Maximum Difference](https://atcoder.jp/contests/abc102/tasks/abc102_b)

```python:MaximumDifference.py
N = int(input())
A = list(map(int,input().split()))
 
maxi = A[0]
mini = A[0]
for i in range(N):
    if maxi < A[i]:
        maxi = A[i]
    if mini > A[i]:
        mini = A[i]
print(maxi-mini)
```

・[ABC 113 B - Palace](https://atcoder.jp/contests/abc113/tasks/abc113_b)

```python:Palace.py
N = int(input())
T,A = map(int,input().split())
H = list(map(int,input().split()))
 
sub = [0 for i in range(N)] 
for i in range(N):
    sub[i] = abs(A-(T - 0.006*H[i]))    
print(sub.index(min(sub))+1)
```

・[ABC 072 B - OddString](https://atcoder.jp/contests/abc072/tasks/abc072_b)

```python:OddString.py
s = input()
 
s_odd = [s[i] for i in range(len(s)) if i%2 == 0]
print("".join(s_odd))
```

・[ABC 053 B - A to Z String](https://atcoder.jp/contests/abc053/tasks/abc053_b)

```python:AtoZString.py
s = input()
 
start = []
end = []
for i in range(len(s)):
    if s[i] == "A":
        start.append(i)
    if s[-(i+1)] =="Z":
        end.append(len(s)-i)
print(end[0]-start[0])
```

・[ABC 095 B - Bitter Alchemy](https://atcoder.jp/contests/abc095/tasks/abc095_b)

```python:BitterAlchemy.py
N,X = map(int,input().split())
M = [int(input()) for i in range(N)]
 
counter = N
X -= sum(M)
counter += X//min(M) 
print(counter)
```





# 第 4 問: [ABC 087 B - Coins](https://atcoder.jp/contests/abc087/tasks/abc087_b)

```python:Coins.py
A = int(input())
B = int(input())
C = int(input())
X = int(input())
 
counter = 0
 
for i in range(A+1):
    for j in range(B+1):
        for k in range(C+1):
            if (i*500+j*100+k*50) == X:
                counter += 1
 
print(counter)
```

## 第4問類題
```python:CakesandDonuts.py
N = int(input())

no_flag = True

for i in range((N//4)+1):
    if no_flag == False:
        break
    for j in range((N//7)+1):
        if no_flag == False:
            break
        if (4*i+7*j) == N:
            print("Yes")
            no_flag = False
            
if no_flag == True:
    print("No")
```
・[ABC 105 B - Cakes and Donuts](https://atcoder.jp/contests/abc105/tasks/abc105_b)

```python:CakesandDonuts.py
N = int(input())

no_flag = True

for i in range((N//4)+1):
    if no_flag == False:
        break
    for j in range((N//7)+1):
        if no_flag == False:
            break
        if (4*i+7*j) == N:
            print("Yes")
            no_flag = False
            
if no_flag == True:
    print("No")
```

・[ARC 004 A - 2点間距離の最大値](https://atcoder.jp/contests/arc004/tasks/arc004_1)

```python:NitenKyori.py
import math
N = int(input())
XY = [list(map(int,input().split())) for i in range(N)]
 
d = []
for a in XY:
    for b in XY:
        d.append(math.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2))
 
print(max(d))
```

・[ABC 051 B - Sum of Three Integers](https://atcoder.jp/contests/abc051/tasks/abc051_b)

```python:SumofThreeIntegers.py
K,S = map(int,input().split())

count = 0
for x in range(K+1):
    for y in range(K+1):
        if 0 <= S-x-y <=K:
            count += 1
print(count)
```
【解説】forを使ったx,y,zの全探索だとTLEになるので、「z = S-x-y」と「0<= z <= K」を利用してzのloopを削減します.





# 第 5 問: [ABC 083 B - Some Sums](https://atcoder.jp/contests/abc083/tasks/abc083_b)

```python:SomeSums.py

```

・[ABC 080 B - Harshad Number](https://atcoder.jp/contests/abc080/tasks/abc080_b)

```python:HarshadNumber.py
N = int(input())

l = []
num = N
for i in range(9):
    l.append(int(num%10))
    num /= 10
if N%(sum(l)) == 0:
    print("Yes")
else:
    print("No")
```

【解説】1<= N <=10^8、10^8は9桁なので、「Nを10で割ったあまりを求めてリストに追加」⇒「Nを10で割る」の操作を最大9回繰り返せば全ての桁の数字を取り出せます。

・[ABC 090 B - Palindromic Numbers](https://atcoder.jp/contests/abc090/tasks/abc090_b)

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

count = 0
for i in range(A,B+1):
    i = str(i)
    if (i[0]==i[-1])and(i[1]==i[-2]):
        count += 1
print(count)
```
【解説】5桁しかないので全幅探索。5桁をabcdeとすると、「a = e」かつ「b = d」を満たす場合カウントアップします。


・[AGC 025 A - Digits Sum](https://atcoder.jp/contests/agc025/tasks/agc025_a)

```python:DigitsSum.py
N = int(input())

if N%10 == 0:
    print(10)
else:
    l = []
    for i in range(6):
        l.append(int(N%10))
        N /= 10
    print(sum(l))
```
【解説】例としてN = 23の場合を考えると、(A,B)の組み合わせと和は以下になります。
(1,22) ⇒　5
(2,21) ⇒　5
(3,20) ⇒　5
(4,19) ⇒　14
(5,18) ⇒　14
(6,17) ⇒　14
(7,16) ⇒　14
(8,15) ⇒　14
(9,14) ⇒　14
(10,13) ⇒　5
(11,12) ⇒　5
ここから各位の和は、A,Bが繰り上がる場合減少、繰り下がる場合増加し、そうでない場合は一定であることがわかります。Nから繰り上がること(例えばN = 999⇒1000になる等)が無いので求める各位の和の最小値は、Nの各位の和そのものとなります(ひっ算をイメージするとわかりやすい)。
ただし、Nが10のべき乗の場合はその限りでなく各位の和の最小値は10になります。
例)N=100のとき、(A,B) = (50,50)が最小

```python:DigitsSum別解.py
N = int(input())

summ = []
for i in range(1,N//2 + 1):
    A = []
    B = []
    k = N-i
    for __ in range(6):
        A.append(int(i%10))
        B.append(int(k%10))
        i /= 10
        k /= 10
    summ.append(sum(A+B))
print(min(summ))
```
【解説】別解はNをiとN-i(1<=i<=N/2)に分割し、各位の和を足し上げる全幅探索です。最初に思い付き、一応ACになるので記載しました。


#第 6 問: [ABC 088 B - Card Game for Two] (https://atcoder.jp/contests/abc088/tasks/abc088_b)
```python:CardGameforTwo.py
N = int(input())
A = list(map(int,input().split()))
 
A.sort(reverse = True)
print(sum(A[0:len(A):2])-sum(A[1:len(A):2]))
```
## 第6問類題

・[ABC 067 B - Snake Toy](https://atcoder.jp/contests/abc067/submit?taskScreenName=abc067_b)

```python:SnakeToy.py
N,K = map(int,input().split())
l = list(map(int,input().split()))
 
l.sort(reverse = True)
print(sum(l[0:K]))
```
【解説】降順でソートして先頭からK番目の要素まで足し上げます。

・[ABC 042 B - Iroha Loves Strings](https://atcoder.jp/contests/abc042/tasks/abc042_b)

```python:IrohaLovesStrings.py
N,L = map(int,input().split())
S = [input() for i in range(N)]
 
S.sort()
print("".join(S))
```
【解説】python組み込みのsort()でリスト内の文字列を辞書順に並べます。最後にjoinで結合します。

・[AGC 027 A - Candy Distribution Again](https://atcoder.jp/contests/agc027/tasks/agc027_a)

```python:CandyDistributionAgain.py
N,x = map(int,input().split())
A = list(map(int,input().split()))
 
if sum(A) < x:
    print(N-1)
else:
    A.sort()
    count = 0
    while(x > 0):
        x -= A[count]
        if x >= 0:
            count += 1
    print(count)
```
【解説】子供が喜ぶお菓子の合計sum(A)が配れるお菓子の数xより大きいか否かで場合分けします。sum(A) < xのとき子供全員にお菓子は配れますが、余りが発生するので誰か一人に余剰を押し付けることになります(=一人は喜ばない)。sum(A) >= xのときは喜ぶお菓子の数が少ない子供から配っていくのが最善です。

・[AGC 012 A - AtCoder Group Contest](https://atcoder.jp/contests/agc012/tasks/agc012_a)

```python:AtCoderGroupContest.py
N = int(input())
A = list(map(int,input().split()))
 
A.sort(reverse = True)
ans = []
for i in range(int(len(A)/3)): # whileは遅い
    ans.append(A[1+2*i])
print(sum(ans))
```
【解説】解答のイメージは下記図のようになります。
![AGC 012 A - AtCoder Group Contest解答イメージ.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/290351/2b2594c3-58b3-1e23-966a-fc941b0f0a3e.jpeg)



# 第 7 問: [ABC 085 B - Kagami Mochi] (https://atcoder.jp/contests/abc085/tasks/abc085_b)

```python:KagamiMochi.py
N = int(input())
D = [int(input()) for i in range(N)]
 
print(len(set(D)))
```


## 第7問類題
・[ABC 071 B - Not Found](https://atcoder.jp/contests/abc071/tasks/abc071_b)

```python:NotFound.py
S = input()
 
S = set(S)
flag = True
alphabet = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
for i in alphabet:
    if i not in S:
        print(i)
        flag = False
        break
if flag:
    print("None")
```


・[ABC 061 B - Counting Roads](https://atcoder.jp/contests/abc061/tasks/abc061_b)

```python:CountingRoads.py
import numpy as np
N,M = map(int,input().split())
ab = [list(map(int,input().split())) for __ in range(M)]
 
ab = np.array(ab).flatten()
for i in range(1,N+1):
    print(len(np.where(ab == i)[0]))
```
【解説】問題を意訳するとai、biの出現回数をカウントするのが目的


・[ABC 047 B - Snuke's Coloring 2](https://atcoder.jp/contests/abc047/tasks/abc047_b)

```python:Snuke'sColoring2.py
W,H,N = map(int,input().split())
XYA = [list(map(int,input().split())) for __ in range(N)]

Xend = W
Yend = H
Xstart = 0
Ystart = 0
for xya in XYA:
    if xya[2] == 1:
        Xstart = max(Xstart,xya[0])
    elif xya[2] == 2:
        Xend = min(Xend,xya[0])
    elif xya[2] == 3:
        Ystart = max(Ystart,xya[1])
    elif xya[2] == 4:
        Yend = min(Yend,xya[1])
if (Xend - Xstart)>0 and (Yend - Ystart)>0:
    print((Xend - Xstart)*(Yend - Ystart))
else:
    print(0)
```

・[ABC 091 B - Two Colors Card Game](https://atcoder.jp/contests/abc091/tasks/abc091_b)

```python:TwoColorsCardGame.py
N = int(input())
S = [input() for __ in range(N)]
M = int(input())
T = [input() for __ in range(M)]

dic_S = {x:0 for x in set(S)}
dic_T = {x:0 for x in set(T)}
ans = list(range(len(set(S))))
for s in S:
    dic_S[s] += 1
for t in T:
    dic_T[t] += 1
for i,key in enumerate(dic_S):
    if key in list(dic_T.keys()):
        ans[i] = dic_S[key]-dic_T[key]
    else:
        ans[i] = dic_S[key]
if max(ans) > 0:
    print(max(ans))
else:
    print(0)
```

・[ABC 081 C - Not so Diverse](https://atcoder.jp/contests/abc081/tasks/arc086_a)

```python:NotsoDiverse.py
N,K = map(int,input().split())
A = list(map(int,input().split()))

Ad = {x:0 for x in set(A)}
if len(set(A)) <= K:
    print(0)
else:
    count = 0
    for a in A:
        Ad[a] += 1
    Ad = sorted(Ad.items(), key=lambda x:x[1])
    for i in range(len(set(A))-K):
        count += Ad[i][1]
    print(count)
```





# 第 8 問: [ABC 085 C - Otoshidama](https://atcoder.jp/contests/abc085/tasks/abc085_c)

```python:Otoshidama.py
N,Y = map(int,input().split())
 
flag = False
for i in range(N+1):
    if flag:
        break
    for j in range(N+1-i):
        if 10000*i + 5000*j + 1000*(N-i-j) == Y:
            l = [i,j,N-i-j]
            flag = True
            break
if flag:
    print(l[0],l[1],l[2])
else:
    print(-1,-1,-1)
```

## 第8問類題

・[ABC 088 C - Takahashi's Information](https://atcoder.jp/contests/abc088/tasks/abc088_c)

```python:TakahashisInformation.py
C = [list(map(int,input().split())) for __ in range(3)]
 
a=[0]*3
b=[0]*3
b[0],b[1],b[2]=C[0]
a[0],a[1],a[2]=0,C[1][0]-b[0],C[2][0]-b[0]
flag = True
for i in range(3):
    if flag == False:
        break
    for j in range(3):
        if C[i][j] != a[i]+b[j]:
            print("No")
            flag = False
            break
if flag == True:
    print("Yes")
```
【解説】高橋君の提示している条件内では、ai,biが不定でも問題ないことがポイントです。つまり、cii = ai+biを満たせばよいので、aiをx増やしたらbiをx減らせばciiは同様に成り立ちます。

つまり、一般化すると
(𝑎1, 𝑎2, 𝑎3, 𝑏1, 𝑏2, 𝑏3) = (𝑝1, 𝑝2, 𝑝3, 𝑞1, 𝑞2, 𝑞3)から
(𝑎1, 𝑎2, 𝑎3, 𝑏1, 𝑏2, 𝑏3) = (𝑝1 + 𝑥, 𝑝2 +𝑥, 𝑝3 + 𝑥, 𝑞1 − 𝑥, 𝑞2 − 𝑥, 𝑞3 − 𝑥)にできます。


この性質を利用して𝑎1 = 0とすると、c11=a1+b1=b1,　c12=a1+b2=b2,　c13=a1+b3=b3
が成立します。b1がわかれば上記と同様にa2,a3はわかります(c21=a2+b1,c31=a3+b1)。


以上を踏まえて問題の解き方は下記の流れになります。
(1)a = 0として、b1,b2,b3を求める
(2)a2 = c21-b1, a3 = c31-b1からa2,a3を求める
(3)求めたa1~3とb1~3を使ってcijの我が正しいか判定する

・[ARC 096 C - Half and Half](https://atcoder.jp/contests/arc096/tasks/arc096_a)

```python:NotsoDiverse.py

```

・[ABC 057 C - Digits in Multiplication](https://atcoder.jp/contests/abc057/tasks/abc057_c)

```python:DigitsinMultiplication.py

```

・[ABC 074 C - Sugar Water](https://atcoder.jp/contests/abc074/tasks/arc083_a)

```python:SugarWater.py

```





# 第 9 問: [ABC 049 C - Daydream] (https://atcoder.jp/contests/abc049/tasks/arc065_a)
```python:Daydream.py
S = input()
 
T = ["dream","dreamer","erase","eraser"]
flag = True
for i in range(len(S)):
    if (flag == False) or (len(S) == 0):
        break
    if S[-5:] in T:
        S = S[:-5]
    elif S[-6:] in T:
        S = S[:-6]
    elif S[-7:] in T:
        S = S[:-7]
    else:
        print("NO")
        flag = False
if flag == True:
    print("YES")
```

## 第9問類題

・[AGC 013 A - Sorted Arrays](https://atcoder.jp/contests/agc013/tasks/agc013_a)

```python:SortedArrays.py

```

・[AGC 011 A - Airport Bus](https://atcoder.jp/contests/agc011/tasks/agc011_a)

```python:AirportBus.py

```

・[ABC 059 C - Sequence](https://atcoder.jp/contests/abc059/tasks/arc072_a)

```python:Sequence.py

```

・[ABC 072 C - Together](https://atcoder.jp/contests/abc072/tasks/arc082_a)

```python:Together.py

```





# 第 10 問: [ABC 086 C - Traveling](https://atcoder.jp/contests/abc086/tasks/arc089_a)

```python:Traveling.py

```

## 第10問類題

・[ABC 093 C - Same Integers](https://atcoder.jp/contests/abc093/tasks/arc094_a)

```python:SameIntegers.py

```

・[AGC 010 A - Addition](https://atcoder.jp/contests/agc010/tasks/agc010_a)

```python:Addition.py

```

・[AGC 020 A - Move and Win](https://atcoder.jp/contests/agc020/tasks/agc020_a)

```python:MoveandWin.py

```

・[ABC 073 C - Write and Erase](https://atcoder.jp/contests/abc073/tasks/abc073_c)

```python:WriteandErase.py

```