競技プログラミング

ABC170

はじめに

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

A - Five Variables

https://atcoder.jp/contests/abc170/tasks/abc170_a

1
2
3
4
A = list(map(int,input().split()))
for i in range(5):
    if A[i] == 0:
        print(i+1)

B - Crane and Turtle

https://atcoder.jp/contests/abc170/tasks/abc170_b

シミュレーションしても十分に間に合います。

1
2
3
4
5
6
7
x, y = map(int,input().split())
for a in range(x+1):
    b = x-a
    if 2*a+4*b==y:
        print ('Yes')
        exit()
print ('No')

C - Forbidden List

https://atcoder.jp/contests/abc170/tasks/abc170_c

解が0や101になる可能性があります。

1
2
3
4
5
6
7
8
9
10
11
X, N = map(int,input().split())
P = list(map(int,input().split()))
P.sort()
diff = 10**10
for p in range(102):
    if p in P:
        continue
    if abs(X-p) < diff:
        diff = abs(X-p)
        ans = p
print (ans)

D - Not Divisible

https://atcoder.jp/contests/abc170/tasks/abc170_d

ソートをして、小さい順にAの倍数を記録していきます。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from collections import Counter
import bisect
N = int(input())
A = list(map(int,input().split()))
cnt = Counter(A)
A.sort()
ans = 0
MX = 10**6
P = [0] * (MX+1)
for a in A:
    if P[a]==0:
        for i in range(MX+1):
            x = a*i
            if x > MX:
                break
            P[x] = 1
        if cnt[a]==1:
            ans+=1
print (ans)

F - Pond Skater

https://atcoder.jp/contests/abc170/tasks/abc170_f

公式の解説にはダイクストラ法による解法がありますが、幅優先探索で解くこともできます

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from collections import deque
dxdy = ((-1,0), (1,0), (0,-1), (0,1)) # タプルやリストで持っておくと便利

H, W, K = map(int,input().split())
x1, y1, x2, y2 = map(int,input().split())
mp = [input() for _ in range(H)]
INF = 10**10
dist = [[INF]*W for _ in range(H)]
dist[x1-1][y1-1] = 0
q = deque()
q.append((x1-1,y1-1)) # スタート地点をenqueue
while(q):
    x, y = q.popleft()
    if x==x2-1 and y==y2-1:
        print (dist[x2-1][y2-1])
        exit()
    else:
        for dx, dy in  dxdy:
            for i in range(1,K+1):
                nx = x + dx*i
                ny = y + dy*i
                if not (0<=nx<H and 0<=ny<W) or mp[nx][ny]=='@':
                    break
                if dist[nx][ny] <= dist[x][y]:
                    break 
                if dist[nx][ny] == INF:
                    q.append((nx,ny))
                    dist[nx][ny] = dist[x][y] + 1
print(-1)

関連記事

過去のABC解説記事です。

  • 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月14日
  • 最終更新日：2020年6月15日