はじめに
2023年8月にあった大幅なAtCoderの言語アップデートで、PythonにもACLとよばれる競プロライブラリが追加されました。
この記事では、そのライブラリの使い方を ACL Practice Contest の問題を通して見ていきます。
この記事ではF問題までを見ていきます。G問題以降については下の記事を見てください。
ac-library-pythonの具体的な使い方が分かります。
内部の詳細な実装は、上のGitHubを参考にしてください。
核となる問題の解き方は、ユーザー解説などを参考にしてください。
ac-library-pythonのインストール方法
1分で終わります。
タスクバーなどにあるパソコン内の検索で「cmd」と入力し、「コマンド プロンプト」と書かれたものを開きます。
黒い画面が出てくると思うので、そこで下の文字列をコピー&ペーストです！
pip install git+https://github.com/not522/ac-library-python
これで使えるようになってるはず！！
A - Disjoint Set Union
問題ページ
解説
Union Find です。
無向グラフで、2頂点が連結かどうかを調べるのに使われます。
- 辺を追加する
- 2頂点が連結かどうかの判定をする
が $O(\alpha (N))$ でできます。
$\alpha (N)$ は逆アッカーマン関数で、競プロ文脈だと $\alpha (N) \leq 4$ が成り立ちます。
(参考URL: 高校数学の美しい物語 巨大数：アッカーマン関数とは )
メソッド一覧
-
uf = DSU(N): 初期化( $N$ は頂点数) -
uf.merge(u, v): 「頂点 $u$ の連結成分」と「頂点 $v$ の連結成分」を結合する。この連結成分の代表元を返す。 -
uf.same(u, v): 2頂点 $u, v$ が同じ連結成分ならTrueを、そうでない場合はFalseを返す。 -
uf.leader(u): 頂点 $u$ の連結成分の代表元を返す。 -
uf.size(u): 頂点 $u$ の連結成分の頂点数を返す。 -
uf.groups(): 各連結成分のリストを返す (各連結成分がそれぞれリストになっていて、全体として2次元リスト)。
コード
from atcoder.dsu import DSU
N, Q = map(int, input().split())
uf = DSU(N)
for _ in range(Q):
t, u, v = map(int, input().split())
if t == 0:
uf.merge(u, v)
else:
if uf.same(u, v):
print(1)
else:
print(0)
B - Fenwick Tree
問題ページ
解説
Fenwick Tree(フェニック木)です。
長さ $N$ のリスト $A$ に対して、
- リスト $A$ 内の要素 $A_i$ の値を変更する
- 半開区間 $[l, r)$ の値の総和 $A_l+A_{l+1}+\cdots +A_{r-1}$ を求める
の2つが $O(\log N)$ でできます。
メソッド一覧
-
ft = FenwickTree(N): 初期化 (値がすべて $0$ で長さ $N$ のリスト) -
ft.add(i, v): $A_i$ の値に $v$ を加算する。 -
ft.sum(l, r): 半開区間 $[l,r)$ の値の総和 $A_l+A_{l+1}+\cdots +A_{r-1}$ を返す。
コード
from atcoder.fenwicktree import FenwickTree
N, Q = map(int, input().split())
a = list(map(int, input().split()))
ft = FenwickTree(N)
for i, el in enumerate(a):
ft.add(i, el)
for _ in range(Q):
t, a, b = map(int, input().split())
if t == 0:
ft.add(a, b)
elif t == 1:
print(ft.sum(a, b))
C- Floor Sum
問題ページ
解説
次の式で表される値を、 $O(\log m)$ で求めます。
$$\sum_{i = 0}^{n - 1} \left\lfloor \frac{a \times i + b}{m} \right\rfloor$$
メソッド一覧
-
floor_sum(n, m, a, b): 上記の式の値を返す。
コード
from atcoder.math import floor_sum
T = int(input())
for _ in range(T):
N, M, A, B = map(int, input().split())
print(floor_sum(N, M, A, B))
D - MaxFlow
問題ページ
解説
最大流問題を解くライブラリです。
スタート、ゴールの超頂点をつくります。スタートからゴールまでフローを流せるだけ流して、その流量が答えになるようにグラフをつくります。
結論だけ書くと、下のようにグラフをつくればいいです。
graph.flow(start, goal)で流せるだけフローを流します。また、その返り値が流量になっています。
graph.edges() でこのグラフのどの辺にフローがいくつ流れているかを確認できます。これでタイルがどこに置かれているかを見ることができます。
メソッド一覧
-
graph = MFGraph(N): 頂点数 $N$ のグラフをつくる。 -
graph.add_edge(u, v, c): 頂点 $u$ から頂点 $v$ へ、最大容量 $c$ の辺をはる。この辺の番号を返す。 -
graph.flow(s, t): 頂点 $s$ から頂点 $t$ への最大フローを求め、その値を返す。 -
graph.get_edge(m): 辺 $m$ の状態(始点、終点、流量)を返す。 -
graph.edges(): 内部のすべての辺の状態をリストにまとめて返す。 -
graph.change_edge(m, c, f): 辺 $m$ の最大容量を $c$ に、流量を $f$ に変更する。 -
graph.min_cut(u): 最小カットを求める。返り値は長さ $N$ のリストで、 $i$ 番目の要素は頂点 $u$ から残余グラフで到達できるならTrueが、到達できないならFalseが入っている。
コード
from atcoder.maxflow import MFGraph
vector_dic = {
(1, 0): 'v',
(0, 1): '>',
(-1, 0): '^',
(0, -1): '<'
}
N, M = map(int, input().split())
S = [list(input()) for _ in range(N)]
graph = MFGraph(N * M + 2)
start, goal = N * M, N * M + 1
for i in range(N):
for j in range(M):
if S[i][j] == '#':
continue
if (i + j) & 1:
graph.add_edge(i * M + j, goal, 1)
else:
graph.add_edge(start, i * M + j, 1)
for ni, nj in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
if not (0 <= ni < N and 0 <= nj < M):
continue
if S[ni][nj] == '#':
continue
graph.add_edge(i * M + j, ni * M + nj, 1)
tile_cnt = graph.flow(start, goal)
for edge in graph.edges():
if edge.flow != 0 and edge.src != start and edge.dst != goal:
i1, j1 = divmod(edge.src, M)
i2, j2 = divmod(edge.dst, M)
S[i1][j1] = vector_dic[(i2 - i1, j2 - j1)]
S[i2][j2] = vector_dic[(i1 - i2, j1 - j2)]
print(tile_cnt)
for row in S:
print(*row, sep='')
E - MinCostFlow
問題ページ
解説
最小費用流ライブラリです。
下のようにグラフをつくります。
注意点が2つあります。
1つ目は、サンプル2にもあるように、どの行・列も要素を $K$ 個選ぶとは限らないということです。
これの対処は、 $s$ から $t$ へ容量 $\infty$ コスト $0$ の辺をはることで解決します。
2つ目は、負のコストを入れてはいけないということです。
これの対処は、とても大きい数 $B$ (下のコードでは $2^{50}$ にしています)から $A[i][j]$ を引いた数をコストにして、最後に答えから $BNK$ を引けば解決します。
メソッド一覧
-
graph = MCFGraph(N): 頂点数 $N$ のグラフをつくる。 -
graph.add_edge(u, v, cap, cost): 頂点 $u$ から頂点 $v$ に最大容量 $cap$ コスト $cost$ の辺をはる。辺の番号を返す。 -
graph.flow(u, v, lim): 頂点 $u$ から頂点 $v$ へ、最大流量 $lim$ まで流せるだけ流す。 $lim$ は省略可能。 (最大フロー、最小コスト)のタプルを返す。 -
graph.slope(u, v, lim): 頂点 $u$ から頂点 $v$ へ、最大流量 $lim$ まで流せるだけ流す。$lim$ は省略可能。 (流量、コスト) の折れ線グラフを返す。 -
graph.get_edge(i): 番号 $i$ の辺の状態(始点、終点、最大流量、流量、コスト)を返す。 -
graph.edges(): 内部のすべての辺の状態をリストにまとめて返す。
コード
from atcoder.mincostflow import MCFGraph
B = 1 << 50
N, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
start, goal = N * 2, N * 2 + 1
graph = MCFGraph(goal + 1)
edges = [[] for _ in range(N)]
for i in range(N):
graph.add_edge(start, i, K, 0)
for j in range(N):
graph.add_edge(j + N, goal, K, 0)
for i in range(N):
for j in range(N):
ei = graph.add_edge(i, j + N, 1, B - A[i][j])
edges[i].append(ei)
graph.add_edge(start, goal, N * K, B)
cost = graph.flow(start, goal, N * K)[1]
print(B * N * K - cost)
ans_grid = list(['.'] * N for _ in range(N))
for i in range(N):
for j in range(N):
if graph.get_edge(edges[i][j]).flow > 0:
ans_grid[i][j] = 'X'
for row in ans_grid:
print(*row, sep='')
F - Convolution
問題ページ
解説
ac-library-python の convolutionだとTLEしてしまいます。
ACしたい場合は、独自のライブラリをつくるしかなさそうです。
畳み込みを $\bmod m$ で計算します( $m$ は素数)。
具体的には、下の式で表される数列 $c_0, c_1, \cdots c_{(N-1)+(M-1)}$ を求めます。
$$c_i = \sum_{j = 0}^i a_j b_{i - j} \bmod m$$
メソッド一覧
-
c=convolution(m, a, b): 上記の数列 $c$ を求める。
コード
# TLEコードだから注意してね。
from atcoder.convolution import convolution
N, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = convolution(998244353, a, b)
print(*c)
おまけ
shakayamiさんのacl-for-pythonからコードを拝借するとACできます。