LoginSignup
7

More than 5 years have passed since last update.

※随時更新※ AtCoder 過去問精選をPythonで解いてみた。(100点~200点問題)

Posted at

はじめに

機械学習の勉強と同時にpythonの文法の勉強も行っておりましたが、先日AtCoderというものを知り早速参加してみました。(そもそも競プロには前から興味があり、いつか始めようと思っていた)

AtCoderって何?という方はこちらを参照ください。
参加方法から参加後に何から手を付けたら良いか、丁寧に説明されています。

本記事で取り扱っている問題も、上記記事で紹介されている過去問精選10問の中に入っています!

上記記事ではC++での解答例が記載されていますが、本記事はpython3での解答例を記載しています。
入力例と、解答コードのみを載せているため、問題文やその他条件を知りたい場合は、リンクより問題文を参照してください。

可読性重視で記載しているつもりですが、まだまだ勉強中の身分の故、効率的ではないアルゴリズムが含まれている可能性があります。
そこは優しく教えて頂けると嬉しいです。

1. 数値を扱う倍数判定系

1-1. ABC 086 A - Product

入力は以下の形式で標準入力から与えられる。
a b

a, b = map(int, input().split())
if (a*b) % 2:
    print('Odd')
else:
    print('Even')

ポイント

なし

1-2. ABC 064 A - RGB Cards

入力は以下の形式で標準入力から与えられる。
r g b

r,g,b = map(int,input().split())
if((10*g + b) % 4 == 0):
    print('YES')
else:
    print('NO')

ポイント

百の位は何であれ、4で割り切れるかどうかは十の位と一の位のみが影響していることに気づくかどうか

1-3. ABC 088 A - Infinite Coins

入力は以下の形式で標準入力から与えられる.
N
A

N = int(input())
A = int(input())
if (N%500) > A:
    print('No')
else:
    print('Yes')

ポイント

ここからYesとNoが小文字になっている点に要注意
これで結構やられました

1-4. ABC 082 A - Round Up the Mean

入力は以下の形式で標準入力から与えられる。
a b

import math
a, b = map(int, input().split())
x = (a + b)/2
print(math.ceil(x))

ポイント

ちなみに切り捨ては下記のようになります。

import math
math.floor(x)

2. 文字列を扱う問題

2-1. ABC 081 A - Placing Marbles

入力は以下の形式で標準入力から与えられる。
s1s2s3

s = input()
c = 0
for i in s:
    if i == '1':
        c += 1
print(c) 

ポイント

もちろん、count関数を用いるともっと簡単にかける

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

2-2. ABC 095 A - Something on It

入力は以下の形式で標準入力から与えられる。
S

S = input()
Y = S.count('o')*100
print(700+Y)

ポイント

なし

2-3. ABC 085 A - Already 2018

入力は以下の形式で標準入力から与えられる。
s

s = input()
print('2018/01/' + s[-2:])

ポイント

置換したい部分以外をスライスで分割します

2-4. ABC 069 B - i18n

入力は以下の形式で標準入力から与えられる。
s

s = input()
c = len(s) - 2
print(s[0:1] + str(c) + s[-1:])

ポイント

なし

2-5. ABC 082 B - Two Anagrams

入力は以下の形式で標準入力から与えられる。
s
t

s = list(input())
t = list(input())
s.sort()
t.sort()
t.reverse() # ソートした文字列を逆順に並び替え
s=''.join(s)
t=''.join(t)
if s < t:
    print('Yes')
else:
    print('No')

ポイント

list.sort()で昇順にソートしています。
join関数の構文は 文字列 = ‘区切り文字’.join(リスト) です。
join関数により、リスト→文字列への変換を行っています。

3. for文を扱う問題

3-1. ABC 081 B - Shift Only

入力は以下の形式で標準入力から与えられる。
N
A1 A2 ... AN

ans = 10**9
N = int(input())
A = list(map(int,input().split()))
for i in A:
    p = 0
    while i % 2 == 0:
        i //= 2
        p += 1
    if p < ans:
        ans = p
print(ans)

ポイント

なし

3-2. ABC 073 B - Theater

入力は以下の形式で標準入力から与えられる。
N
l1 r1
l2 r2
・・・
lN rN

n = int(input())
box = [list(map(int, input().split())) for _ in range(n)]
sum = 0
for i in range(n):
    sum += box[i][-1] - box[i][0] + 1
