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

A問題

入力を list(str) で受け取る．
数字がそれぞれ何回ずつ現れたかをカウントする． cnt
題意を満たせば Yes

A.py

"""
<方針>
- 入力を `list(str)` で受け取る．
- 数字がそれぞれ何回ずつ現れたかをカウントする． `cnt`
- 題意を満たせば `Yes`
"""
# 入力
N =list(str(input()))

# カウントを保持
cnt = [0]*10

# 数字を見る
for n in N:
  # 数値になおす
  n = int(n)
  # カウントする
  cnt[n] += 1

# 条件を満たすかどうか．
if cnt[1]==1 and cnt[2]==2 and cnt[3] == 3:
  print("Yes")
else:
  print("No")

B問題

split() メソッドを使って， | で区切れば，出力すべき数字が見えてくる．
ただし，前後は削る必要があるので，スライス [1:-1] を使う．

B.py

"""
<方針>
- `split()` メソッドを使って， `|` で区切れば，出力すべき数字が見えてくる．
- ただし，前後は削る必要があるので，スライス `[1:-1]` を使う．
"""
# 入力
S = input()

# | で分割
S_split = S.split("|")

# 答えを保持するリスト
ans = []
for s in S_split[1:-1]:
  # -の数をカウント
  A = s.count("-")
  # 答えに追加
  ans.append(A)

# アンパックして出力
print(*ans)

C問題

方針

塊を一つずつ動かしていたら， O(N^2) かかってしまう．
塊をまとめて動かして仕舞えば， O(N) でいける．
まず，塊の開始位置と塊を形成する数を記録する変数 clusters を作成する．
K 番目の位置を 0 にする．
K-1 番目の位置を 1 にする．

前提

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

C.py

"""
<方針>
- 塊を一つずつ動かしていたら， `O(N^2)` かかってしまう．
- 塊をまとめて動かして仕舞えば， `O(N)` でいける．
- まず，塊の開始位置と塊を形成する数を記録する変数 `clusters` を作成する．
- `K` 番目の位置を `0` にする．
- `K-1` 番目の位置を `1` にする．
"""
# 入力
N, K = map(int, input().split())
S = list(input())


cnt_1 = 0 # 現在の1の数
clusters = [] # (塊の開始位置, 塊を形成する数)
# 塊の開始位置と塊を形成する数を記録する．
for i, s in enumerate(S + ["0"]): # 1終わりへの対策として，番兵をつけてloopをする．
  if s == "1":
    # カウントアップ
    cnt_1 += 1
  if s == "0":
    # 塊がある時，
    if cnt_1 > 0:
      # 開始位置と塊の数を記録
      clusters.append([i-cnt_1, cnt_1])
    # カウントを戻す．
    cnt_1 = 0
# K番目の位置を取得
index_old, cnt_k_th = clusters[K-0-1] # 0-index
# K番目の位置を0にする．
S[index_old:index_old+cnt_k_th] = ["0"]*cnt_k_th
# K-1番目の位置を取得
index_new, cnt_k_1_th = clusters[K-1-1] # 0-index
# K-1番目の位置を1にする．
S[index_new+cnt_k_1_th:index_new+cnt_k_1_th+cnt_k_th] = ["1"]*cnt_k_th

# 出力
print("".join(S))

D問題

S の最終的な長さは無限として良い．
まず，K が最初の状態 S のどの文字に注目しているかをみる．
その次に，その文字が大小反転しているかどうかを2進数で確認する．

D.py

"""
<方針>
- `S` の最終的な長さは無限として良い．
- まず，`K` が最初の状態 `S` のどの文字に注目しているかをみる．
- その次に，その文字が大小反転しているかどうかを2進数で確認する．
"""
S = input()
Q = int(input())
K = list(map(int, input().split()))
ans = []
for k in K:
  # 0-index
  k -= 1
  # 最初の文字列の長さで割ってみる．
  di, mo = divmod(k, len(S))
  # 注目している文字
  s = S[mo]
  # 反転の判定
  if bin(di).count("1") % 2 == 1:
    s = s.swapcase()
  
  ans.append(s)
  
print(*ans)

E問題

unionfind で頑張る．
- left で左端を管理しよう．
- right で右端を管理しよう．
- color で現在の色を管理しよう．
cnt で現在のそれぞれの色がいくつあるかをカウントしよう．
【参考】 WA が 7~8 で取れず，atcoder-companions で見ても，明らかに想定と違う解しか見つからないとき
- おそらく，left や right の管理がうまくいってないとそうなってしまう．
- 筆者の場合は，本解答の find の実装に left と right を更新するコードを足したらうまくいった．
- left と right のようなものを実装しているところを注意深くみると良いと思う．

E.py

"""
<方針>
- `unionfind` で頑張る．
  - `left` で左端を管理しよう．
  - `right` で右端を管理しよう．
  - `color` で現在の色を管理しよう．
- `cnt` で現在のそれぞれの色がいくつあるかをカウントしよう．
- 【参考】 `WA` が `7~8` で取れず，`atcoder-companions` で見ても，明らかに想定と違う解しか見つからないとき
  - おそらく，`left` や `right` の管理がうまくいってないとそうなってしまう．
  - 筆者の場合は，本解答の `find` の実装に `left` と `right` を更新するコードを足したらうまくいった．
  - `left` と `right` のようなものを実装しているところを注意深くみると良いと思う．
  
"""
import sys
sys.setrecursionlimit(10**6)

class UF:
  
  def __init__(self, N):
    self.parents = [-1]*N
    self.color = list(range(N)) # 左端
    self.left = list(range(N)) # 右端
    self.right = list(range(N)) # 色
  
  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      x_bef = x
      self.parents[x] = self.find(self.parents[x])
      self.left[x] = self.left[x_bef] = min(self.left[x], self.left[x_bef])
      self.right[x] = self.right[x_bef] = max(self.right[x], self.right[x_bef])
      return self.parents[x]
      
  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    
    if(x==y):
      return 
    
    if(self.parents[x] < self.parents[y]):
      x, y = y, x
    
    self.parents[x] += self.parents[y]
    self.parents[y] = x
    
    self.left[x] = min(self.left[x], self.left[y])
    self.right[x] = max(self.right[x], self.right[y])
    
    
  def same(self, x, y):
    return self.find(x) == self.find(y)
    
N, Q = map(int, input().split())
cnt = [1]*N # 色のカウント
uf = UF(N)
for _ in range(Q):
  query = list(map(int, input().split()))
  match query:
    case [1, x, c]:
      x -= 1
      c -= 1
      # 処理後の色
      af = c
      X = uf.find(x) # 親
      be = uf.color[X] # 処理前の色
      cnt[be] -= (-uf.parents[X]) # 色のカウントを減らす
      cnt[af] += (-uf.parents[X]) # 色のカウントを増やす
      uf.color[X] = af # 処理後の色にする
      # 左右との併合を試みる
      for y in [
        max(0, uf.left[X]-1),
        min(uf.right[X]+1, N-1),
        ]:
          # 枠内に収まっているとき，
          if 0<=y<N:
            # 色が処理後の色と一緒の時，
            if uf.color[uf.find(y)] == af:
              # 併合
              uf.union(y, x)
    case [2, c]:
      c -= 1
      print(cnt[c])

補足

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

今回のコンテスト

筆者について

その他

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

最後に一言

かっこよくなりたい．