2024-03-20

Z algorithmの文章による説明

Z algorithmを図に頼らずに理解したかったので書きました．

長さ $N (\geq 1)$ の文字列 $S$ にZ algorithmを適用することを考えます．

以下の説明では文字列中の各文字を0-basedで指定します¹． $S$ の $i$ 文字目を $S[i]$ と表記します．また， $S$ の $l$ 文字目から $r-1$ 文字目までを取り出した部分文字列を $S[l:r]$ と表記します． $l=r$ のとき $s[l:r]$ は空文字列とし，空文字列同士は一致するとします．便宜上 $S[N]$ を任意の文字に一致しない文字と取り決めます．

$i=0,1,\cdots,N-1$ に対し， $Z[i]$ を $S[0:j]=S[i:i+j]$ かつ $S[j] \neq S[i+j]$ を満たす $N-i$ 以下の非負整数とします．つまり， $Z[i]$ は $S$ と $S[i:N]$ の最長共通接頭辞の長さを表します． $S=S[0:N]$ なので $Z[0]=N$ です．

以下， $N \geq 2$ とし，ある $i (\geq 1)$ について $Z[0], Z[1], \cdots, Z[i]$ が既知であるとします．また， $j=Z[i]$ とします． $Z[i]$ の定義より， $S[0:j]=S[i:i+j]$ かつ $S[j] \neq S[i+j]$ です．

$k=1, 2, \cdots, j-1$ について，この順に $Z[i+k$ ]を求めることを考えます． $i+k>k$ より $Z[i+k]$ を求めるときには $Z[k]$ は既知であり，この値を利用します．各 $k$ について， $k+Z[k]$ の値により以下のように場合分けして考えます．

$k+Z[k] \lt j$ のとき

$S[0:j]=S[i:i+j]$ より， $[k:k+Z[k]+1]=S[i+k:i+k+Z[k]+1]$ なので以下の2つの関係が成り立ちます．
- $S[0:Z[k]]=S[k:k+Z[k]]=S[i+k:i+k+Z[k]]$
- $S[Z[k]] \neq S[k+Z[k]] = S[i+k+Z[k]]$
$S$ の $k$ 文字目以降の $Z[k]+1$ 文字と $S$ の $i+k$ 文字目以降の $Z[k]+1$ 文字とが， $S$ の接頭辞と $Z[k]$ 文字目で不一致となることも含めて一致しているので $Z[i+k]=Z[k]$ であると分かります²．
$k+Z[k] \geq j$ のとき

$S[0:j]=S[i:i+j]$ 及び $Z[k] \geq j-k$ より， $S[0:j-k]=S[k:j]=S[i+k:i+j]$ が成り立ち， $Z[i+k] \geq j-k$ であると分かります． $Z[i+k]$ を確定するために $S$ と $S[i+k]$ を比較する必要がありますが，最初の $j-k$ 文字については既に一致していることが判明しているため，比較処理を省略することができます．

Z algorithmでは $k+Z[k] \geq j$ となる $k$ が見つかった時点で $i$ を $i+k$ で置き換え，最初の $j-k$ 文字の比較処理を省略して $Z[i]$ を求めることで $Z[0], Z[1], \cdots, Z[i]$ が既知である最初の状態に戻します．このようにすることで文字を比較する位置が後退せず，全体の計算量が $\Theta(N)$ になります．

実装例 (Rust)

pub fn z_algorithm<T>(seq: &[T]) -> Vec<usize>
where
    T: Eq,
{
    if seq.is_empty() {
        return vec![];
    }

    let n = seq.len();

    let mut lengths = vec![0; n];
    lengths[0] = n;

    let mut cursor = 1;
    let mut common_len = 0;
    while cursor < n {
        while cursor + common_len < n && seq[cursor + common_len] == seq[common_len] {
            common_len += 1;
        }

        if common_len == 0 {
            cursor += 1;
            continue;
        }

        lengths[cursor] = common_len;

        let mut shift = 1;
        while shift + lengths[shift] < common_len {
            lengths[cursor + shift] = lengths[shift];
            shift += 1;
        }

        cursor += shift;
        common_len -= shift;
    }

    lengths
}

