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

A問題

Sの文字を一文字ずつ見ていく．
Sの一つずつの文字を答えに追記するかどうかのフラグcutを用意する．Falseの時に追記する．初期値はFalseとする．
パイプ(|)が初めて出た瞬間からは，答えに文字を追記しない．つまり，フラグをFalse->Trueとする．
パイプ(|)を2回目に見てからは，答えに文字を追記する．つまり，フラグをTrue->Falseとする．
つまり，パイプ(|)を見たら，答えに文字を追記するかどうかのフラグを反転させれば良い．

A.py

"""
<方針>
- Sの文字を一文字ずつ見ていく．
- Sの一つずつの文字を答えに追記するかどうかのフラグcutを用意する．Falseの時に追記する．初期値はFalseとする．
- パイプ(|)が初めて出た瞬間からは，答えに文字を追記しない．つまり，フラグをFalse->Trueとする．
- パイプ(|)を2回目に見てからは，答えに文字を追記する．つまり，フラグをTrue->Falseとする．
- つまり，パイプ(|)を見たら，答えに文字を追記するかどうかのフラグを反転させれば良い．
"""

# 標準入力受け取り
S = input()

# 不要な文字の時にTrueになっているフラグ
cut = False
# 答え．Sを一つずつ見て，追記していく．
ans = ""

# Sを一つずつ前から見ていく
for s in S:
  
  # 文字がパイプ(|)だったときに，フラグを反転させる．
  if(s=="|"):
    cut = not cut
  # ここをelifではなく，ifにすると，答えにパイプ(|)が含まれてしまう．
  elif(not cut):
    # フラグがFalseのとき，文字を追記する．
    ans += s

# 答えを出力
print(ans)

B問題

入力を1行ずつ受け取る．その際，try~catchを使って，エラーハンドリングする．
エラーをキャッチしたら，一行ずつ受け取るのをやめる．
受け取った入力を逆順に出力する．

B.py

"""
<方針>
- 入力を1行ずつ受け取る．その際，try~catchを使って，エラーハンドリングする．
- エラーをキャッチしたら，一行ずつ受け取るのをやめる．
- 受け取った入力を逆順に出力する．
"""

# 入力を一時的に格納する配列．
sta = []

# エラーが起きるまで入力を受け取り続ける．
while True:
  try:
    # 入力を受け取る．
    s = input()
    # 入力を一時的に格納する．
    sta.append(s)
  except Exception as e:
    # 入力受け取りに失敗(つまり，受け取れる入力がなくなった)した時，無限ループから脱出する．
    break
  
# 入力を逆順に出力する．
for i in range(len(sta)):
  # 逆順に出力
  print(sta[len(sta)-i-1])

C問題

Xの要素一つずつに対して，毎回A, B, Cから一つずつ選んで，合致するか調べていては計算量がO(NMLQ)になり(NMLQ=10^11)，TLEする．
Xの値に依らず(つまり，X1, X2だろうと)，A, B, Cから一つずつ選んで，作った和の種類は全部一緒である．
では，最初からA, B, Cから一つずつ選んで作った和の種類は計算しておこう(O(NML)で間に合う)．
あらかじめ計算した和をlist(もしくはarray)ではなく，setに持たせる必要がある．
値の存在判定において，list(もしくはarray)を使うとO(NML)の時間になってしまうため，全体の計算量はO(NMLQ)となってしまい，TLEする．
しかし不思議なことに，setをを使うとO(1)となり，全体の計算量はO(NML+Q)となり間に合う．

C.py

"""
<方針>
- Xの要素一つずつに対して，毎回A, B, Cから一つずつ選んで，合致するか調べていては計算量がO(NMLQ)になり(NMLQ=10^11)，TLEする．
- Xの値に依らず(つまり，X1, X2だろうと)，A, B, Cから一つずつ選んで，作った和の種類は全部一緒である．
- では，最初からA, B, Cから一つずつ選んで作った和の種類は計算しておこう(O(NML)で間に合う)．
- あらかじめ計算した和をlist(もしくはarray)ではなく，setに持たせる必要がある．
- 値の存在判定において，list(もしくはarray)を使うとO(NML)の時間になってしまうため，全体の計算量はO(NMLQ)となってしまい，TLEする．
- しかし不思議なことに，setをを使うとO(1)となり，全体の計算量はO(NML+Q)となり間に合う．
"""
# 標準入力受け取り
N = int(input())
A = list(map(int, input().split()))
M = int(input())
B = list(map(int, input().split()))
L = int(input())
C = list(map(int, input().split()))
Q = int(input())
X = list(map(int, input().split()))

# A, B, Cの和を格納するset
se = set()

## この3重ループの計算量はO(NML)
# Aの候補
for i in range(N):
  # Bの候補
  for j in range(M):
    # Cの候補
    for k in range(L):
      # setに格納する．
      se.add(A[i]+B[j]+C[k])
      
