Go to Qiita Advent Calendar 2024 Top
LoginSignup
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@arajiru(arakawa)

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

Last updated at Posted at 2020-02-09

題通りです。解いているのは類題なのでご注意下さい。
精選問題もついでに解いています。解答はすべてACになることを確認しています。
AtCoderに登録したら解くべき精選過去問10問

精選問題10問の解答は下記記事をご参照下さい。
AtCoderに登録したら解くべき精選過去問10問をPythonで解いてみた

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

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

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

・ABC 095 A - Something on It

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

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

・ABC 069 B - i18n

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

・ABC 082 B - Two Anagrams

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

・ABC 068 B - Break Number

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

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

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

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

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

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

・ABC 105 B - Cakes and Donuts

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点間距離の最大値

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

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

・ABC 080 B - Harshad Number

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

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

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)が最小

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)

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

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

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

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

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

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

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

第7問類題

・ABC 071 B - Not Found

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

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

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

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

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

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

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

NotsoDiverse.py

・ABC 057 C - Digits in Multiplication

DigitsinMultiplication.py

・ABC 074 C - Sugar Water

SugarWater.py

第 9 問: [ABC 049 C - Daydream] (https://atcoder.jp/contests/abc049/tasks/arc065_a)

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

SortedArrays.py

・AGC 011 A - Airport Bus

AirportBus.py

・ABC 059 C - Sequence

Sequence.py

・ABC 072 C - Together

Together.py

第 10 問: ABC 086 C - Traveling

Traveling.py

第10問類題

・ABC 093 C - Same Integers

SameIntegers.py

・AGC 010 A - Addition

Addition.py

・AGC 020 A - Move and Win

MoveandWin.py

・ABC 073 C - Write and Erase

WriteandErase.py
1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?