print(sum)

ポイント

最後の座席番号(box[i][-1]) - 最初の座席番号(box[i][0])+ 1で人数を計算しています。

3-3. ABC 072 B - OddString

入力は以下の形式で標準入力から与えられる。
s

s = list(input())
for i in range(len(s)):
    if i % 2 == 0:
        print(s[i], end = "")

ポイント

rint('文字列', end = "") は、改行コードを出力しないという意味です。

3-4. ABC 053 B - A to Z String

入力は以下の形式で標準入力から与えられる。
s

s = list(input())
a = 200000
z = 0
for i in range(len(s)):
    if s[i] == 'A' and a > i:
        a = i
    if s[i] == 'Z' and z < i:
        z = i
print(z - a + 1)

ポイント

なし

3-5. ABC 095 B - Bitter Alchemy

入力は以下の形式で標準入力から与えられる。
N X
m1
m2
・・・
mN

n, x = map(int, input().split())
m = [int(input()) for _ in range(n)]
x -= sum(m)
mini = min(m)
print(n + x//mini)

ポイント

なし

4. for文のネストを扱う問題

4-1. ABC 087 B - Coins

入力は以下の形式で標準入力から与えられる。
A
B
C
X

A = int(input())
B = int(input())
C = int(input())
X = int(input())
count = 0
for i in range(A+1):
    for j in range(B+1):
        for k in range(C+1):
            if (500 * i) + (100 * j) + (50 * k) == X:
                count += 1
print(count)

ポイント

for文をネストさせて、全探索を行います。

4-2. ABC 105 B - Cakes and Donuts

入力は以下の形式で標準入力から与えられる。
N

N = int(input())
cake = 4
donut = 7
ac = False
for i in range(25):
    for j in range(14):
        if N == (cake * i + donut * j):
            ac = True
            break
if ac:
    print('Yes')
else:
    print('No')

ポイント

range(25)range(14)はそれぞれ100までの中に4, 7の倍数がいくつあるかを示し、その数だけループしています。

4-3. ARC 004 A - 2点間距離の最大値

なんだか急に問題文が難しくなった気がします。

入力は以下の形式で標準入力から与えられる。
N
x0 y0
x1 y1
・・・
xN-1 yN-1

import math
n = int(input()) # 入力値設定 N
longest = 0
point = []
for i in range(n): # 入力値設定 x y
    point.append(list(map(int, input().split())))

for i in range(n):
    for j in range(i,n):
        x1 = point[i][0]
        y1 = point[i][1]
        x2 = point[j][0]
        y2 = point[j][1]
        l = math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
        if longest < l:
            longest = l

print(longest)

ポイント

range(i,n)は、iからnまでの要素を持つリストを返しています
x1, y1, x2, y2には、座標の各点を設定しています → (x1, y1) (x2, y2)
longestに最長線分の長さを代入しています
 →線分の計算には三平方の定理を使用

4-4. ABC 051 B - Sum of Three Integers

入力は以下の形式で標準入力から与えられる。
K S

k, s = map(int, input().split())
count = 0
for x in range(k + 1):
    for y in range(k + 1):
        z = s - x - y
        if 0 <= z <= k:
            count += 1
print(count)

ポイント

forループを3変数分(x, y, z)行うと、各変数で0~Kまでの全パターンが網羅できないため、
ループは2変数のみにして、残りの1変数zは式変形と四則演算を駆使して求めます

5. 10 進法表記に関する問題

5-1. ABC 083 B - Some Sums

入力は以下の形式で標準入力から与えられる。
N A B

n, a, b = map(int, input().split())
sum = 0
for i in range(1, n+1):
    isum = 0
    m = i
    while m != 0:
        isum += m%10
        m = m//10
    if isum >= a and isum <= b:
        sum += i
print(sum)

ポイント

例えば、834の各桁の和は8 + 3 + 4 = 15になるので、このような処理をプログラムする
834 を 10 で割った余りは 4 -> 答えに加算
834 を 10 で割って 83
83 を 10 で割った余りは 3 -> 答えに加算
83 を 10 で割って 8
8 を 10 で割った余りは 8 -> 答えに加算
8 を 10 で割って 0
0 なので break

5-2. ABC 080 B - Harshad Number

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
7