## このループの計算量はO(Q)
for i in range(Q):
  # Xの値を取得する．
  q = X[i]
  # qがA, B, Cの和の候補に存在するか．(この計算量は不思議なことにO(1))
  if(q in se):
    print("Yes")
  else:
    print("No")

D問題

dpを愚直に構築し，愚直に遷移する．それでも計算時間は間に合う．
dpの詳細→行動iをした後に，Tのj番目の文字までが合致するものを作れた時に，支払ったお金の最小値

D.py

"""
<方針>
- dpを愚直に構築し，愚直に遷移する．それでも計算時間は間に合う．
- dpの詳細→行動iをした後に，Tのj番目の文字までが合致するものを作れた時に，支払ったお金の最小値
"""
# 標準入力受け取り
T = input()
N = int(input())
SS = []
for i in range(N):
  a, *S = map(str, input().split())
  SS.append(S)
  

# お金の支払いの最大値は100なので，1000は自明に大きい値である．
INF = 1000
# dp[i][j]とは，行動iをした後に，Tのj番目の文字までが合致するものを作れた時に，お金を支払った最小値である．
# iは(0~N)をとる．iの袋を選択した後のこと．0は初期値である．
# jはTのj番目の文字まで合致することができた時のこと．0の時は自明にdpに0が格納される．
dp = [[INF]*(len(T)+1) for i in range(N+1)]

# jの値が0の時は自明にdpに0が格納される．
for i in range(N+1):
  dp[i][0] = 0

# 行動i+1を順番に行う．(0<=i<N)
for i in range(N):
  # 行動i+1でとれる袋を取得
  S = SS[i]
  # 行動i+1でとれる袋の中身を一つずつ取得
  for s in S:
    # 行動"i"が終わっている時に，Tのj文字目まで文字を合致できていた前提で，文字の追記を試みる．
    for j in range(len(T)+1):
      # j文字目から順番にsの文字を比較していく．合致していない文字があったら，このokフラグはFalseとなる．
      ok = True
      # j文字目からsの文字を比較していく．
      for k in range(len(s)):
        # j文字目からsの文字を追記したら，Tの最大文字数を超えたとき，
        if(j+k>=(len(T))):
          # okフラグを折る．
          ok = False
          break
        # j文字目からsを追記し，j+k番目の文字が合致しない時，
        if(T[j+k] != s[k]):
          # okフラグを折る．
          ok = False
          break
      # 文字が合致していたら，dpを遷移する．
      if(ok):
        dp[i+1][j+len(s)] = min(dp[i+1][j+len(s)], dp[i][j]+1)
  
  # 行動i+1にて，どの文字も選ばないパターンもあるので，行動"i"の時のテーブルと比較して更新する．
  for j in range(len(T)+1):
    dp[i+1][j] = min(dp[i+1][j], dp[i][j])


# Tという文字にするのにかかった最小コスト
ans = dp[N][len(T)]

# Tという文字が実現不可能な時
if(ans == INF):
  ans = -1


print(ans)

E問題

数列に対して，あるところに挿入，あるところを削除しか行わない．
毎回のクエリに対して，一瞬で前述のことができれば良い．別に全体の数列をすぐ出力できる必要はない．
それぞれの数列の要素が左右にどんな要素を持つかを保持すれば良い．
ただし，一番左は-1とし，便宜上その左の要素も-1とする．一番右は-2とし，便宜上その右の要素も-2とする．
最後に数列を構築する計算量も考慮して，計算量はO(Q+N)となる．

E.py

"""
<方針>
- 数列に対して，あるところに挿入，あるところを削除しか行わない．
- 毎回のクエリに対して，一瞬で前述のことができれば良い．別に全体の数列をすぐ出力できる必要はない．
- それぞれの数列の要素が左右にどんな要素を持つかを保持すれば良い．
- ただし，一番左は-1とし，便宜上その左の要素も-1とする．一番右は-2とし，便宜上その右の要素も-2とする．
- 最後に数列を構築する計算量も考慮して，計算量はO(Q+N)となる．
"""
N = int(input())
tmpA = list(map(int, input().split()))


# 数列の初期値
A = [-1] # 最左は-1
for i in range(N):
  A.append(tmpA[i])
A.append(-2) # 最右は-2


# keyを数列の値とし，そのvalueを(その左の値, その右の値)とする，連想配列
di = {}
di[-1] = (-1, A[1]) # 最左
for i in range(1, N+1):
  di[A[i]] = (A[i-1], A[i+1]) # 真ん中
di[-2] = (A[N], -2) # 最右

