はじめに
機械学習の勉強と同時に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