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

# 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問題
- [参考](https://atcoder.jp/contests/abc357/submissions/54360955)
- 俺が本番で書いたコードは汚すぎて終わってるので，「競技プログラミングをするフレンズ」さんのコードを参考に解説します．
- 計算量など気にせずに再帰的にただ実装するだけです．
```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問題
- [参考](https://x.com/kyopro_friends/status/1799437970312949926)
- [参考](https://betrue12.hateblo.jp/entry/2020/09/22/194541)
- 遅延セグメント木を使う．
- 実体の情報として，「加算された回数」・「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])
```

# 補足
### 関係するリンク(参考文献など)
- [今回のコンテスト](https://atcoder.jp/contests/abc357)
- [競技プログラミングをするフレンズさんのC問題の提出](https://atcoder.jp/contests/abc357/submissions/54360955)
- [競技プログラミングをするフレンズさんのTwitter(新X)の解説](https://x.com/kyopro_friends/status/1799437970312949926)
- [ACLの遅延セグメント木の使い方](https://betrue12.hateblo.jp/entry/2020/09/22/194541)
### 筆者について
- [Atcoderアカウント](https://atcoder.jp/users/mattsunkun)
- [今回の成績(ooooxx-)](https://atcoder.jp/users/mattsunkun/history/share/abc357)
- [解説で示したA問題の提出](https://atcoder.jp/contests/abc357/submissions/54402523)
- [解説で示したB問題の提出](https://atcoder.jp/contests/abc357/submissions/54402594)
- [解説で示したC問題の提出](https://atcoder.jp/contests/abc357/submissions/54402775)
- [解説で示したD問題の提出](https://atcoder.jp/contests/abc357/submissions/54403240)
- [解説で示したE問題の提出](https://atcoder.jp/contests/abc357/submissions/54403772)
- [解説で示したF問題の提出](https://atcoder.jp/contests/abc357/submissions/54402345)
### その他
- **間違いを含んでいる可能性があります．**
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
### 最後に一言
- 厳しい2週間を乗り越えました(前回と前々回の記事参照)．
- 次は院試です．応援してください．