ACL Practice Contestをac-library-pythonで解いてみたよ。(A～F問題)

# はじめに
2023年8月にあった大幅なAtCoderの言語アップデートで、PythonにもACLとよばれる競プロライブラリが追加されました。

https://github.com/not522/ac-library-python/

この記事では、そのライブラリの使い方を [ACL Practice Contest](https://atcoder.jp/contests/practice2) の問題を通して見ていきます。

この記事ではF問題までを見ていきます。G問題以降については下の記事を見てください。

https://qiita.com/hyouchun/items/3eee499a7ef31ca55b46

:::note info
ac-library-pythonの具体的な使い方が分かります。
:::
:::note warn
内部の詳細な実装は、上のGitHubを参考にしてください。
核となる問題の解き方は、ユーザー解説などを参考にしてください。
:::

# ac-library-pythonのインストール方法
1分で終わります。
タスクバーなどにあるパソコン内の検索で「cmd」と入力し、「コマンド プロンプト」と書かれたものを開きます。
黒い画面が出てくると思うので、そこで下の文字列をコピー&ペーストです！
```bash
pip install git+https://github.com/not522/ac-library-python
```
これで使えるようになってるはず！！

# A - Disjoint Set Union

## 問題ページ

https://atcoder.jp/contests/practice2/tasks/practice2_a

## 解説
Union Find です。
無向グラフで、2頂点が連結かどうかを調べるのに使われます。

- 辺を追加する
- 2頂点が連結かどうかの判定をする

が $O(\alpha (N))$ でできます。
$\alpha (N)$ は逆アッカーマン関数で、競プロ文脈だと $\alpha (N) \leq 4$ が成り立ちます。

(参考URL:  [高校数学の美しい物語 巨大数：アッカーマン関数とは](https://manabitimes.jp/math/1010) )

## メソッド一覧
- `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次元リスト)。


## コード
```Python
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
## 問題ページ

https://atcoder.jp/contests/practice2/tasks/practice2_b

## 解説
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}$ を返す。

## コード
```Python
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
## 問題ページ

https://atcoder.jp/contests/practice2/tasks/practice2_c

## 解説
次の式で表される値を、 $O(\log m)$ で求めます。

$$\sum_{i = 0}^{n - 1} \left\lfloor \frac{a \times i + b}{m} \right\rfloor$$

## メソッド一覧
- `floor_sum(n, m, a, b)` : 上記の式の値を返す。

## コード
```Python
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
## 問題ページ

https://atcoder.jp/contests/practice2/tasks/practice2_d

## 解説
最大流問題を解くライブラリです。

スタート、ゴールの超頂点をつくります。スタートからゴールまでフローを流せるだけ流して、その流量が答えになるようにグラフをつくります。

結論だけ書くと、下のようにグラフをつくればいいです。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2469270/333dd075-d587-b3a2-610b-d7fec1b183a1.png)

`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が入っている。

## コード
```Python
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
## 問題ページ

https://atcoder.jp/contests/practice2/tasks/practice2_e

## 解説
最小費用流ライブラリです。
下のようにグラフをつくります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2469270/81cb078a-bcf8-79d0-f4aa-2cedd39a445e.png)

注意点が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()` : 内部のすべての辺の状態をリストにまとめて返す。

## コード
```Python
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
## 問題ページ

https://atcoder.jp/contests/practice2/tasks/practice2_f

## 解説
:::note warn
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$ を求める。
## コード
```Python
# 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できます。

[AC提出コード (522ms)](https://atcoder.jp/contests/practice2/submissions/48921277)

https://github.com/shakayami/ACL-for-python