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

Posted at 2025-01-11

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

A問題

スライス [0] を用いて入力の先頭を取得する．
文字列を + で結合する．

A.py

"""
<方針>
- スライス `[0]` を用いて入力の先頭を取得する．
- 文字列を `+` で結合する．
"""
# 入力
S = input()

# 頭の文字
head = S[0]
# 結合
ans = head + "UPC"

# 出力
print(ans)

B問題

🐍それぞれの現在の重さを管理する変数 W を作成する．
D 回🐍それぞれの重さ W を🐍それぞれの太さ T を用いて更新する．
その時の🐍の一番重たいやつを出力する．

B.py

"""
<方針>
- 🐍それぞれの現在の重さを管理する変数 `W` を作成する．
- `D` 回🐍それぞれの重さ `W` を🐍それぞれの太さ `T` を用いて更新する．
- その時の🐍の一番重たいやつを出力する．
"""
# 入力
N, D = map(int, input().split())
T = [] # 太さ
L = [] # 長さ
W = [] # 重さ
for _ in range(N):
  t, l = map(int, input().split())
  T.append(t) # 太さ
  L.append(l) # 長さ
  W.append(t*l) # 重さ

# D回伸ばす
for _ in range(D):
  # 蛇全員の重さを更新する
  for i in range(N):
    W[i] += T[i] # 太さを用いて重さを更新
  
  # 現在一番重たいやつを出力する．
  print(max(W))

C問題

方針

全ての組み合わせをフルメッシュで確認していたら，O(N^2) となってしまい，当然間に合わない．
なので，土台 a を固定して，上にセットできるやつがいくつあるかを効率よく探したい．
大きさが小さい順に並んでいるので，二分探索で見つけていけば良い．
- めぐる式二分探索を組めるようになるとバグらせにくい．
二分探索なので，O(logN) より，全体として，O(NlogN) で解くことができる．

前提

C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう．
AとB問題では，基本的に制約条件を見ずにやっても解ける．
しかし，C問題以降では，制約条件を見ないと必ずTLEすると思っても良い．
詳しい話は私の352回の記事のC問題の解説に記したので，是非参照してほしい．

C.py

"""
<方針>
- 全ての組み合わせをフルメッシュで確認していたら，`O(N^2)` となってしまい，当然間に合わない．
- なので，土台 `a` を固定して，上にセットできるやつがいくつあるかを効率よく探したい．
- 大きさが小さい順に並んでいるので，二分探索で見つけていけば良い．
  - めぐる式二分探索を組めるようになるとバグらせにくい．
- 二分探索なので，`O(logN)` より，全体として，`O(NlogN)` で解くことができる．
"""
# 入力
N = int(input())
A = list(map(int, input().split()))


ans = 0 # 組み合わせの総数
# 土台を固定する．
for a in A:
  
  # めぐる式二分探索．詳しくはググってみてください．
  ok = -1 # 上に乗っけられる最大のindex
  ng = N # 乗っけられないやつ
  while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if(A[mid]<=a//2):
      ok = mid
    else:
      ng = mid
  
  # 個数を登録
  ans += (ok + 1)

# 出力
print(ans)

D問題

線形時間で解く方法を考えると，年をとる左の人から順番に石の最終的な数を考えれば良さそう．
そのためには，石がもらえなくなる数を保持する lost と，いつから石がもらえなくなるかの when を用意する．
i 番目の人の具体的な計算方法
- まず，石がもらえなくなる数を更新するので，lost += when[i] とする．
- その人は，earn = i - lost の石を左の人からもらえる．
- その人は，自分の石が途中でなくならなければ，give = N - 1 -i の意思を右の人に渡す．
- なので，その人が持っている最終的な石の数は，b = A[i] + take - give になる．
- もし，b が負の値になれば，b を 0 にし，when[N+b] += 1 として，自分の石が 0 になるタイミングを記録する．

D.py

"""
<方針>
- 線形時間で解く方法を考えると，年をとる左の人から順番に石の最終的な数を考えれば良さそう．
- そのためには，石がもらえなくなる数を保持する `lost` と，いつから石がもらえなくなるかの `when` を用意する．
- `i` 番目の人の具体的な計算方法
  - まず，石がもらえなくなる数を更新するので，`lost += when[i]` とする．
  - その人は，`earn = i - lost` の石を左の人からもらえる．
  - その人は，自分の石が途中でなくならなければ，`give = N - 1 -i` の意思を右の人に渡す．
  - なので，その人が持っている最終的な石の数は，`b = A[i] + take - give` になる．
  - もし，`b` が負の値になれば，`b` を `0` にし，`when[N+b] += 1` として，自分の石が `0` になるタイミングを記録する．
"""
# 入力
N = int(input())
A = list(map(int, input().split()))

lost = 0 # 石がもらえなくなった個数
when = [0]*N # いつ石がもらえなくなるか
B = [] # 答え
# 左から順番に見る
for i in range(N):
  # 石の数を更新
  lost += when[i]
  # 受け取る石の個数
  take = i - lost
  # できれば与えたい石の個数
  give = N - 1 - i
  # 最終的な石の数(負の値を許容)
  b = A[i] + take - give
  
  # 石の数が負の値の時，
  if(b<0):
    # 自分の石を失うタイミングを記録する．
    if(0<=N+b<=N-1):
      when[N+b] += 1
    # 石の個数を本当の値である，0にする．
    b = 0
  
  # 答えに記録
  B.append(b)

# 出力
print(*B)

E問題

K 個の鏡餅を作成するときは，前からと後ろからで K 個ずつ作成するパターンさえ試せば十分である．
適切な K を二分探索で調べれば良い．
全体の計算量は，O(NlogN)

E.py

"""
<方針>
- `K` 個の鏡餅を作成するときは，前からと後ろからで `K` 個ずつ作成するパターンさえ試せば十分である．
- 適切な `K` を二分探索で調べれば良い．
- 全体の計算量は，`O(NlogN)`
"""
# 入力
N = int(input())
A = list(map(int, input().split()))

# 二分探索
ok = 0
ng = N//2 + 1
while abs(ok-ng)>1:
  mid = (ok+ng)//2
  K = mid
  flag = True # 鏡餅がK個作れる時はTrueである．
  # 前後からK個順番に取ってくる
  for top, bottom in zip(A[:K], A[-K:]):
    # 鏡餅が作れない時，
    if (top>bottom//2):
      # 作れないフラグを立てる
      flag = False
  
  # 鏡餅が作れるかどうか
  if(flag):
    ok = mid
  else:
    ng = mid

# 出力
print(ok)

補足

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

今回のコンテスト

筆者について

その他

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

最後に一言

友人に勧められて，独学大全を部分的に読んでいます．

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up