$S$ の先頭の文字は $0$ 文字目，最後の文字は $N-1$ 文字目となります．↩
人の課題を写したら全く同じ間違え方をしていてバレたという話と少し似ています．↩

2024-03-15

AtCoderのコンテスト参加環境

AtCoderのコンテストに参加するときの環境 (2024/03/15 現在)

OS: Ubuntu 22.04 LTS
エディタ: Visual Studio Code
- 拡張機能: rust-analyzer等
使用言語: Rust
自動化ツール: cargo-compete

テンプレート

use proconio::input;

fn main() {
    input! {
        
    }
}

テンプレートはシンプルにして、必要に応じてUser Snippetsで自作ライブラリなどを貼り付けています。

2023-09-22

トリボナッチ数列と行列

トリボナッチ数列の計算*1

フィボナッチ数列に類似した数列にトリボナッチ数列があります．フィボナッチ数列は最初の2項を初期値とし，3項目以降を直前の2項の和として定めていますが，トリボナッチ数列は最初の3項を初期値とし，4項目以降を直前の3項の和として定めています．

トリボナッチ数列 $T = (T_0, T_1, T_2, \cdots)$ は以下のように定義されます．

$\displaystyle \begin{equation} \begin{cases} T_0 = 0 \\ T_1 = 0 \\ T_2 = 1 \\ T_k = T_{k-3} + T_{k-2} + T_{k-1} & (k = 3, 4, 5, \cdots) \end{cases} \end{equation}$

トリボナッチ数列の具体的な値を以下の表に示します．

$n$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	$\cdots$
$T_n$	0	0	1	1	2	4	7	13	24	44	81	149	274	504	927	1705	3136	5768	10609	19513	35890	66012	121415	223317	410744	755476	1389537	2555757	4700770	8646064	15902591	$\cdots$

$k = 0, 1, 2, \cdots$ について， $T$ の連続した3つの要素を成分にもつベクトル $\boldsymbol{t}_k$ を以下のように定義します．

$\displaystyle \begin{equation} \boldsymbol{t}_k = \begin{pmatrix} T_{k+2} \\ T_{k+1} \\ T_k \end{pmatrix} \end{equation}$

以下の線形変換 $f \colon \mathbb{R}^2 \to \mathbb{R}^2$ は $\boldsymbol{t}_k$ を $\boldsymbol{t}_{k+1}$ に写します．

$\displaystyle \begin{equation} f\left(\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix}\right) = \begin{pmatrix} x_1 + x_2 + x_3 \\ x_1 \\ x_2 \end{pmatrix} \end{equation}$

線形変換は行列により表すことができます．変換 $f$ を表す行列を $A$ とすると， $A$ の各列には基本ベクトル $\boldsymbol{e}_1, \boldsymbol{e}_2, \boldsymbol{e}_3$ をそれぞれ $f$ で変換した $f(\boldsymbol{e}_1), f(\boldsymbol{e}_2), f(\boldsymbol{e}_3)$ が並びます．これは線形変換において，基本ベクトルの変換先の情報のみを用いて任意のベクトルの変換先を計算できるためです．

$\displaystyle \begin{gather} f(\boldsymbol{e}_1) = f\left(\begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}\right) = \begin{pmatrix} 1 + 0 + 0 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix} \\ f(\boldsymbol{e}_2) = f\left(\begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}\right) = \begin{pmatrix} 0 + 1 + 0 \\ 0 \\ 1\end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix} \\ f(\boldsymbol{e}_3) = f\left(\begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}\right) = \begin{pmatrix} 0 + 0 + 1 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} \end{gather}$

より，

$\displaystyle \begin{equation} A = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{pmatrix} \end{equation}$

となります．

$\displaystyle \begin{equation} A \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} x_1 + x_2 + x_3 \\ x_1 \\ x_2 \end{pmatrix} \end{equation}$

