ABC338のA~F問題をPythonで解説(復習)

## はじめに
### 関係するリンク(参考文献など)
- [今回のコンテスト](https://atcoder.jp/contests/abc338)
- [競技プログラミングをするフレンズさんのE問題解説](https://twitter.com/kyopro_friends/status/1751240830646698040)
- [F問題の公式解説](https://atcoder.jp/contests/abc338/editorial/9170)
### 筆者について
- [Atcoderアカウント](https://atcoder.jp/users/mattsunkun)
- [今回の成績(ooooxxx)](https://atcoder.jp/users/mattsunkun/history/share/abc338)
- [解説で示したA問題の提出](https://atcoder.jp/contests/abc338/submissions/49777105)
- [解説で示したB問題の提出](https://atcoder.jp/contests/abc338/submissions/49777441)
- [解説で示したC問題の提出](https://atcoder.jp/contests/abc338/submissions/49777545)
- [解説で示したD問題の提出](https://atcoder.jp/contests/abc338/submissions/49777912)
- [解説で示したE問題の提出](https://atcoder.jp/contests/abc338/submissions/49778055)
- [解説で示したF問題の提出](https://atcoder.jp/contests/abc338/submissions/49778164)

# A問題
- 0番目の文字とそれ以外の文字を切り分けて考える．
- islower()を使って小文字判定する．
```A.py
# 入力受け取り
S = input()

# 0番目の文字が小文字だったらNoで終了．
if(S[0].islower()):
  print("No")
  exit()
  
# 1番目の文字から最後までの文字を見る．
for i in range(1, len(S)):
  # 小文字だったら次をみる．
  if(S[i].islower()):
    continue
  # 大文字だったらNoで終了．
  else:
    print("No")
    exit()
    
# Yesを出す．
print("Yes")
```

# B問題
- 頻度を登録する辞書を作る．
- 最頻度を保持する．
- 最頻度になっている文字をアルファベットでソートする．
```B.py
S = input()

N = len(S)

# 頻度を辞書で保存する．
# key: 文字の種類
# val: 文字の頻度
di= {}

# 「一番頻度の高い文字の頻度数」．初期値は0
ma = 0

# それぞれの文字に対して確認を行う．
for s in S:
  # 辞書に既に登録されている文字だったら
  if(s in di):
    # その文字に対して頻度を一つ増やす．
    di[s] += 1
  # 辞書にまだ登録されていなかったら．
  else:
    # 辞書に(初めて出てきたから)頻度1で登録する．
    di[s] = 1
    
  # 「更新した頻度数」で，新しい「一番頻度の高い文字の頻度数」を決定する．
  ma = max(ma, di[s])
    

# 一番頻度数の高い文字を格納するためのリスト
ans = []
# 頻度の辞書key-valueで取り出す．
for k, v in di.items():
  # 頻度が「一番頻度の高い文字の頻度数」のときのその文字をリストに追加．
  if v == ma:
    ans.append(k)
    

# 文字をアルファベット順にソートする．
ans.sort()

# 最初のアルファベットを出力する．
print(ans[0])
```

# C問題
- Aがn(0~最大値)個作れるとする．
- そのnが論理的に可能かを確認する．
- そのnに対してBの作れる値を算出する．
- 答えを更新する．
```C.py
N = int(input())

Q = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# 制約条件的に作れるAまたはBの最大値のちょっと多めの値．
MAX = 10**6 + 2

# 答え
ans = 0

# 無限を表現する数
INF = 10**7

# aをbで割って，0で割った時は無限を返す関数．
def divinn(a, b):
  if(b == 0):
    return INF
  else:
    return a//b

# Aを作る数を0からMAXまでとする．
for aCre in range(MAX):
  # 残ったBに使える材料を格納する．
  bLeft = []
  # 終了フラグ
  kill = False
  # それぞれの材料に対して
  for i in range(N):
    # bに使える残りの材料．
    left = Q[i] - (aCre*A[i])
    # 材料が負なら，aCreの値が不適切より，終了
    if(left < 0):
      kill = True
      break
    # bに使える残りの材料を登録
    bLeft.append(left)
  
  # 終了フラグが立ってたら終了
  if(kill):
    continue
  
  # bの作れる数
  bCre = divinn(bLeft[0], B[0])
  
  # bの作れる数は，それぞれの材料に対して作ることのできる数の最小値に依存する．
  for i in range(1, N):
    bCre = min(bCre, divinn(bLeft[i], B[i]))
  
  # 最大値を更新する．
  ans = max(ans, aCre+bCre)
  
print(ans)
```

# D問題
- コードに書いた方針通りです．

字が汚くてごめん．`getDist(st, ed)`関数のイメージ図です．
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3534163/e0a25538-0595-b614-beb7-131fb6f5d826.png)

```D.py
import itertools

N, M = map(int, input().split())

X = list(map(int, input().split()))

"""
<方針>
ツアーで島を巡り，その際，島に行ける最短ルートの候補2つを登録する．
それらのルートはそれぞれ，そのルートに対して，通らなかったルートの橋を切り落とした前提となる．
このルートを毎回全て書き込んでいては計算が間に合わないので，いもす法でなんとかする．
"""

# index: どこの橋を切り取るか．
# value: l(ツアーの長さ)
ls = [0]*N

# stからedに行く2通りのほうほうを出力する．
# ただし，0~N-1に対して，後で累積和をとったときに正しくなるように(いもす法)，
# どこでどの値を入れるべきかの辞書を返す．
def getDist(st, ed):
  # 戻り値
  di = {}
  
  # st<edとする．
  if(st>ed):
    st, ed = ed, st
    
  # st==0のとき，いもす法の変換は1箇所のみだから
  if(st == 0):
    first = (N-ed)
    last = ed
    di[0] = first
    di[ed] = -first + last
  else:
    r = ed - st
    l = N - r
    
    l, r = r, l
    
    di[0] = l
    di[st] = -l + r
    di[ed] = -r + l

  return di

# ツアー開始したタイミングでは長さlは0だから，それ以外のツアーで考える．
for i in range(1, M):
  # 一個前のツアーとの距離に対して，getDistを行う．
  di = getDist(X[i-1]-1, X[i]-1)
  
  # いもす法を行うところをリストに登録する．
  for k, v in di.items():
    ls[k] += v
    

# 累積和を行う．
ans = list(itertools.accumulate(ls))

# 最小値を登録する．
print(min(ans))
```

# E問題
- 円は数直線上に展開しても問題ない．
- Chrodを結ぶ線で一意な対消滅する数字の組み合わせを作成する．
- 数字の組み合わせを端から順番に見た時に，全て対消滅すれば，交点は存在しない．
```E.py
from collections import deque



N = int(input())
ls = [0]*(2*N)
for i in range(N):
  ab = list(map(int, input().split()))
  
  # 0-indexed
  a, b = ab[0]-1, ab[1]-1
  # a<bとする．
  if(a>b):
    a, b = b, a

  # 一意な自然数を登録
  ls[a] = (i+1)
  # 上記のマイナスの数を登録
  ls[b] = -(i+1)
  

# 自然数が登録されたdeque
q = deque(ls)
# 足して0になる数が連続すると対消滅するスタック
st = deque() 
while q:
  # 数を取り出す．
  x = q.popleft()
  # スタックに数が存在し，それと取り出した数の和が0の時，
  if(st and st[-1] + x == 0):
    # 対消滅
    st.pop()
  else:
    # スタックに数保存
    st.append(x)
    

if(st):
  print("Yes")
else:
  print("No")
```

# F問題
- 何回でも頂点を訪れていいので，先に全ての頂点の間の最短距離を求めておく．(O(N^3))
- あとは通常の循環セールスマン問題．(O(2^N * N^2))
- 制限時間が6secなので，N=20でも大丈夫そう．

```F.py
N, M = map(int, input().split())

UVW = []
INF = 10**10

# 重み付きグラフを作成する．
graph = [[INF]*N for i in range(N)]
for i in range(M):
  u, v, w = map(int, input().split())
  # 0-indexed
  u -= 1
  v -= 1
  UVW.append((u, v, w))
  graph[u][v] = w
  
# ワーシャル・フロイド
def warshallFloyd(graph, INF):
  N = len(graph)
  # 初期値は入力をコピー
  dp = []
  for i in range(N):
    dp.append(graph[i][:])
  
  # 3重ループで全ての頂点の間の距離を求める．
  for k in range(N):
    for i in range(N):
      for j in range(N):
        if(dp[i][k] == INF or dp[k][j] == INF):continue
        dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])
        
  return dp

# 全ての頂点の間の距離を取得する．
wf = warshallFloyd(graph, INF)

# 頂点集合Sを訪れたとき，最後に特定の頂点であった時のコストの最小値
dp = [[INF]*N for i in range(1<<N)]
for i in range(N):
  dp[1<<i][i] = 0

# 頂点集合を確認する．
for bit in range(1, (1<<N)):
  # 現在の頂点
  for i in range(N):
    # bitのグループに入っていなければ更新しない．
    if(((~bit>>i) & 1) == 1):continue
    # 現在到達不能なところにいたら更新しない．
    if(dp[bit][i] == INF):continue
    # 移動先の頂点
    for j in range(N):
      # bitのグループに既に入っているところは更新しない．
      if(((bit>>j)&1) == 1):continue
      # iからjへのパスが存在しなければ更新しない．
      if(wf[i][j] == INF):continue
      dp[bit|(1<<j)][j] = min(dp[bit|(1<<j)][j], dp[bit][i]+wf[i][j])
      
ans = min(dp[(1<<N) - 1])

# 全ての頂点を訪れることができなかったらNo
if(ans >= INF):
  print("No")
else:
  print(ans)
```