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

A問題

• 文字列がそれぞれAtCoderとLandとなるかどうかを確認する．

A.py

"""
<方針>
- 文字列がそれぞれ`AtCoder`と`Land`となるかどうかを確認する．
"""
# 標準入力を受け取る．
S, T = input().split()

# 文字列が両方ともAtcoderとLandであるかどうか
if(S=="AtCoder" and T=="Land"):
  # Yesを出力する．
  print("Yes")
else:
  # Noを出力する．
  print("No")

B問題

• チケットに並ぶ人を順番に見ていく．
• 経過時間の時点で並んでない場合は，経過した時間timeをチケットに並び始めた人が来たその時間T[i]まで早める．
• 並んだ人を時間Aをかけて対応する．
• 経過した時間timeを出力する．

B.py

"""
<方針>
- チケットに並ぶ人を順番に見ていく．
- 経過時間の時点で並んでない場合は，経過した時間`time`をチケットに並び始めた人が来たその時間`T[i]`まで早める．
- 並んだ人を時間`A`をかけて対応する．
- 経過した時間`time`を出力する．
"""
# 標準入力を受け取る．
N, A = map(int, input().split())
T = list(map(int, input().split()))

# 経過した時間
time = 0
# 並んだ人を順番に対応する．
for i in range(N):
  # 経過時間の時点で並んでない場合
  if(time<T[i]):
    # チケットに並び始めた時間まで，時間を早める．
    time = T[i]
  # 時間`A`をかけて対応する．
  time += A
  
  # 経過時間を出力する．
  print(time)

C問題

• それぞれの店に「行く」・「行かない」の2パターンをN回試す．
• それぞれのパターンが2**N回あって，ポップコーンに何味があるかを確認するのに，M回あるので，計算量はO(M*2^N)．これは十分に間に合う．

C.py

"""
<方針>
- それぞれの店に「行く」・「行かない」の2パターンを`N`回試す．
- それぞれのパターンが`2**N`回あって，ポップコーンに何味があるかを確認するのに，`M`回あるので，計算量は`O(M*2^N)`．これは十分に間に合う．
"""
# 標準入力を受け取る．
N, M = map(int, input().split())
SS = []
for i in range(N):
  SS.append(input())

# 答え．最悪のパターンが全ての店を巡ることなので，Nを初期値として，更新を試みる．
ans = N
# 2**Nを全て試す．
for i in range(1<<N):
  # 今回の答え
  tmpAns = 0
  # ポップコーンの味が揃ったかどうかを確認するリスト．
  has = [False]*M
  # どのお店に行くかどうかを確認する．
  for j in range(N):
    # bitをずらして，行くお店を確認する．
    if(i&(1<<j)):
      # お店に行くお店の数を増やす．
      tmpAns += 1
      # お店にあったポップコーンの種類の確認する．
      for k, s in enumerate(SS[j]):
        # ポップコーンにk番目の味があった時，
        if(s=="o"):
          # k番目のポップコーンの味が発見できたことを記録する．
          has[k] = True      
  
  # 全てのポップコーンの味が揃ったかどうかを確認する．
  go = True
  # それぞれ確認する．
  for j in range(M):
    # 一つでも揃ってないと，
    if(not has[j]):
      # Falseにする．
      go = False
  
  # もし，全ての味が揃っていたら，
  if(go):
    # 答えの更新を試みる．
    ans = min(tmpAns, ans)
# 答えを出力する．
print(ans)

D問題

• 貪欲に行こう．
• AとBをそれぞれ小さい順番にソートをする．
• Bを順番に見ていき，Aも順番に見ていく．
• Aの値がBの値をカバーし切れるものが出るまで順番に見ればOK

D.py

"""
<方針>
- 貪欲に行こう．
- `A`と`B`をそれぞれ小さい順番にソートをする．
- `B`を順番に見ていき，`A`も順番に見ていく．
- `A`の値が`B`の値をカバーし切れるものが出るまで順番に見ればOK
"""
# 入力
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# 小さい順にソートして，貪欲に行く．
A.sort()
B.sort()

# 現在，どのAを見ているかを記録する変数．
now = 0
# 答え
ans = 0

# Bを順番に見ていく．
for b in B:
  # Aを全て見ても，Bのループを抜けれなかったとき，
  if(now==N):
    print(-1)
    exit()
  # bを満たすA[now]を探す．
  while True:
    # bを満たすA[now]が見つかったとき，
    if(A[now]>=b):
      break
    # 見つからなかったので，次のA[now]を探す．
    else:
      now += 1
      # Aを全て見てしまったとき，
      if(now==N):
        print(-1)
        exit()
  # 答えの値を増やす．
  ans += A[now]
  # 次のnowを見る．
  now += 1