より， $A$ は $f$ と同じ変換を表すことが分かります．

上の計算を丁寧に書くと以下のようになります．計算には変換の線形性が利用されています．

$\displaystyle \begin{align} A \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} & = A(x_1 \boldsymbol{e}_1 + x_2 \boldsymbol{e}_2 + x_3 \boldsymbol{e}_3) \\ & = x_1 A \boldsymbol{e}_1 + x_2 A \boldsymbol{e}_2 + x_3 A \boldsymbol{e}_3 \hspace{10pt} (\because \text{変換の線形性}) \\ & = x_1 \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix} + x_2 \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix} + x_3 \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} \\ & = \begin{pmatrix} x_1 + x_2 + x_3 \\ x_1 \\ x_2 \end{pmatrix} \end{align}$

$A$ による $n$ 回の変換は行列の累乗 $A^n$ で表されるので， $\boldsymbol{t}_n$ は以下の式で計算できます．

$\displaystyle \begin{equation} \boldsymbol{t}_n = A^n \boldsymbol{t}_0 = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} \end{equation}$

ただし， $A^0$ は恒等変換を表す単位行列とします．

$\boldsymbol{t}_n = \begin{pmatrix} T_{n+2} \\ T_{n+1} \\ T_n \end{pmatrix}$ より， $T_n$ は $\boldsymbol{t}_n$ の第3成分として求めることができます．これは $A^n$ の $(3, 1)$ 成分に一致します．

例えば $T_8$ は

$\displaystyle \begin{equation} \boldsymbol{t}_8 = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}^8 \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 81 & 68 & 44 \\ 44 & 37 & 24 \\ 24 & 20 & 13 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 81 \\ 44 \\ 24 \end{pmatrix} \end{equation}$

より， $24$ であると分かります．

$n$ が大きいとき， $A^n$ の計算に繰り返し2乗法を用いることで計算の高速化を図ることができます．

一般化

フィボナッチ数列やトリボナッチ数列を一般化した数列として，最初の $N$ 項を初期値とし， $N+1$ 項目以降を直前の $N$ 項の和として定めた数列 $F = (F_0, F_1, F_2, \cdots)$ を考えます． $F_n$ は以下の式により求められるベクトルの第 $N$ 成分として求めることができます．

$\displaystyle \begin{equation} \begin{pmatrix} 1 & 1 & 1 & & 1 & 1 & 1 \\ 1 & 0 & 0 & \cdots & 0 & 0 & 0 \\ 0 & 1 & 0 & & 0 & 0 & 0 \\ & \vdots & & \ddots & & \vdots & \\ 0 & 0 & 0 & & 0 & 0 & 0 \\ 0 & 0 & 0 & \cdots & 1 & 0 & 0 \\ 0 & 0 & 0 & & 0 & 1 & 0 \\ \end{pmatrix}^n \begin{pmatrix} F_{N-1} \\ F_{N-2} \\ F_{N-3} \\ \vdots \\ F_2 \\ F_1 \\ F_0 \end{pmatrix} \end{equation}$

$N = 2, F_0 = 0, F_1 = 1$ のとき $F$ はフィボナッチ数列となり， $F_n$ は以下で計算されるベクトルの第2成分として求めることができます．

$\displaystyle \begin{equation} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \\ 0 \end{pmatrix} \end{equation}$

$N = 4, F_0 = F_1 = F_2 = 0, F_3 = 1$ のとき $F$ はテトラナッチ数列となり， $F_n$ は以下で計算されるベクトルの第4成分として求めることができます．

$\displaystyle \begin{equation} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ \end{pmatrix}^n \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} \end{equation}$

*1:行列との関係を観察しやすそうだったので，フィボナッチ数列ではなくトリボナッチ数列を中心に考えます．

2023-07-26

包除原理の拡張を考える

多次元累積和を用いて多次元配列の矩形範囲の総和を計算するときに必要になったので，包除原理の拡張を考えました．

