ABC348(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)
A問題
- FizzBuzzと同じノリでやる.
-
ooxooxooxooxo...
をまとめて出力するため,ans
変数に値を格納していく. -
for
で回すときは,繰り返し変数i
は,0
始まりなことに注意し,i+1
で評価する.
A.py
"""
<方針>
- FizzBuzzと同じノリでやる.
- `ooxooxooxooxo...`をまとめて出力するため,`ans`変数に値を格納していく.
- `for`で回すときは,繰り返し変数`i`は,`0`始まりなことに注意し,`i+1`で評価する.
"""
# 標準入力から値を受け取る.
N = int(input())
# 答えを格納するListの変数
ans = []
# ペナルティキックを一つずつ見る
for i in range(N):
# 3の倍数のとき,
if( (i+1)%3 == 0 ):
# 答えに"x"を追加する.
ans.append("x")
# 3の倍数でないとき,
else:
# 答えに"o"を追加する.
ans.append("o")
# Listを空文字列で連結して出力する.
print("".join(ans))
B問題
- 入力を最初に全て受け取る.
- 一つ一つの頂点に対して,全ての頂点との距離を測る.
- その際,番号の若い順番から見ていき,距離が少しでも大きくなるときのみ値を更新する.
- 距離を測り終えたら,ループの中で答えを出力する.
B.py
"""
<方針>
- 入力を最初に全て受け取る.
- 一つ一つの頂点に対して,全ての頂点との距離を測る.
- その際,番号の若い順番から見ていき,距離が少しでも大きくなるときのみ値を更新する.
- 距離を測り終えたら,ループの中で答えを出力する.
"""
# 入力受け取り
N = int(input())
XY = []
for i in range(N):
XY.append(list(map(int, input().split())))
# 一つ一つの頂点に注目する.
for i in range(N):
# 距離の最大値を格納する変数.初期値は-♾️にする.
ma = -float("inf")
# 距離の最大値の座標番号を記録する変数.初期値は-1にする.
nu = -1
# 他の頂点との距離を一つずつ測る.
for j in range(N):
# 自分同士の距離は計測しない.
if(i==j):
continue
# 自分自身の頂点
a = XY[i]
# 相手の頂点
b = XY[j]
# 距離を測る.
di = (a[0]-b[0])**2+(a[1]-b[1])**2
# 距離の最大値がベストを更新したとき,
if(ma<di):
# 距離を更新する.
ma = di
# 座標番号を更新する.
nu = j
# 座標番号は0-indexedで記録しているので,+1して出力する.
print(nu+1)
C問題
- 色
C
におけるおいしさの最小値を辞書で記録する. - 上記で求めた辞書から,値が最大となるものを出力する.
C.py
"""
<方針>
- 色`C`におけるおいしさの最小値を辞書で記録する.
- 上記で求めた辞書から,値が最大となるものを出力する.
"""
# 入力
N = int(input())
# 色Cにおけるおいしさの最小値を記録する辞書
di = dict()
for i in range(N):
# おいしさと色を取得
a, c = map(int, input().split())
# 色が既に辞書に登録されていれば,
if(c in di):
# 既に辞書に登録されているその色のおいしさと比較して,小さい方を辞書に再登録する.
di[c] = min(di[c], a)
# 色がまだ辞書に登録されていなければ,
else:
# 辞書にその色と味を登録登録する.
di[c] = a
# 答えの出力.おいしさの最大値の初期値は-1とする.
ans = -1
# 辞書の要素を一つずつ見る.
for k, v in di.items():
# おいしさの最大値を更新する.
ans = max(v, ans)
# 出力
print(ans)
D問題
- 薬があるところ全てについて,他の薬を使わずに,他の薬及びゴールまで行けるかどうかを判定し,有向グラフを作成する.
- スタートと位置が被っている薬の位置から開始し,ゴールまで辿り着けるかどうかを判定する.
D.py
"""
<方針>
- 薬があるところ全てについて,他の薬を使わずに,他の薬及びゴールまで行けるかどうかを判定し,有向グラフを作成する.
- スタートと位置が被っている薬の位置から開始し,ゴールまで辿り着けるかどうかを判定する.
"""
H, W = map(int, input().split())
rawAA = [] # グリッド情報
S = (-1, -1) # スタート座標
T = (-1, -1) # ゴール座標
for i in range(H):
a = input()
tmp = [] # グリッド情報として格納するリスト
for j in range(W):
if(a[j]=="#"):
# 障害物は-1と表現する
tmp.append(-1)
else:
# 通れるマス(空きマスなど)は0と表現する
tmp.append(0)
# スタートとゴール座標を登録する.
if(a[j]=="S"):
S = (i, j)
if(a[j]=="T"):
T = (i, j)
rawAA.append(tmp)
N = int(input())
RCE = [] # R, C, Eの入力をそのまま保持するList
# 薬がマスに置いてあるかどうかの二次元配列.
## -1: 薬が置いてない.
## 0<=i<N: i番目の薬が置いてある.
## N: ゴールの位置
isMed = [[-1]*W for i in range(H)]
# スタートと位置が被っている薬が何番目の薬かを記録する変数.
st = -1
for i in range(N):
r, c, e = map(int, input().split())
r -= 1 # 0-indexed
c -= 1 # 0-indexed
RCE.append([r, c, e])
isMed[r][c] = i # 薬登録
if(r==S[0] and c==S[1]):
st = i # スタート位置にある薬の登録
# ゴールの位置を記入する.既に薬が置いてあるとしても上書きする.
isMed[T[0]][T[1]] = N
# スタート位置に薬がないとき,
if(st == -1):
print("No")
exit()
from collections import deque
# ある薬からある薬へ到達できるかの有向グラフ
Edges = [set() for i in range(N+1)]
# それぞれの薬に注目する.
for i in range(N):
# 新しいグリッドを作成する.
# このグリッドに,最も高いエネルギーを持った状態で到達できる値を記入していく.
AA = [x[:] for x in rawAA]
q = deque() # 現在いるマスの情報と,現在のエネルギー情報を持つdeque
q.append(RCE[i][:])
AA[r][c] = e # 薬の開始位置の最高エネルギーは決まっている.
# BFSを行う.
while q:
r, c, _e = q.popleft()
# 上下左右に移動する.
for fla1 in range(4):
y, x, e = r, c, _e # 移動後の座標とエネルギー
if(fla1==0):
y -= 1
if(fla1==1):
y += 1
if(fla1==2):
x -= 1
if(fla1==3):
x += 1
e -= 1
# 移動先に壁が無いかどうかの確認をする.
if(0<=y<H and 0<=x<W and AA[y][x]!=-1):
# 他の薬があれば,
if(isMed[y][x]!=-1):
# 有向辺を作成する.
Edges[i].add(isMed[y][x])
# 高エネルギーな値をグリッドに記入できれば,
if(AA[y][x]<e):
# 値を更新する.
AA[y][x] = e
# dequeに追加する.
q.append([y, x, e])
# スタートからゴールまで到達できるか探索するdeque
q = deque()
q.append(st)
# スタート位置から到達可能な薬のList.N番目はゴールに到達できるかどうかを表現する.
vis = [False]*(N+1)
vis[st] = True # 開始位置は当然到達可能
# BFS
while q:
x = q.popleft()
for item in Edges[x]:
# 到達したことがなければ,
if(not vis[item]):
# 到達した記録をし,
vis[item] = True
# dequeに追加する.
q.append(item)
if(vis[N]):
print("Yes")
else:
print("No")
補足
関係するリンク(参考文献など)
筆者について
その他
- 間違いを含んでいる可能性があります.
- 方針と言いつつ,方針ではない感想などを書いている可能性があります.
- A問題から解説がだんだん省略されます.
最後に一言
- 一応,EとFは復習(
他人のコードのほぼ丸コピ)したけど,言語化できるほど理解できていないため,記事にはしませんでした.