# 出力
print(ans)

E問題

• 使えるアルファベットの文字数をAから順番に見ていく形でdpを更新する．つまり，最外ループは26回．
• そのループの中で，dpを一つずつ更新する．
• dpはi個新しいアルファベットを，j個の既に並んでるアルファベットに混ぜて並べていく形で更新していく．パターン数は(c+k)!/(c!*k!)となり，dpの値はj個の既に並んでいるアルファベットのパターン数．
• よって，組み合わせのコンビネーションの要領でdpを更新する(new_dp = dp*(c+k)!/(c!*k!))．
• 階乗はあらかじめ計算することで高速化．
• なんか頭回らなくなってきた．意味のわからんこと言ってたらごめん．

E.py

"""
<方針>
- 使えるアルファベットの文字数をAから順番に見ていく形でdpを更新する．つまり，最外ループは26回．
- そのループの中で，dpを一つずつ更新する．
- dpは`i`個新しいアルファベットを，`j`個の既に並んでるアルファベットに混ぜて並べていく形で更新していく．パターン数は`(c+k)!/(c!*k!)`となり，dpの値は`j`個の既に並んでいるアルファベットのパターン数．
- よって，組み合わせのコンビネーションの要領でdpを更新する(`new_dp = dp*(c+k)!/(c!*k!)`)．
- 階乗はあらかじめ計算することで高速化．
- なんか頭回らなくなってきた．意味のわからんこと言ってたらごめん．
"""
K = int(input())
C = list(map(int, input().split()))
MAX = 2000
mod = 998244353

# 階乗をあらかじめ計算しておく．
f = [i for i in range(MAX+1)]
f[0] = 1
for i in range(MAX):
  f[i+1] *= f[i]%mod

# 階乗の逆元も計算しておく．
invF = []
for i in range(MAX+1):
  invF.append( pow(f[i], -1, mod))

# dp．アルファベットを並び替えるパターン数．
# h: h番目のアルファベットを見た時，
# j: アルファベットをj個並べた状態のとき，
dp = [[0]*(K+1) for _ in range(26+1)]

# 0個のアルファベットを並べるのは1パターンだけ存在するものとする．
for i in range(26+1):
  dp[i][0] = 1

# アルファベットをAから順番に見ていく．
for h, c in enumerate(C):
  # 新しいアルファベットをi個使うとする．
  for i in range(c+1):
    # 既に並んでいるアルファベットがj個並んでいるものとする．
    for j in range(K+1):
      # dpの更新が範囲外のときは更新しない．
      if(j+i<=0 or K<j+i):
        continue
      
      # dpを更新する．
      dp[h+1][j+i] += dp[h][j]*f[i+j]*invF[i]*invF[j]%mod

# 総和を1〜Kからでとる．
print(sum(dp[26][1:])%mod)

F問題

• 眠くなってきた．公式解説を見た感じ，方針は似てたので，そんな感じです．
• コメントを参照して頑張ってついてきてください．

F.py

"""
<方針>
- 眠くなってきた．公式解説を見た感じ，方針は似てたので，そんな感じです．
- コメントを参照して頑張ってついてきてください．
"""
N, M, K = map(int, input().split())

# 最短ルートで辿り着けない時，
if(K<N):
  print("No")
  exit()

# 迂回しなきゃいかん分の2回分
di, mo = divmod(K-N, 2)

# 迂回が奇数だから無理
if(mo == 1):
  print("No")
  exit()
  
