AtCoder Library Practice Contest を ac-library-rs で解いてみた - 数学編

# はじめに

https://qiita.com/hossie/items/084e7cf777fb023234f5 

のつづきです。本記事では数学関係の 2問を扱います。

## 本記事で扱うこと (前回と同じ)

* コードとの対応が分かる程度の問題の解き方図解
    * Rust 以外で解く方にも、競技プログラミングで使うアルゴリズムの参考になるかもしれません
* ac-library-rs の使い方
* Rust + ac-library-rs + proconio, itertools で解いたコード例
    * AtCoder Library や ac-library-rs GitHub 内の解答例を参考にしました:
    * [ac\-library/document\_ja/index\.md at master · atcoder/ac\-library](https://github.com/atcoder/ac-library/blob/master/document_ja/index.md)
        * とても丁寧な公式解説です。C++ 以外の方にもおすすめ
    * [ac\-library\-rs/examples at master · rust\-lang\-ja/ac\-library\-rs](https://github.com/rust-lang-ja/ac-library-rs/tree/master/examples)
    * [Add sample code for the practice contest by TonalidadeHidrica · Pull Request \#52 · rust\-lang\-ja/ac\-library\-rs](https://github.com/rust-lang-ja/ac-library-rs/pull/52)

## 本記事で扱わないこと

* AtCoder Library の AtCoder Library Practice Contest では使わない機能については触れません (modint 詳細など)
* AtCoder Library が内部でどのようなデータ構造を持ち、データ処理しているかということは扱いません
* AtCoder Library 以外のライブラリーでも解ける、という話は扱いません (petgraph など)
* 問題の解答方針をどうすれば考え付くかというところは扱いません。練習問題の解説リンクにあるけんちょんさん解説などをどうぞ。

AtCoder Library の詳細説明は、 @sysdev さんの「AtCoder Library を読んでアルゴリズムを勉強」シリーズがとてもいい感じです。こちらもどうぞ。

* [AtCoder Library を読んでアルゴリズムを勉強：セグメント木 \- Qiita](https://qiita.com/sysdev/items/6aaf0c9157cf96a64e59)
* [AtCoder Library を読んでアルゴリズムを勉強：セグメント木（一括更新版） \- Qiita](https://qiita.com/sysdev/items/4fbcc46f18a13dc8e065)
* [AtCoder Library を読んでアルゴリズムを勉強：フェニック木（BIT） \- Qiita](https://qiita.com/sysdev/items/30aa7d5e9ac4ea871bd3)
* [AtCoder Library を読んでアルゴリズムを勉強：DSU（union\-find） \- Qiita](https://qiita.com/sysdev/items/0d300dbb3a1e499ca2a3)
* [AtCoder Library を読んでアルゴリズムを勉強：強連結成分 \- Qiita](https://qiita.com/sysdev/items/4532d52ab9978cd9d4d4)
* [AtCoder Library を読んでアルゴリズムを勉強：2\-SAT \- Qiita](https://qiita.com/sysdev/items/c6b707666541bacd22bf)

## AtCoder Library Practice Contest 問題一覧

* データ構造系
    * B - Fenwick Tree
    * I - Number of Substrings
    * J - Segment Tree
    * K - Range Affine Range Sum
    * L - Lazy Segment Tree
* 数学系 (本記事の対象)
    * C - Floor Sum
    * F - Convolution
* グラフ系
    * A - Disjoint Set Union
    * D - Maxflow
    * E - MinCostFlow
    * G - SCC
    * H - Two SAT

スキルツリーを描くと次のような感じ。実線の矢印は関連が強いですので、順番に進めることをおすすめです。A → H の順が G 問題で扱うトポロジカルソートになっています。

```mermaid
flowchart LR
  subgraph データ構造系
    direction LR
    subgraph 木構造
      direction TB
      B(B - Fenwick Tree)
      J(J - Segment Tree)
      K(K - Range Affine Range Sum)
      L(L - Lazy Segment Tree)
    end
    subgraph 文字列
      I(I - Number of Substrings)
    end
    B-."和以外の一点更新".->J
    J--"区間更新 (遅延)"-->K
    K--"複雑な区間更新"-->L
  end
  subgraph 数学系
    direction TB
    C(C - Floor Sum)
    F(F - Convolution)
  end
  subgraph グラフ系
  direction LR
    subgraph フロー
      D(D - Maxflow)
      E(E - MinCostFlow)
    end
    subgraph グループ化
      A(A - Disjoint Set Union)
      G(G - SCC)
      H(H - Two SAT)
    end
    A-."有向グラフ".->G
    D--"辺にコスト追加"-->E
    G--"SCC 使用例"-->H
  end
```


# 数学
## C - Floor Sum
* [C \- Floor Sum](https://atcoder.jp/contests/practice2/tasks/practice2_c)
* [atcoder\.github\.io/ac\-library/document\_ja/math\.html](https://atcoder.github.io/ac-library/document_ja/math.html)

```math
\sum_{i=1}^{n-1} \left \lfloor \frac{a \times i + b}{m} \right \rfloor
```
を求める関数 `floor_sum(n, m, a, b)` が提供されています。

C 問題は `floor_sum()` をそのまま呼び出すと終了です。

## C 解答例

```rust:practice2-c.rs
use proconio::input;

fn main() {
    input! {
        nmabs: [(i64, i64, i64, i64)],
    }
    for (n, m, a, b) in nmabs {
        println!("{}", ac_library::floor_sum(n, m, a, b));
    }
}
```

2か月前の ABC313-G で使えたそうです。

* [G \- Redistribution of Piles](https://atcoder.jp/contests/abc313/tasks/abc313_g)

# F - Convolution

* [F \- Convolution](https://atcoder.jp/contests/practice2/tasks/practice2_f)
* [atcoder\.github\.io/ac\-library/document\_ja/convolution\.html](https://atcoder.github.io/ac-library/document_ja/convolution.html)

長さ $N$ の数列 $a_0, a_1,..., a_{N-1}$ と、長さ $M$ の数列 $b_0, b_1,..., b_{M-1}$ から、長さ $N+M−1$ の数列
```math
c_i = \sum_{j=0}^i{a_j b_{i−j}​} 
```

を求める関数 `convolution(a, b)` が提供されています。

F 問題は `convolution()` をそのまま呼び出すと終了です。 [^1]

[^1]: この数式を見て i≧N のときに a_i は範囲外だからどうなるのだろうと思ってしまいました。畳み込み演算ですから対称そう、計算しないと分かるでしょう、でしょうか。

![practice2-f.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/118172/6720ac11-5836-8623-ba9e-ef639539a8b0.png)

## F 解答例

```rust:practice2-f.rs
use itertools::Itertools;
use proconio::input;

type Mint = ac_library::ModInt998244353;

fn main() {
    input! {
        n: usize,
        m: usize,
        a: [Mint; n],
        b: [Mint; m],
    }
    let result = ac_library::convolution(&a, &b).iter().join(" ");
    println!("{result}");
}
```


# 最後に

前書きの方が長い記事となりました。

グラフ編に続きます。