Qiita Teams that are logged in
You are not logged in to any team

Community
Service
Qiita JobsQiita ZineQiita Blog
0
Help us understand the problem. What is going on with this article?
@arajiru

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

More than 1 year has passed since last update.

AtCoderに登録したら解くべき精選過去問10問

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

第 1 問: ABC 086 A - Product

Product.py
```a,b = map(int,input().split())
if a*b%2 == 0:
print("Even")
else:
print("Odd")
```

第1問類題

ABC 064 A - RGB Cards

RGBCards.py
```r,g,b = map(int,input().split())

if (100*r + 10*g + b)%4 == 0:
print("YES")
else:
print("NO")
```

ABC 088 A - Infinite Coins

InfiniteCoins.py
```N = int(input())
A = int(input())

if (N%500) <= A:
print("Yes")
else:
print("No")
```

ABC 082 A - Round Up the Mean

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

PlacingMarbles.py
```S = input()
count = 0
for s in S:
if s == "0":
count += 1
print(count)
```

第2問 類題

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))
```
```s = input()

print(s.replace("2017","2018"))
```
i18n.py
```s = input()

print(s[0] + str(len(s)-2) + s[-1])
```
TwoAnagrams.py
```s = sorted(input())
t = sorted(input(),reverse = True)

if s < t:
print("Yes")
else:
print("No")
```

第 3 問: ABC 081 B - Shift Only

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問類題

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])
```
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)
```
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)
```
OddString.py
```s = input()

s_odd = [s[i] for i in range(len(s)) if i%2 == 0]
print("".join(s_odd))
```
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])
```
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

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問類題

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")
```
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")
```
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))
```
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

SomeSums.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回繰り返せば全ての桁の数字を取り出せます。

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」を満たす場合カウントアップします。

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になります。

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

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問類題

SnakeToy.py
```N,K = map(int,input().split())
l = list(map(int,input().split()))

l.sort(reverse = True)
print(sum(l[0:K]))
```

【解説】降順でソートして先頭からK番目の要素まで足し上げます。

IrohaLovesStrings.py
```N,L = map(int,input().split())
S = [input() for i in range(N)]

S.sort()
print("".join(S))
```

【解説】python組み込みのsort()でリスト内の文字列を辞書順に並べます。最後にjoinで結合します。

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のときは喜ぶお菓子の数が少ない子供から配っていくのが最善です。

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))
```

【解説】解答のイメージは下記図のようになります。

第 7 問: ABC 085 B - Kagami Mochi

KagamiMochi.py
```N = int(input())
D = [int(input()) for i in range(N)]

print(len(set(D)))
```

第7問類題

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")
```
```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の出現回数をカウントするのが目的

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)
```
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)
```
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:
for i in range(len(set(A))-K):
print(count)
```

第 8 問: ABC 085 C - Otoshidama

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問類題

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の我が正しいか判定する

NotsoDiverse.py
DigitsinMultiplication.py
SugarWater.py

第 9 問: ABC 049 C - Daydream

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")
```

SortedArrays.py
AirportBus.py
Sequence.py
Together.py

第 10 問: ABC 086 C - Traveling

Traveling.py

第10問類題

SameIntegers.py
MoveandWin.py
WriteandErase.py
0
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
1. We will deliver articles that match you
By following users and tags, you can catch up information on technical fields that you are interested in as a whole
2. you can read useful information later efficiently
By "stocking" the articles you like, you can search right away