全体集合 $\Omega$ の $n (\geq 1)$ 個の部分集合 $A_1, A_2, \cdots , A_n$ と写像 $f\colon\Omega\to\mathbb{R}$ を考えます．このとき，和集合 $\bigcup_{i=1}^n A_i$ の全ての要素の $f$ による像の総和 $\sum_{a\in\bigcup_{i=1}^n A_i} f(a)$ について次の等式が成り立ちます．

$\displaystyle \sum_{a\in\bigcup_{i=1}^n A_i} f(a) = \sum_{k=1}^n (-1)^{k+1} \sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n} \sum_{a\in\bigcap_{j=1}^k A_{i_j}} f(a)$

$\forall_{a\in\Omega} f(a)=1$ のとき，和集合の要素数 $|\bigcup_{i=1}^n A_i|$ を計算する通常の包除原理と一致します．

証明

数学的帰納法を用いて証明します．

まず， $n=1$ ，即ち集合が1個のときを考えると，

$\displaystyle (\text{左辺}) = (\text{右辺}) = \sum_{a\in A_1} f(a)$

より成り立ちます．

次に， $n(n \geq 1)$ 個の集合について成り立つと仮定し， $n+1$ 個の集合について考えます．

$\displaystyle \begin{align} (\text{左辺}) & = \sum_{a \in \bigcup_{i=1}^{n+1} A_i} f(a) \\ & = \sum_{a \in (\bigcup_{i=1} A_i)\cup A_{n+1}} f(a) \\ & = \sum_{a \in \bigcup_{i=1}^n A_i} f(a) + \sum_{a \in A_{n+1}} f(a) - \sum_{a \in (\bigcup_{i=1}^n A_i)\cap A_{n+1}} f(a) \\ & = \sum_{k=1}^n (-1)^{k+1} \sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n} \sum_{a\in\bigcap_{j=1}^k A_{i_j}} f(a) + \sum_{a \in A_{n+1}} f(a) - \sum_{a \in (\bigcup_{i=1}^n (A_i \cap A_{n+1}))} f(a) \\ \end{align}$

ここで，

$\displaystyle \begin{align} \sum_{a \in (\bigcup_{i=1}^n (A_i \cap A_{n+1}))} f(a) & = \sum_{k=1}^n (-1)^{k+1} \sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n} \sum_{a\in\bigcap_{j=1}^k (A_{i_j} \cap A_{n+1})} f(a) \\ & = \sum_{k=2}^{n+1} (-1)^k \sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n+1} \sum_{a \in \bigcap_{j=1}^k A_{i_j}} f(a) - \sum_{k=2}^n (-1)^k \sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n} \sum_{a \in \bigcap_{j=1}^k A_{i_j}} f(a) \\ & = -\sum_{k=2}^{n+1} (-1)^{k+1} \sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n+1} \sum_{a \in \bigcap_{j=1}^k A_{i_j}} f(a) + \sum_{k=2}^n (-1)^{k+1} \sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n} \sum_{a \in \bigcap_{j=1}^k A_{i_j}} f(a) \end{align}$

より，

$\displaystyle \begin{align} (\text{左辺}) & = \sum_{k=1}^1 (-1)^{k+1} \sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n} \sum_{a\in\bigcap_{j=1}^k A_{i_j}} f(a) + \sum_{a \in A_{n+1}} f(a) + \sum_{k=2}^{n+1} (-1)^{k+1} \sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n+1} \sum_{a \in \bigcap_{j=1}^k A_{i_j}} f(a) \\ & = \sum_{i=1}^{n+1} \sum_{a \in A_i} f(a) + \sum_{k=2}^{n+1} (-1)^{k+1} \sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n+1} \sum_{a \in \bigcap_{j=1}^k A_{i_j}} f(a) \\ & = \sum_{k=1}^{n+1} (-1)^{k+1} \sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n+1} \sum_{a \in \bigcap_{j=1}^k A_{i_j}} f(a) \\ & = (\text{右辺}) \end{align}$

よって， $n+1$ 個の集合についても成り立ちます．

以上より，全ての正の整数 $n$ について成り立つことが示されました．