AtCoder ABC176 A-D問題までpythonで解いてみた.
AtCoder ABC176に参加したのでその記録として投稿しようと思います.
A問題
高橋君はたこ焼きが好きです。
たこ焼き器を使うと、1度に最大で X個のたこ焼きを作ることができます。
これにかかる時間は作る個数によらずT分です。N個のたこ焼きを作るためには何分必要ですか？
考えたこと
N個のたこ焼きを作るためにX個作る作業を何回行う必要があるか考えました.
N%X == 0 の時に注意してN//Xを考えれば良いです.
n, x, t = map(int, input().split())
cnt = n//x
if n%x == 0:
print(cnt*t)
else:
cnt += 1
print(cnt*t)
B問題
整数Nが9の倍数であることと、Nを十進法で表したときの各桁の数の和が9の倍数であることは同値です。
Nが9の倍数であるか判定してください。
0 < N < 10**(200000)
考えたこと
Nを文字列として受け取り,最上位から順に整数に変換しながら加えていけば良いです.
自分はNが非常に大きくなる可能性があるため逐次9で割っていたのですが,その必要はなかったみたいです.
n=input()
l = len(n)
mod = 9
judge = 0
for i in range(l):
judge += int(n[i])
judge %= mod
if judge == 0: print("Yes")
else: print("No")
C問題
N人が1列に並んでおり、前からi番目の人の身長はA_iです。
それぞれの人の足元に、高さが0以上の踏み台を設置し、全ての人が次の条件を満たすようにしたいです。
条件：踏み台を込めて身長を比較したとき、自分より前に、自分より背の高い人が存在しない
この条件を満たす時の、踏み台の高さの合計の最小値を求めてください。
考えたこと
難しく考えず,今現在注目している人の身長と次の人の身長を比較して
A_i < A_i+1 であれば踏み台は必要ではありません.
A_i >= A_i+1 の時後ろの人に踏み台が必要です.(身長差がない場合(A_i == A_i+1の時)は踏み台の高さは0です)
この時最小の踏み台の高さhは A_i - A_i+1 です.
A_i+1 = A_i と更新することを忘れずにi=1~n-1まで調べれば良いです.
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n-1):
if a[i] >= a[i+1]:
ans += a[i] - a[i+1]
a[i+1] = a[i]
else:
pass
print(ans)
D問題
考えたこと
道'.'続きのところはいくら移動してもコスト(魔法を使う回数)は0であるから,道続きな部分を集合にすれば良いと思った.
しかし,集合にしたところでコストを最小にする道の選び方をどのように実装すれば良いかわからなかった為コンテスト中にはAC出来なかった.
from collections import deque
H, W=map(int, input().split())
ch, cw=map(int, input().split())
dh, dw=map(int, input().split())
ch-=1 #0_indexedにする
cw-=1
dh-=1
dw-=1
grid=["0"]*H
for i in range(H):
s=input()
grid[i]=s
Inf=10**12
cost=[[Inf] * W for i in range(H)] #各マスへの移動コスト
walk=[(0, 1), (0, -1), (-1, 0), (1, 0)]
warp=[]
for i in range(-2, 3):
for j in range(-2, 3):
if i==0 and j==0:
continue
if (i, j) not in walk:
warp.append((i, j))
q=deque()
cost[ch][cw]=0
q.append((ch, cw, 0))
while q:
x, y, c=q.popleft()
for dx, dy in walk: #移動A
nx = x+dx
ny = y+dy
if 0<= nx < H and 0<= ny < W and grid[nx][ny]=="." and cost[nx][ny]>c:
cost[nx][ny]=c
q.appendleft((nx, ny, c)) #移動Aはコスト０,キューの先頭に追加
for dx, dy in warp:#移動B
nx = x+dx
ny = y+dy
if 0<= nx < H and 0<= ny < W and grid[nx][ny]=="." and cost[nx][ny]>c+1:
cost[nx][ny]=c+1
q.append((nx, ny, c+1)) #移動Bはコスト1,キューの最後尾に追加
if cost[dh][dw]==Inf:
print(-1)
else:
ans=cost[dh][dw]
print(ans)
どうやら深さ優先探索(DFS)というアルゴリズムを用いるみたいだった.
典型的なアルゴリズムらしい()のでしっかりと理解し,次は実装出来るようにしておきたい.
やっていることは理解できるのですが,問題に適用するとなると急にハードルが上がる気がします😢
参考
MA-R-CO NOTEさん
https://marco-note.net/