LoginSignup
9
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@mattsunkun

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

Posted at

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

A問題

  • 手を順番に洗っていき，洗ったら消毒液の残り回数が負になった時に，現在の0-indexedの値を返す．
  • 全員手を洗えたら，人数Nを出力する．
A.py
"""
<方針>
- 手を順番に洗っていき，洗ったら消毒液の残り回数が負になった時に，現在の0-indexedの値を返す．
- 全員手を洗えたら，人数`N`を出力する．
"""
# 標準入力を受け取る
N, M = map(int, input().split())
H = list(map(int, input().split()))

# 宇宙人に手を順番に洗わせる．
for i in range(N):
  # i番目の宇宙人に手を洗わせる
  M -= H[i]
  # 消毒液が負になった時(本来洗えない状態)，
  if(M<0):
    # 0-indexedを出力することで，現在の宇宙人をカウントせずに，人数を出力する．
    print(i)
    # プログラムを終了する．
    exit()
# 全員洗えた時は，全体の人数を出力する．
print(N)

B問題

  • 大文字と小文字の個数を数える．
  • その個数の大小で全体を大文字にするor小文字にする．
B.py
"""
<方針>
- 大文字と小文字の個数を数える．
- その個数の大小で全体を大文字にするor小文字にする．
"""
S = input()

# 大文字の個数
u = 0
# 小文字の個数
l = 0

# 文字を一つずつみる．
for s in S:
  # 文字が小文字のとき
  if s.islower():
    # 小文字の個数を増やす
    l += 1
  else:
    # 大文字の個数を増やす．
    u += 1

# 大文字の方が多い時，
if(u>l):
  # 全て大文字にする．
  print(S.upper())
else:
  # 全て小文字にする．
  print(S.lower())

C問題

  • 参考
  • 俺が本番で書いたコードは汚すぎて終わってるので，「競技プログラミングをするフレンズ」さんのコードを参考に解説します．
  • 計算量など気にせずに再帰的にただ実装するだけです．
C.py
"""
<方針>
- [参考](https://atcoder.jp/contests/abc357/submissions/54360955)
- 俺が本番で書いたコードは汚すぎて終わってるので，「競技プログラミングをするフレンズ」さんのコードを参考に解説します．
- 計算量など気にせずに再帰的にただ実装するだけです．
"""
N=int(input()) # 標準入力
N3=pow(3,N) # 3のN乗
ans=[["."]*N3 for _ in range(N3)] # 最初に全ての盤面を白で塗り尽くす．

# 再帰的に実行する．
def f(i,j,N3):
  # N3==1, つまり，N==0のとき，
  if N3==1:
    # 黒に塗る．また，(i, j)の位置は左上なので，黒に塗って問題ない．
    ans[i][j]="#"
  else:
    # 領域を縦と横それぞれ3分割し，全体で9分割する．
    N3//=3
    # 縦方向の分割
    for ii in range(3):
      # 横方向の分割
      for jj in range(3):
        # 真ん中の領域のところは白のままで良い．
        if ii==1 and jj==1: continue
        # 領域を再帰的に塗る．
        f(i+N3*ii,j+N3*jj,N3)

# 色を塗る．Pythonのリストがオブジェクト管理なので，問題無い．
f(0,0,N3)

# リスト状になっている答えを出力する．
for row in ans:
  # 区切りなしで文字を出力する．
  print("".join(row))

D問題

  • $V_N$は，$a_0=N$, $r=10^L$とした等比級数になっている．
  • 従って，$V_N=N\frac{(10^L)^N-1}{(10^L-1)}$となる．
  • ビルトインのpowは対数を利用して高速であるため(たぶん)，いける．
D.py
"""
<方針>
- $V_N$は，$a_0=N$, $r=10^L$とした等比級数になっている．
- 従って，$V_N=N\frac{(10^L)^N-1}{(10^L-1)}$となる．
- ビルトインの`pow`は対数を利用して高速であるため(たぶん)，いける．
"""

N = int(input()) # 入力
mod = 998244353 # mod
L = len(str(N)) # 桁数
a = N%mod # 初項
r = pow(10, L, mod) # 等比
nu = a*(pow(r, N, mod)-1) # V_Nの分子
de = r-1 # V_Nの分母
invDe = pow(de, -1, mod) # V_Nの分母の逆数
ans = (nu*invDe)%mod # 答え
print(ans)

E問題

  • 特定のノードから移動していけば，必ず閉路でループします．
  • ループ構造を成しているノードの数が，そのループ内のノードの到達できるノードの数になる．
  • 閉路を発見した時，そこから遡及して，通ったノードそれぞれから到達できるノードの個数をメモする．
  • もし，ノードの到達できる数がメモされていたら，そのメモを利用する．