# 毎回のクエリ
Q = int(input())
for i in range(Q):
  
  fla, *other = map(int, input().split())
  
  # 挿入
  if(fla==1):
    x, y = other
    
    pasL, pasR = di[x] # 前回のxの左右を取得
    di[x] = (pasL, y) # 新しいxの左右を設定
    di[y] = (x, pasR) # yの左右を設定
    di[pasR] = (y, di[pasR][1]) # 前回のxの右の左右を設定
  # 削除
  else:
    x = other[0]
    
    pasL, pasR = di[x] # 前回のxの左右を取得
    di[pasL] = (di[pasL][0], pasR) # 前回のxの左の左右を設定
    di[pasR] = (pasL, di[pasR][1]) # 前回のxの右の左右を設定
    
# 数列を構築して出力する．
now = di[-1][1] # 最左は-1なので，その右の要素が出力したい値としての最左
ans = [now] # 答えに格納
# 数列を構築
while True:
  # 右の値を取得
  _, r = di[now]
  # 最右に到達したときbreak
  if(r==-2):
    break
  # 値を答えに格納
  ans.append(r)
  # 次の探索する値
  now = r
  

print(*ans)

F問題

公式解説にあるように，お金を最も効率よくチャージする方法は今まで経由してきた中で一番お金を大きくチャージできるところでチャージすること．
それぞれのマスには最悪N^2パターンのチャージパターン額が入っているので，マス目がN^2個あることを考慮するとO(N^4)となる．
dpにはお金のチャージ額とお金をチャージした回数と現在持っているお金があれば良い．

F.py

"""
<方針>
- 公式解説にあるように，お金を最も効率よくチャージする方法は今まで経由してきた中で一番お金を大きくチャージできるところでチャージすること．
- それぞれのマスには最悪N^2パターンのチャージパターン額が入っているので，マス目がN^2個あることを考慮するとO(N^4)となる．
- dpにはお金のチャージ額とお金をチャージした回数と現在持っているお金があれば良い．
"""

N = int(input())
PP = []
for i in range(N):
  PP.append(list(map(int, input().split())))

RR = []
for i in range(N):
  RR.append([-1]+list(map(int, input().split()))) # 最左をパディングしている．
  
DD = [[-1]*N] # 最上をパディングしている．
for i in range(N-1):
  DD.append(list(map(int, input().split())))
  
INF = 10**20
# dpの値には(経由した中で一番お金を稼げる場所でお金をチャージした回数, 現在持っているお金の符号を反転したもの)が入っている．
# 現在のお金の額を反転させているのは，大小比較を簡単にするため(Pythonの都合)
# dp[i][j][maxP]の添字について解説する．
# i: i行目
# j: j列目
# maxP: 経由した道の中でチャージできる最大金額

# dp初期化
dp = [[dict() for j in range(N)] for i in range(N) ]
        
        
# 初期値
dp[0][0][PP[0][0]] = (0, -0)

for i in range(N):
  for j in range(N):
    if(i-1>=0):
      # 右方向の更新
      for k, v in dp[i-1][j].items():
        p = k
        c, m = v
        m = -m
        e = DD[i][j]
        t = max(((e-m)+p-1)//p, 0)

        # p: 送り元dpにおける一度でチャージできるお金の最大額
        # c: 送り元dpにおける既にチャージした回数
        # m: 送り元dpから更新したいdpに移動する前の所持金
        # e: 送り元dpから更新したいdpに移動するのに必要なお金
        # t: 送り元dpから更新したいdpに移動するのに必要な最小追加チャージ回数
        
        # (一度でチャージできるお金を最大額が更新したいdpの連想配列のキーに「無い」とき)
        # or
        # (更新したいdpに既に入っている(チャージ回数, 所持金の符号反転)よりも今回のdp遷移による値(t+c, -(t*p-e+m))の方が小さいとき)
        if not (max(p, PP[i][j]) in dp[i][j]) or (dp[i][j][max(p, PP[i][j])] > (t+c, -(t*p-e+m))):
          # 更新
          dp[i][j][max(p, PP[i][j])] = (t+c, -(t*p-e+m))
          
    if(j-1>=0):
      # 下方向の更新(右方向の更新と考え方は変わりません)
      for k, v in dp[i][j-1].items(): # dpの添字が右方向と違う
        p = k
        c, m = v
        m = -m
        e = RR[i][j] # ここが右方向の更新と比べてRR[i][j]になっている
        t = max(((e-m)+p-1)//p, 0)
        
        if not (max(p, PP[i][j]) in dp[i][j]) or (dp[i][j][max(p, PP[i][j])] > (t+c, -(t*p-e+m))):
          dp[i][j][max(p, PP[i][j])] = (t+c, -(t*p-e+m))
    
 # チャージした回数
ans = min(dp[N-1][N-1].items(), key=lambda x: x[1][0])
# 移動は必ず2*(N-1)回ちょうどするので，それを足して出力
print(ans[1][0]+(2*(N-1)))

補足

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

筆者について

その他

間違いを含んでいる可能性があります．
方針と言いつつ，方針ではない感想などを書いている可能性があります．
A問題から解説がだんだん省略されます．

最後に一言

絶対acだと思うのに，waくらった時は一回コードを再構築すると良いことを学びました．