ABC348(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)

# 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")
```


# 補足
### 関係するリンク(参考文献など)
- [今回のコンテスト](https://atcoder.jp/contests/abc348)
### 筆者について
- [Atcoderアカウント](https://atcoder.jp/users/mattsunkun)
- [今回の成績(ooox--)](https://atcoder.jp/users/mattsunkun/history/share/abc348)
- [解説で示したA問題の提出](https://atcoder.jp/contests/abc348/submissions/52231793)
- [解説で示したB問題の提出](https://atcoder.jp/contests/abc348/submissions/52231936)
- [解説で示したC問題の提出](https://atcoder.jp/contests/abc348/submissions/52234314)
- [解説で示したD問題の提出](https://atcoder.jp/contests/abc348/submissions/52234730)
### その他
- **間違いを含んでいる可能性があります．**
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
### 最後に一言
- 一応，EとFは復習(~~他人のコードのほぼ丸コピ~~)したけど，言語化できるほど理解できていないため，記事にはしませんでした．