競技プログラミング

ABC172

はじめに

この記事では、AtCoder Beginer Contest 172のA~D問題を解説します。

A - Calc

https://atcoder.jp/contests/abc172/tasks/abc172_a
Pythonの累乗は第一引数と第二引数が共に整数であれば、整数を返すので問題ありません。

1
2
a = int(input())
print (a+a**2+a**3)

B - Minor Change

https://atcoder.jp/contests/abc172/tasks/abc172_b

一文字ずつ判定をしていけば良いです。

1
2
3
4
5
6
S = input()
T = input()
ans = 0
for s,t in zip(S,T):
    ans += (s!=t)
print (ans)

C - Tsundoku

https://atcoder.jp/contests/abc172/tasks/abc172_c

累積和を用いることでO(M+N)で求めることができます。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import itertools
N,M,K = map(int,input().split())
A = [0]+list(map(int,input().split()))
B = [0]+list(map(int,input().split()))
SA = list(itertools.accumulate(A))
SB = list(itertools.accumulate(B))
ans = 0
j = len(B)-1
for i in range(len(SA)):
    while(j>=0):
        if SA[i] + SB[j] <= K:
            ans = max(ans,i+j)
            break
        j-=1
print (ans)

D - Sum of Divisors

https://atcoder.jp/contests/abc172/tasks/abc172_d

公式解説の解法の通りに実装すれば、O(N)です。

1
2
3
4
5
6
N = int(input())
ans = 0
for X in range(1, N+1):
  Y = N // X
  ans += Y * (Y + 1) // 2 * X
print(ans)

二重ループ内の計算が軽いため、PyPyであれば以下のコードでもACできます。

1
2
3
4
5
6
N = int(input())
ans = 0
for i in range(1, N+1):
    for j in range(i, N+1, i):
        ans += j
print(ans)

関連記事

過去のABC解説記事です。

  • ABC171
    • A-E問題を解いています。
  • ABC170
    • A-D問題を解いています。
  • ABC169
    • A-F問題を解いています。
  • ABC168
    • A-E問題を解いています。
  • ABC167
    • A-E問題を解いています。
  • ABC166
    • A-F問題を解いています。
  • ABC165
    • A-F問題を解いています。
  • ABC164
    • A-E問題を解いています。
  • ABC163
    • A-D問題を解いています。
  • ABC162
    • A-E問題を解いています。

記事情報

  • 投稿日：2020年6月27日
  • 最終更新日：2020年6月27日