はじめに

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])