[ABC376] ABC 376(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)

# [ABC376] ABC 376(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)

# A問題
- 飴玉を前回もらったタイミングを `a` という変数で管理する．
  - 前回もらった時は遠い過去 `-float("inf")` とする．
- 飴玉がもらえるかどうかをシミュレーションすれば良い．
```A.py
"""
<方針>
- 飴玉を前回もらったタイミングを `a` という変数で管理する．
  - 前回もらった時は遠い過去 `-float("inf")` とする．
- 飴玉がもらえるかどうかをシミュレーションすれば良い．
"""
# 入力
N, C = map(int, input().split())
T = list(map(int, input().split()))

# 飴玉を何個もらえたか．
ans = 0
# 前回飴玉をもらったタイミング
a = -float("inf")
# シミュレーション
for t in T:
  # 飴玉もらえる時
  if(t-a>=C):
    # 飴玉もらえたタイミングを更新
    a = t
    # 飴玉もらった個数を更新
    ans += 1

# 出力
print(ans)
```

# B問題
- 最小コストは単純に腕を回していれば達成しそう．
- 実際にシミュレーションするしかねぇ！！
- 腕を回した時に， `N` と `1` を跨ぐかどうかは毎回判断するしかねぇ！！
- せっかくだから，俺は `0-indexed` で話を進めるぜ！！
```B.py
"""
<方針>
- 最小コストは単純に腕を回していれば達成しそう．
- 実際にシミュレーションするしかねぇ！！
- 腕を回した時に， `N` と `1` を跨ぐかどうかは毎回判断するしかねぇ！！
- せっかくだから，俺は `0-indexed` で話を進めるぜ！！
"""
# 入力
N, Q = map(int, input().split())

# 左手の位置
a = 0
# 右手の位置
b = 1
# コスト
ans = 0

# シミュレーション
for i in range(Q):
  # 入力
  h, t = input().split()
  # 0-indexedで目的地を取得
  t = int(t)-1
  
  # 左手を動かす時
  if(h=="L"):
    # 既に目的地に到達していれば動かさない．
    if(a==t):continue
    # 現在地と目的地が右手よりも位置が大きいor小さい時
    if (a<b and t<b) or (a>b and t>b):
      # N -> 1を跨がずに移動する．
      ans += abs(t-a)
    else:
      # N -> 1を跨いで移動する．
      ans += (N - abs(t-a))
    # 目的地に移動する
    a = t
  # 右手を動かす時
  else:
    # 既に目的地に到達していれば動かさない．
    if(b==t):continue
    # 現在地と目的地が左手よりも位置が大きいor小さい時
    if (b<a and t<a) or (b>a and t>a):
      # N -> 1を跨がずに移動する．
      ans += abs(t-b)
    else:
      # N -> 1を跨いで移動する．
      ans += (N - abs(t-b))
    # 目的地に移動する．
    b = t
# 出力
print(ans)
```

# C問題
## 方針
- `A` と `B` を逆順にソートする．
- おもちゃを既にある箱でしまえたら問題はない．
- もし，しまえないおもちゃが現れたら， `x` で代用していく．その時，添え字のずれを `d` で保存しておく．
- もし，しまえないおもちゃが `2` つ目以降も出てきたら `-1` を出す．
- 最後まで `x` を用いなかった場合は，一番小さいおもちゃをしまう．
## 前提
- `C`問題あたりで，`TLE`になる人は，制約条件を見る癖をつけよう．
- `A`と`B`問題では，基本的に制約条件を見ずにやっても解ける．
- しかし，`C`問題以降では，制約条件を見ないと必ず`TLE`すると思っても良い．
- 詳しい話は私の[352回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`C`問題の解説に記したので，是非参照してほしい．
```C.py
"""
<方針>
- `A` と `B` を逆順にソートする．
- おもちゃを既にある箱でしまえたら問題はない．
- もし，しまえないおもちゃが現れたら， `x` で代用していく．その時，添え字のずれを `d` で保存しておく．
- もし，しまえないおもちゃが `2` つ目以降も出てきたら `-1` を出す．
- 最後まで `x` を用いなかった場合は，一番小さいおもちゃをしまう．
"""
# 入力
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# 逆順ソート
A.sort(reverse=True)
B.sort(reverse=True)

# xを使うと1になる
d = 0
# xを使うとintが入る
ind = None
# おもちゃを見ていく
for i in range(N-1):
  # おもちゃがしまえない時
  if(A[i+d]>B[i]):
    # 既にxを使っていたら
    if(d==1):
      # しまえない
      print(-1)
      exit()
    # 初めてしまえないものを見つけたら
    else:
      # 添え字のずれを保存する
      d = 1
      # xを利用したタイミングを保存する
      ind = i
      # <最後のおもちゃ対策> 次のおもちゃがしまえなくなった時
      if(A[i+d]>B[i]):
        # しまえない
        print(-1)
        exit()
# xを使わなかったとき
if(ind is None):
  # 一番小さいおもちゃをxでしまう
  ind = -1
# 作った箱の大きさを出力
print(A[ind])
```

# D問題
- `dijkstra` を使って全ての頂点への最短距離を求める．
- 原点に戻ってきた時，最短距離だった場合は答え(`ans`)を更新する．
```D.py
"""
<方針>
- `dijkstra` を使って全ての頂点への最短距離を求める．
- 原点に戻ってきた時，最短距離だった場合は答え(`ans`)を更新する．
"""
# 有向グラフ構築
N, M = map(int, input().split())
E = [[] for _ in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  E[a].append(b)

# それぞれの頂点への最短移動距離
V = [float("inf")]*N
# 原点のコストは0
V[0] = 0
# 原点に戻ってきた時の最短コスト
ans = float("inf")

# dijkstra
import heapq
q = [0]
while q:
  u = heapq.heappop(q)
  for v in E[u]:
    # 原点に戻ってきた時
    if(v==0):
      # 最短距離の更新
      ans = min(ans, V[u]+1)
      continue
    if(V[u]+1<V[v]):
      V[v] = V[u] + 1
      heapq.heappush(q, v)

# 原点に戻って来れなかった時
if(ans>10**10):
  ans = -1
# 出力
print(ans)
```


# 補足
### 関係するリンク(参考文献など)
- [今回のコンテスト](https://atcoder.jp/contests/abc376)
### 筆者について
- [Atcoderアカウント](https://atcoder.jp/users/mattsunkun)
- *今回も不参加のため，成績なし．*
- [解説で示したA問題の提出](https://atcoder.jp/contests/abc376/submissions/59129666)
- [解説で示したB問題の提出](https://atcoder.jp/contests/abc376/submissions/59129876)
- [解説で示したC問題の提出](https://atcoder.jp/contests/abc376/submissions/59130083)
- [解説で示したD問題の提出](https://atcoder.jp/contests/abc376/submissions/59130162)
### その他
- **間違いを含んでいる可能性があります．**
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
### 最後に一言
- やらなきゃいけないことをやってなくてやばい．