# 移動可能なマスの数よりも，移動を試みる時，
if(di>(N)*(M-1)//2):
  print("No")
  exit()

# 壁の行のテンプレート
wall = []
for i in range(2*M+1):
  if(i%2==0):
    wall.append("+")
  else:
    wall.append("-")

# 通路の行のテンプレート
road = []
for i in range(2*M+1):
  if(i%2==0):
    road.append(".")
  else:
    road.append("o")
road[0] = "+"
road[-1] = "+"

# Yesを出力する．
print("Yes")

# 最初の行を出力
st = ["+"]*(M+M+1)
st[-2] = "S"
print(*st, sep="")

# 行を一つずつ出力する．
for i in range(N//2):
  # 最初の時以外は
  if(i!=0):
    # 一個前の道との壁を生成する．
    ls = wall[:]
    ls[-2] = "."
    print(*ls, sep="")
  
  # 迂回するマスの数．
  wind = 0
  # 迂回するマスの数が今回の2行で足りる時，
  if(di-(M-1)<0):
    # di残った分だけやる
    wind = di
    di = 0
  # 迂回するマスの数が今回の2行以上必要なとき，
  else:
    # diをひたすらやる．
    wind = M-1
    di-=M-1
  
  # 2行分の道とその間の壁を作成する．
  r = road[:]
  w = wall[:]
  w[-2*(wind+1)] = "." # 間の壁の穴を開ける．
  # 2行を部分的に迂回する時，
  if(wind!=M-1):
    # 使わない分は壁をつける．
    r[-(2*wind+1+2)] = "|"
  
  # 1つ目の道と壁だけ出力する．
  print(*r, sep="")
  print(*w, sep="")
  # 最後の道とかつ，Nが奇数のとき，
  if(i==(N//2 - 1) and N%2==1):
    # 1つ目の壁を2つに分割し，その間に壁を作る．
    r1 = road[:]
    w = wall[:]
    r2 = road[:]
    
    # 壁の一番右に穴を開ける．
    w[-2] = "."
    
    # Mの大きさが1以外の時は，壁を作る．
    if(M!=1):
      r2[-3] = "|"
      
    # 最後の足りない迂回を最下の行を利用して行う．
    for j in range(di):
      r1[2+4*j] = "|"
      w[2+4*j+1] = "."
      w[2+4*j-1] = "."
      r2[4+4*j] = "|"
    
    # 最初の1つ目の壁と，分割した壁のうち，最初の壁の壁を一部対応させる．
    for j in range(len(r)):
      if(r[j]=="|"):
        r1[j] = "|"
    
    # 道と壁を出力する．
    print(*r1, sep="")
    print(*w, sep="")
    print(*r2, sep="")
  # 通常時は，
  else:
    # 2つ目の壁をそのまま出力する．
    print(*r, sep="")
  
# 最後の行を出力
ed = ["+"]*(M+M+1)
ed[-2] = "G"
print(*ed, sep="")

G問題

• 公式解説と同じ考え方です．
• ただ，dpはそれぞれのマスにおけるmin(K, H*W)回行動をした後の楽しさの最大値としてます(移動することも留まることも可能)．

G.py

"""
<方針>
- 公式解説と同じ考え方です．
- ただ，`dp`はそれぞれのマスにおける`min(K, H*W)`回行動をした後の楽しさの最大値としてます(移動することも留まることも可能)．
"""
H, W, K = map(int, input().split())
S = list(map(int, input().split()))
AA = [list(map(int, input().split())) for i in range(H)]

# dp: 楽しさの最大値．-1の時は，辿り着けていないことを示す．
## i: 行
## j: 列
dp = [[-1]*W for _ in range(H)]

# 開始する位置を定義
dp[S[0]-1][S[1]-1] = 0

# 行動する．
for _ in range(min(K, H*W)):
  # 行動した後のdp
  newDp = [[-1]*W for _ in range(H)]
  for i in range(H):
    for j in range(W):
      # 辿り着けている時，
      if(dp[i][j] != -1):
        for y, x in [
          # 留まる
          (i, j), 
          # 上下左右への移動
          (i+1, j), 
          (i-1, j), 
          (i, j+1), 
          (i, j-1), 
          ]:
            # マスが存在する時，
            if(0<=y<H and 0<=x<W):
              # dpを更新する．
              newDp[y][x] = max(newDp[y][x], dp[i][j]+AA[y][x])
  # dpを書き換える．
  dp = newDp

ans = 0
for i in range(H):
  for j in range(W):
    # 余剰分を足す．
    ans = max(ans, dp[i][j]+AA[i][j]*max(K-H*W, 0))
    
print(ans)

補足

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

• 今回のコンテスト
• F問題の公式解説
• G問題の公式解説

筆者について

• Atcoderアカウント
• 今回の成績(ooooxox)
• 解説で示したA問題の提出
• 解説で示したB問題の提出
• 解説で示したC問題の提出
• 解説で示したD問題の提出
• 解説で示したE問題の提出
• 解説で示したF問題の提出
• 解説で示したG問題の提出

その他

• 間違いを含んでいる可能性があります．
• 方針と言いつつ，方針ではない感想などを書いている可能性があります．
• A問題から解説がだんだん省略されます．
• コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．

最後に一言

• 全部復習(笑)してみた！！