E.py
"""
<方針>
- 特定のノードから移動していけば，必ず閉路でループします．
- ループ構造を成しているノードの数が，そのループ内のノードの到達できるノードの数になる．
- 閉路を発見した時，そこから遡及して，通ったノードそれぞれから到達できるノードの個数をメモする．
- もし，ノードの到達できる数がメモされていたら，そのメモを利用する．
"""
N = int(input())
A = list(map(int, input().split()))

# そのノードが到達できるノードの数
S = [0]*N
# ノードが移動したルートを記録するもの．記録を使ったら，値を-1にして，破棄する．
## 値が-1であれば，そのルートを辿ってない．開始した場所が0になり，そこ以降のノードは1, 2, 3... となる．
T = [-1]*N
# ノード一つ一つから辿っていく．
for now in range(N):
  # 既に，到達できるノードの数がわかってる時は，走らせない．
  if(S[now]!=0):
    continue
  # 辿ったノードのインデックスを記録する配列
  R = []
  # 変数Tの値に書き込むもの．何番目に訪れたか
  vis = 0
  # ノードを順番に訪れていく．
  while True:
    # 既に，到達できるノード数がわかっているor閉路を見つけた時，breakする．
    if(S[now]!=0 or T[now]!=-1):
      break
    
    # Tに何番目に訪れたかを記録する．
    T[now] = vis
    # 辿ったノードのインデックスを記録する．
    R.append(now)
    # 次のノードに移動する．
    now = A[now]-1
    # 変数Tに記入するものをインクリメントする．
    vis += 1
  
  # 閉路を成しているノードの数
  loop = len(R)-T[now]
  # ノードを順番に訪れるのを終了したのは，メモが用意されているのが理由の時，Trueになる．
  memo = (S[now]!=0)
  # ノードを訪れた回数-1
  lastT = T[now]
  for j in range(len(R)):
    # 後ろから順番に訪れた場所を取得する．
    r = R[len(R)-1-j]
    # ループを抜け出したのが，メモが用意されていたのが理由な時，
    if(memo):
      # 訪れる回数を，メモから順番にインクリメントして，入力する．
      S[r] = S[now]+j+1
    # ループを抜け出したのが，閉路があったのが理由な時，
    else:
      # ノードが閉路を成しているとき，
      if(lastT<=T[r]):
        # 閉路を成しているノードの数を入力する．
        S[r] = loop
      # ノードが閉路を成していない時，
      else:
        # 閉路を成しているノードの数から順番にインクリメントしたものを入力する．
        S[r] = loop + lastT-T[r]
    
    # 使わなくなった訪れた順番は-1にして，初期化する．
    T[r] = -1

# ノードが訪れることのできる回数の総和
print(sum(S))

F問題

  • 参考
  • 参考
  • 遅延セグメント木を使う．
  • 実体の情報として，「加算された回数」・「Aの和」・「 Bの和」・「(A, B)の内積」を乗せる
  • 遅延の情報は，「Aの和」・「Bの和」とする．
F.py
"""
<方針>
- [参考](https://x.com/kyopro_friends/status/1799437970312949926)
- [参考](https://betrue12.hateblo.jp/entry/2020/09/22/194541)
- 遅延セグメント木を使う．
- 実体の情報として，「加算された回数」・「Aの和」・「 Bの和」・「(A, B)の内積」を乗せる
- 遅延の情報は，「Aの和」・「Bの和」とする．
"""
from atcoder.lazysegtree import LazySegTree
mod = 998244353

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

# 実体同士の評価
def op(S, T):
  sL, sA, sB, sAB = S
  tL, tA, tB, tAB = T
  return (sL+tL, (sA+tA)%mod, (sB+tB)%mod, (sAB+tAB)%mod)
  
# 実体の単位
ele = (0, 0, 0, 0)

# 遅延と実体の評価
def ma(F, S):
  sL, sA, sB, sAB = S
  fA, fB = F
  return (sL, (sA+fA*sL)%mod, (sB+fB*sL)%mod, (sAB+sA*fB+sB*fA+sL*fA*fB)%mod)
  
# 遅延同士の評価
def co(F, G):
  fA, fB = F
  gA, gB = G
  return ((fA+gA)%mod, (fB+gB)%mod)
  
# 遅延の単位
ide = (0, 0)

# 初期値
lst = [(1, a, b, a*b%mod) for a, b in zip(A, B)]

# セグ木の初期化
dp = LazySegTree(op, ele, ma, co, ide, lst)

# クエリごとの処理
for _ in range(Q):
  q = list(map(int, input().split()))
  match q:
    case [1, l, r, x]:
      dp.apply(l-1, r, (x, 0))
    case [2, l, r, x]:
      dp.apply(l-1, r, (0, x))
    case [3, l, r]:
      print(dp.prod(l-1, r)[3])

補足

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

筆者について

その他

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

最後に一言

  • 厳しい2週間を乗り越えました(前回と前々回の記事参照)．
  • 次は院試です．応援してください．
9
2
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
9
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?