[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])
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
- 解説で示したE問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- かっこよくなりたい．