はじめに
2023年8月にあった大幅なAtCoderの言語アップデートで、PythonにもACLとよばれる競プロライブラリが追加されました。
この記事では、そのライブラリの使い方を ACL Practice Contest の問題を通して見ていきます。
この記事ではG問題以降を見ていきます。A～F問題については下の記事を見てください。
ac-library-pythonの具体的な使い方が分かります。
内部の詳細な実装は、上のGitHubを参考にしてください。
核となる問題の解き方は、ユーザー解説などを参考にしてください。
G - SCC
問題
解説
強連結成分分解です。
また、問題文にはトポロジカルソートした状態で出力するように書かれていますが、ac-library-pythonの強連結成分分解はトポロジカルソートされた状態でリストを返してくれるので、今回は気にせず出力してよいです。
強連結成分分解とは
有向グラフにおいて、お互いに行き来できる頂点を1つのグループにまとめることを、強連結成分分解と言います。トポロジカルソートとは
頂点 $u_i$ から頂点 $v_i$ への有向辺があったとき、 $u_i$ の属する強連結成分よりも $v_i$ の属する強連結成分の方が後ろになるように並べることを、トポロジカルソートと言います。メソッド一覧
-
graph = SCCGraph(N): 頂点数 $N$ のグラフをつくる。 -
graph.add_edge(u, v): 頂点 $u$ から頂点 $v$ への有向辺をはる。 -
graph.scc(): 2次元リストを返す。各要素(リスト)は強連結成分です。またトポロジカルソートされていて、異なる強連結成分の頂点 $u, v$ について $u$ から $v$ に到達できるとき、 $u$ の属するリストは $v$ の属するリストよりも前にある。
コード
from atcoder.scc import SCCGraph
N, M = map(int, input().split())
graph = SCCGraph(N)
for _ in range(M):
a, b = map(int, input().split())
graph.add_edge(a, b)
groups = graph.scc()
print(len(groups))
for group in groups:
print(len(group), *group)
H - Two SAT
問題
解説
Two SAT 問題を解きます。
Two SAT 問題とは、$(a \lor b) \land (c \lor d) \land (e \lor f) \land \cdots$ の式があったときに、$a, b, c, \cdots $ に対して適切に真偽値(True か False) を当てはめることで、式全体をTrueにできるかどうか、という問題のことです。
旗 $i$ を座標 $X_i$ に設置することを True、座標 $Y_i$ に設置することをFalseとします。
たとえば $2$ つの旗 $i, j$ について $|X_i-X_j|<D$ だったとき、旗 $i, j$ をそれぞれ $X_i, X_j$ に置くことはできず、「旗 $i$ を 座標 $Y_i$ に置く」または「旗 $j$ を座標 $Y_j$ に置く」のどちらかを満たさないといけません。つまり、 $i=\text{False} \lor j=\text{False}$ が成り立ちます。
これをそれぞれの旗・座標に対しておこないます。
メソッド一覧
-
twosat = TwoSAT(N): $N$ 変数の Two SAT をつくる。 -
twosat.add_clause(i, f, j, g): $(x_i = f) \lor (x_j = g)$ の条件式を追加する。 -
twosat.satisfiable(): 条件を満たすように $x_1, x_2, \cdots ,x_N$ に真偽値を割り当てられるならTrueを、そうでなければFalseを返す。 -
twosat.answer(): 最後に呼んだsatisfiable()のときの $x_1, x_2, \cdots ,x_N$ の真偽値リストを返す。
コード
from atcoder.twosat import TwoSAT
N, D = map(int, input().split())
Flag = [tuple(map(int, input().split())) for _ in range(N)]
twosat = TwoSAT(N)
for i in range(N - 1):
for j in range(i + 1, N):
if i == j:
continue
if abs(Flag[i][0] - Flag[j][0]) < D:
twosat.add_clause(i, False, j, False)
if abs(Flag[i][0] - Flag[j][1]) < D:
twosat.add_clause(i, False, j, True)
if abs(Flag[i][1] - Flag[j][0]) < D:
twosat.add_clause(i, True, j, False)
if abs(Flag[i][1] - Flag[j][1]) < D:
twosat.add_clause(i, True, j, True)
if twosat.satisfiable():
print("Yes")
ans = twosat.answer()
for i in range(N):
if ans[i]:
print(Flag[i][0])
else:
print(Flag[i][1])
else:
print("No")
I - Number of Substrings
問題
解説
連続する部分文字列の種類数を求めます。
しかし部分文字列の種類数を求めるものはac-library-pythonにはありません。
その代わりにac-library-pythonの中にあるsuffix-arrayとlcp-arrayをつかうことで、この問題を解くことができます。
suffix-arrayとは。
- suffix-arrayとは。
- 和訳すると、「接尾辞配列」です。
たとえば文字列 $S$ が "abcbc" だったとします。
$i=0, 1, \cdots , |S|-1$ について、$S[i:]$ をリスト $P$ に入れます。すなわち、 $P$ の中には、 "abcbc", "bcbc", "cbc", "bc", "c" の $5$ つが入っていることになります。
これを辞書順にソートします。すなわち、 $P$ は左から順に、 "abcbc", "bc", "bcbc", "c", "cbc" になります。
それぞれの文字列について、ソートする前の $P$ でのインデックスに置き換えます。つまり、 $[0,3,1,4,2]$ になります。このリストがsuffix-arrayです。
suffix-arrayの大まかな解説コード
上の文字解説をコードに書き起こしました。
実際に内部で実装されているアルゴリズムの方が高速で、これは雰囲気をつかむためだけのものなので注意してください。
"""ac-library-pythonの内部実装とは違うのに注意してね。"""
S = "abcbc"
P = [S[i:] for i in range(len(S))]
sP = sorted(P)
suffix_array = [P.index(ele) for ele in sP]
lcp-arrayとは。
- lcp-arrayとは。
- LCPはLongest Common Prefixの略で、和訳すると「最長共通接頭辞」です。
先ほどのsuffix-arrayで、 $i=0, 1, \cdots , |S|-1$ に対して $S[i:]$ を辞書順に管理できました。
lcp-arrayでは、各 $i$ についてその辞書順の $i$ 番目と $i+1$ 番目の文字列のLCPを求めます。
たとえば上のsuffix-arrayで用いた文字列 $S=\text{abcbc}$ について、suffix-arrayで辞書順に並べた結果、 $1$ 番目と $2$ 番目はそれぞれ "bc" と "bcbc" でした。この2つは "bc" の部分が接頭辞として共通しているのでLCPは $2$ です。
同様にして他のLCPも求めると、 $[0,2,0,1]$ になります。これがlcp-arrayです。
lcp-arrayの大まかな解説コード
上の文字解説をコードに書き起こしました。実際に内部で実装されているアルゴリズムの方が高速で、これは雰囲気をつかむためだけのものなので注意してください。
"""ac-library-pythonの内部実装とは違うのに注意してね。"""
def lcp(s1, s2):
result = 0
for el1, el2 in zip(s1, s2):
if el1 == el2:
result += 1
else:
break
return result
S = "abcbc"
P = [S[i:] for i in range(len(S))]
P.sort()
lcp_array = [lcp(P[i], P[i + 1]) for i in range(len(P) - 1)]
メソッド一覧
-
sa = suffix_array(S): 文字列 $S$ のsuffix-arrayとして、長さ $|S|$ のリストを返す。 -
la = lcp_array(S, sa): 文字列 $S$ のLCP-array として、長さ $|S|-1$ のリストを返す。 -
z = z_algorithm(S): 長さ $|S|$ のリストを返す。 $i$ 番目の要素は、 $S$ と $S[i:]$ のLCP(最長共通接頭辞)の長さ。
コード
from atcoder.string import suffix_array, lcp_array
S = input()
sa = suffix_array(S)
ans = len(S) * (len(S) + 1) // 2
for x in lcp_array(S, sa):
ans -= x
print(ans)
J- Segment Tree
問題
解説
セグメントツリーです。
- リスト内のインデックスを $1$ つ指定して、そのインデックスの値を変更する。
- リスト内の範囲を指定して、その区間全体に対する演算(総和 $\text{sum}$ や最小値 $\min$ など)を行った結果を取得する。
の $2$ つをどちらも $O(\log N)$ で行えます。
メソッド一覧
-
st = SegTree(op, e, v): セグメントツリーを構築する。$op$ は区間の演算につかう関数、$e$ はその単位元。 $v$ にはlist型かint型を入れる。list型の場合はそのリストをそのまま入り、int型の場合はすべての要素が単位元 $e$ で長さ $v$ のリストになる。 -
st.set(p, x): リスト $A$ について、$A_p$ に $x$ を代入する。 -
st.get(p): リスト $A$ の $p$ 番目の要素 $A_p$ を返す。 -
st.prod(l, r): 半開区間 $[l: r)$ における演算の結果を返す。 -
st.all_prod(): リスト全体における演算の結果を返す。 -
st.max_right(p, func): セグメントツリー上で二分探索をする。 $p \leq i$ を満たす $i$ の中で、関数 $\text{func}$ を満たす最小の $i$ を返す。 -
st.min_left(p, func): セグメントツリー上で二分探索をする。 $i < p$ を満たす $i$ の中で、関数 $\text{func}$ を満たす最大の $i$ を返す。
コード
from atcoder.segtree import SegTree
N, Q = map(int, input().split())
A = list(map(int, input().split()))
st = SegTree(max, -1, A)
for _ in range(Q):
t, x, y = map(int, input().split())
if t == 1:
st.set(x - 1, y)
elif t == 2:
print(st.prod(x - 1, y))
else:
print(st.max_right(x - 1, lambda p: p < y) + 1)
K - Range Affine Range Sum
問題
解説
遅延セグメントツリーです。
- リスト内の範囲を指定して、その値を一括で変更する。
- リスト内の範囲を指定して、その区間全体に対する演算(総和 $\text{sum}$ や最小値 $\min$ など)を行った結果を取得する。
の $2$ つをどちらも $O(\log N)$ で行えます。
この問題では、モノイドとして遅延セグメントツリーに (値, そのノードの区間の長さ) のタプルをのせています。
解説記事
-
Pythonで遅延セグメントツリーの問題を解けるようにする！ (私の記事です。)
-
AtCoder LibraryのLazy Segtreeの使い方 (アルメリアさんの記事です。)
メソッド一覧
-
ls = LazySegTree(op, e, mapping, composition, _id, lst): 遅延セグメントツリーを構築する。引数は以下の通り。-
op: 区間取得の演算 -
e: $op$ の単位元 -
mapping: $\text{data}$ に $\text{lazy}$ を作用させたときの関数 -
composition: $\text{lazy}$ に別の $\text{lazy}$ を作用させたときの関数 -
_id: $\text{mapping}$ の恒等写像、 -
lst: 初期リスト。
-
-
ls.apply(l, r , f)リスト $A$ について、 $i=l,l+1, \cdots , r-1$ それぞれに対して $A_i$ に $f$ を作用させる。 -
ls.set(p, x)リスト $A$ について、 $A_p$ に $x$ を代入する。 -
ls.get(p): リスト $A$ の $p$ 番目の要素 $A_p$ を返す。 -
ls.prod(l, r): 半開区間 $[l: r)$ における演算の結果を返す。 -
ls.all_prod(): リスト全体における演算の結果を返す。 -
ls.max_right(p, func): セグメントツリー上で二分探索をする。 $p \leq i$ を満たす $i$ の中で、関数 $\text{func}$ を満たす最小の $i$ を返す。 -
ls.min_left(p, func): セグメントツリー上で二分探索をする。 $i < p$ を満たす $i$ の中で、関数 $\text{func}$ を満たす最大の $i$ を返す。
コード
from atcoder.lazysegtree import LazySegTree
MOD = 998244353
e = (0, 0) # opの単位元 (値, このノードの区間の長さ)
_id = (1, 0) # mappingにおける恒等写像
# 区間取得の演算
def op(data1, data2):
sum1, length1 = data1
sum2, length2 = data2
next_sum = (sum1 + sum2) % MOD
next_length = length1 + length2
return next_sum, next_length
# lazy -> data
def mapping(lazy_upper, data_lower):
b, c = lazy_upper
sum1, length1 = data_lower
next_sum = (b * sum1 + c * length1) % MOD
return next_sum, length1
# lazy -> lazy
def composition(lazy_upper, lazy_lower):
b2, c2 = lazy_upper
b1, c1 = lazy_lower
next_b = b1 * b2 % MOD
next_c = (b2 * c1 + c2) % MOD
return next_b, next_c
N, Q = map(int, input().split())
A = list(map(int, input().split()))
lst = [(a, 1) for a in A]
ls = LazySegTree(op, e, mapping, composition, _id, lst)
for _ in range(Q):
t, *q = map(int, input().split())
if t == 0:
l, r, b, c = q
ls.apply(l, r, (b, c))
else:
l, r = q
ans = ls.prod(l, r)[0]
print(ans)
L - Lazy Segment Tree
問題
解説
遅延セグメントツリーです。
K問題とつかうデータ構造は同じです。
この問題では、モノイドとして遅延セグメントツリーに (0の個数, 1の個数, ノード内での転倒数) のタプルをのせています。
メソッド一覧
(K問題と同じなので省略)
コード
from atcoder.lazysegtree import LazySegTree
e = (0, 0, 0) # opの単位元 (0の個数, 1の個数, このノード内での転倒数)
_id = False # mappingにおける恒等写像
# 区間取得の演算
def op(ele1, ele2):
l0, l1, l_inv = ele1
r0, r1, r_inv = ele2
nex0 = l0 + r0
nex1 = l1 + r1
nex_inv = l_inv + r_inv + l1 * r0
return nex0, nex1, nex_inv
# lazy -> data
def mapping(func, ele):
x0, x1, x_inv = ele
if func:
return x1, x0, x0 * x1 - x_inv
else:
return x0, x1, x_inv
# lazy -> lazy
def composition(func_upper, func_lower):
if func_upper:
return not func_lower
else:
return func_lower
N, Q = map(int, input().split())
A = list(map(int, input().split()))
lst = [(0, 1, 0) if a == 1 else (1, 0, 0) for a in A]
lazy_segtree = LazySegTree(op, e, mapping, composition, _id, lst)
for _ in range(Q):
t, l, r = map(int, input().split())
if t == 1:
lazy_segtree.apply(l - 1, r, True)
else:
print(lazy_segtree.prod(l - 1, r)[2])