LoginSignup
2
0
@mattsunkun

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

Posted at

はじめに

関係するリンク(参考文献など)

筆者について

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

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)
2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
0