はじめに
ABC380の復習メモです
解説読んでも理解できないことが多いので、いつも復習に時間がかかります。
せっかく復習してるので記事として投稿してみようと思いましたが、続くかは分かりません。
C - Move Segment
使用言語：Python (PyPy 3.10-v7.3.12)
説明（例：入力例１）
ランレングス圧縮を用いて1と0にグループ分け
010011100011001 ->
[['0', 1], ['1', 1], ['0', 2], ['1', 3], ['0', 3], ['1', 2], ['0', 2], ['1', 1]]
3番目の1の塊を2番目の1の塊に結合
= 3番目の1の数を2番目の1の塊に加算。3番目の1の数は0に
[['0', 1], ['1', 1], ['0', 2], ['1', 3], ['0', 3], ['1', 2], ['0', 2], ['1', 1]]
->
[['0', 1], ['1', 1], ['0', 2], ['1', 5], ['0', 3], ['1', 0], ['0', 2], ['1', 1]]
これを元に戻してあげれば答えが求まる
[['0', 1], ['1', 1], ['0', 2], ['1', 5], ['0', 3], ['1', 0], ['0', 2], ['1', 1]] ->
010011111000001
コード全文
import sys
from itertools import groupby
input = sys.stdin.readline
def main():
N, K = input_to_int_list()
S = input_to_str()
runLength = runLengthEncode(S)
counter = 0
for i in range(len(runLength)):
if runLength[i][0] == "1":
counter += 1
if counter == K:
runLength[i - 2][1] += runLength[i][1]
runLength[i][1] = 0
break
print(runLengthDecode(runLength))
def input_to_str():
return input().strip()
def input_to_int_list():
return list(map(int, input().split()))
def runLengthEncode(S):
res = []
for k, v in groupby(S):
count = sum(1 for _ in v)
res.append([k, count])
return res
def runLengthDecode(L):
res_list = []
for c, n in L:
res_list.append(c * int(n))
return "".join(res_list)
if __name__ == "__main__":
main()
補足
ランレングス圧縮を元に戻す際、文字列の結合を行うと速度が間に合わなくなるので注意
文字列結合遅いのは有名なようですが、一度ハマってしまった...
def runLengthDecode(L):
res = ""
for c, n in L:
res += c * int(n)
return res
D - Strange Mirroring
使用言語：Python (PyPy 3.10-v7.3.12)
説明（例：入力例１）
繰り返しのパターンを考えると以下のようになる（ | が折り返しポイント）
0:aB
1:aB|Ab
2:aBAb|AbaB
3:aBAbAbaB|AbaBaBAb
Kの制約が10^18なので、繰り返し回数は2^60が上限
繰り返しごとに大文字小文字が入れ替わるので、繰り返しの回数と初期値との対応が分かれば良さそう。
（1-indexedで考えます）
K = 16について、繰り返しを追跡すると、
K=16は繰り返し3回目の末尾
1回前は、2回目の繰り返しのindex=8
2回前は、1回目の繰り返しのindex=4
3回前は、0回目の繰り返しのindex=2
初期値B（index=2）に対して3回繰り替えされた結果がK=16なので、小文字のbが答えと求まる
補足
swapcaseは文字列の大文字と小文字を入れ替えてくれる。
今回初めて知った。
コード全文
import sys
input = sys.stdin.readline
def main():
S = input_to_str()
N = len(S)
Q = input_to_int()
K = input_to_int_list()
ans = []
for k in K:
i = 60
k -= 1
swap = False
for i in range(60, 0, -1):
if k >= N * (2 ** (i - 1)):
k -= N * (2 ** (i - 1))
swap = not swap
ans.append(S[k].swapcase() if swap else S[k])
print(*ans)
def input_to_str():
return input().strip()
def input_to_int_list():
return list(map(int, input().split()))
def input_to_int():
return int(input())
if __name__ == "__main__":
main()
E - 1D Bucket Tool
使用言語：Python (PyPy 3.10-v7.3.12)
説明（例：入力例１）
どんどん同色のグループが増えていくと解釈して、UnionFindで検討。
最初はすべて独立したグループ
グループ管理
１： 親１，サイズ１、左端：１，右端：１、色：青
２： 親２，サイズ１、左端：２，右端：２、色：黄
３： 親３，サイズ１、左端：３，右端：３、色：赤
４： 親４，サイズ１、左端：４，右端：４、色：緑
５： 親５，サイズ１、左端：５，右端：５、色：紫
色管理
青：１，黄：１，赤：１、緑：１、紫：１
５を緑で塗ると、４と５が同グループになる
親で管理することとして、子になった５の色などは無視
グループ管理
１： 親１，サイズ１、左端：１，右端：１、色：青
２： 親２，サイズ１、左端：２，右端：２、色：黄
３： 親３，サイズ１、左端：３，右端：３、色：赤
４： 親４，サイズ２、左端：４，右端：５、色：緑
５： 親４，サイズ１、左端：５，右端：５、色：紫
色管理
青：１，黄：１，赤：１、緑：２、紫：０
４を黄で塗ると、４と５のグループが黄になる（色はサイズ分変化）
グループ管理
１： 親１，サイズ１、左端：１，右端：１、色：青
２： 親２，サイズ１、左端：２，右端：２、色：黄
３： 親３，サイズ１、左端：３，右端：３、色：赤
４： 親４，サイズ２、左端：４，右端：５、色：黄
５： 親４，サイズ１、左端：５，右端：５、色：紫
色管理
青：１，黄：３，赤：１、緑：０、紫：０
３を黄で塗ると、２～５が同グループになる
まずは３の緑を黄にかえて、その後２，４～５と結合
グループ管理
１： 親１，サイズ１、左端：１，右端：１、色：青
２： 親４，サイズ１、左端：２，右端：２、色：黄
３： 親４，サイズ１、左端：３，右端：３、色：黄
４： 親４，サイズ４、左端：２，右端：５、色：黄
５： 親４，サイズ１、左端：５，右端：５、色：紫
色管理
青：１，黄：４，赤：０、緑：０、紫：０
２を赤で塗ると、２～５のグループが赤になる（親である４の色が赤に）
グループ管理
１： 親１，サイズ１、左端：１，右端：１、色：青
２： 親４，サイズ１、左端：２，右端：２、色：黄
３： 親４，サイズ１、左端：３，右端：３、色：黄
４： 親４，サイズ４、左端：２，右端：５、色：赤
５： 親４，サイズ１、左端：５，右端：５、色：紫
色管理
青：１，黄：０，赤：４、緑：０、紫：０
このような管理を実際のコードで行えば良さそう
補足
上記の例は実際のコードの挙動とは少し異なる可能性がありますが、結果は同じです。
（どちらが親で、どちらが子になるかなど）
コード全文
import sys
input = sys.stdin.readline
def main():
N, Q = input_to_int_list()
uf = UnionFind(N)
for _ in range(Q):
query = input_to_int_list()
if query[0] == 1:
uf.change_color(query[1], query[2])
minimum = uf.min[uf.root(query[1])]
maximum = uf.max[uf.root(query[1])]
if minimum > 1 and uf.color[uf.root(minimum - 1)] == query[2]:
uf.unite(query[1], minimum - 1)
if maximum < N and uf.color[uf.root(maximum + 1)] == query[2]:
uf.unite(query[1], maximum + 1)
else:
print(uf.count_color(query[1]))
class UnionFind:
def __init__(self, N):
self.N = N
# グループ管理
self.parents = [-1] * (N + 1)
self.size = [1] * (N + 1)
self.color = [i for i in range(N + 1)]
self.min = [i for i in range(N + 1)]
self.max = [i for i in range(N + 1)]
# 色管理
self.color_count = {i: 1 for i in range(1, N + 1)}
def root(self, x):
# 親が-1ということは、根に到達したということ
if self.parents[x] == -1:
return x
# 親を根に繋ぎ直す（経路圧縮）
self.parents[x] = self.root(self.parents[x])
return self.parents[x]
def change_color(self, n, color):
root = self.root(n)
self.color_count[self.color[root]] -= self.size[root]
self.color[root] = color
self.color_count[self.color[root]] += self.size[root]
def count_color(self, color):
return self.color_count[color]
def unite(self, u, v):
rootu = self.root(u)
rootv = self.root(v)
if rootu == rootv:
return
if self.size[rootu] > self.size[rootv]:
rootu, rootv = rootv, rootu
# 大きい方のグループに、小さい方のグループを結合するようにする
# v >= u
self.parents[rootu] = rootv
self.size[rootv] += self.size[rootu]
self.min[rootv] = min(self.min[rootv], self.min[rootu])
self.max[rootv] = max(self.max[rootv], self.max[rootu])
def input_to_str():
return input().strip()
def input_to_int_list():
return list(map(int, input().split()))
def input_to_int():
return int(input())
if __name__ == "__main__":
main()