Home / Python / [Atcoder] Pythonで挑む『過去問精選 10 問！』
2020-03-22

[Atcoder] Pythonで挑む『過去問精選 10 問！』

AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～を参考にしつつPythonで各問題を解いていきます。



第1問: ABC 086 A - Product (100 点)



a, b = map(int,input().split())
print("EOvdedn"[a*b%2>0::2])


与えられた値a,bの積が奇数か偶数かを判定する問題です。積が奇数であればTrueとなり、2文字目から1文字ずつ飛ばしてOddを出力します。偶数の時は1文字目から1文字ずつ飛ばしてEvenを出力します。%演算子を使って2の剰余を求めることで奇数・偶数の判定をしています。

第2問: ABC 081 A - Placing Marbles (100 点)



print(input().count('1'))


.count()を使うことで文字列中に特定の文字列を含む数をカウントできます。

第3問: ABC 081 B - Shift Only (200 点)



input()
A = list(map(int, input().split()))
cnt = 0
while all([i%2==0 for i in A]):
    A = [a/2 for a in A]
    cnt +=1
print(cnt)


リストAの要素がすべて2で割り切れる間、リストの要素を半分にする処理を続けcntをインクリメントします。

第4問: ABC 087 B - Coins (200 点)



A, B, C, X = [int(input()) for i in range(4)]
cnt = 0
for a in range(A+1):
  for b in range(B+1):
    for c in range(C+1):
      cnt += (X == a*500 + b*100 + c*50)
print(cnt)


総当たりで Xと等しくなる硬貨の組み合わせをカウントします。

第5問: ABC 083 B - Some Sums (200 点)



N, A, B = map(int,input().split())
t = 0
for n in range(N+1):
  if A <= sum(map(int, str(n))) <= B:
    t += n
print(t)


一度nを文str型にしてmapでint型にキャストすると1桁ずつ数字を取り出すことができます。

第6問: ABC 088 B - Card Game for Two (200 点)



input()
a = sorted(map(int, input().split()))[::-1]
print(sum(a[::2])-sum(a[1::2]))


カードを降順にソートし、交互に最大値を取り出したリストの和の差を求めます。

第7問: ABC 085 B - Kagami Mochi (200 点)



N = int(input())
print(len({input() for _ in range(N)}))


大きさの違う餅だけで鏡餅が作れるので集合で段数を数えます。

第8問: ABC 085 C - Otoshidama (300 点)



N, Y = map(int, input().split())
for x in range(N+1):
  for y in range(N-x+1):
    z = N - x - y
    if 10000*x + 5000*y + 1000*z == Y:
      print(x, y, z)
      exit()
print(*[-1]*3)


3重ループにかけると計算量が多くなりすぎて-1のパターンの時にTLEが生じる問題です。x,yがわかればzは確定するのでforループをかけないのがみそです。

第9問: ABC 049 C - Daydream (300 点)



s = input()[::-1]
while s:
  start = len(s)
  for t in ['maerd', 'remaerd', 'esare', 'resare']:
    if t == s[:len(t)]:
      s = s[len(t):]
  if start == len(s):
    break
print("YNEOS"[len(s)>0::2])


使う文字列をひっくり返せば文字列の切り取りができるという問題です。

第10問: ABC 086 C - Traveling (300 点)



T, X, Y = 0, 0, 0
cnt = 0
for n in range(int(input())):
  t, x, y = map(int,input().split())
  dist = abs(x-X) + abs(y-Y)
  dt = t - T
  cnt += all([dist <= dt, (dist - dt) % 2 == 0])
  T, X, Y = t, x, y
print("YNeos"[n+1!=cnt::2])


距離と所要時間を比較したり、偶数か奇数かを確認したりしてスポットに時間通りに到達可能かを判定します。

まとめ



Pythonicな書き方とアルゴリズムの双方をこれからも深めていけるようゆっくり入門していきます。