まとめ

文字列の識別を DFA として表現することで、複数の条件や状態遷移を分けて記述し、これらの組み合わせで桁DPを構成するフレームワークが出来ました！

いかがでしたか？

参考文献は以下の通りです。ありがとうございました。

水谷 正大, オートマトンと言語理論

決定性有限オートマトン - Wikipedia

オートマトン上の DP (桁 DP の一般化) - kuretchi’s blog

数学が多少出てきますが、面倒であれば実装＆問題例に飛んでも問題ありません。何をやりたいかは十分掴めると思います。

追記（ツイートの記録）

文字列

有限個の記号集合 $\Sigma$ をアルファベットとし、$\Sigma$ の要素を並べたものを文字列（または語）とします。

長さ $n$ の文字列全体の集合を $\Sigma^n$ とします。

任意の長さの文字列全体の集合を $\Sigma^* = \Sigma^0 \cup \Sigma^1 \cup \Sigma^2 \cup \cdots$ とします。

有限オートマトン

有限個の状態と遷移と動作の組み合わせからなる数学的に抽象化された「ふるまいのモデル」である。

出典：有限オートマトン - Wikipedia

文字列から文字を $1$ 文字ずつ読み取りながら、内部状態を遷移させていく機構。

有限オートマトンには、次のような種類があります。

  • 決定的有限オートマトン（DFA）
  • 非決定的有限オートマトン（NFA）
  • $\varepsilon$動作を含む非決定的有限オートマトン（$\varepsilon$-NFA）

ここでは DFA のみを扱います。

決定性有限オートマトン（DFA)

決定性有限オートマトン（Deterministic Finite Automaton）は、現在の内部状態と受け取った文字によって次の状態が一意に定まるような有限オートマトン。

最終的な内部状態に応じて、入力文字列を受理(accept)するかどうかを決定します（文字列の識別）。

形式的な定義は次の通りです。

$M = (Q, \Sigma, \delta, q_0, F)$ であって、以下の性質を満たすものを DFA とする。

$Q$：有限集合（状態集合）

$\Sigma$：有限集合（文字集合）

$\delta : Q \times \Sigma \rightarrow Q$（遷移関数）

$q_0 \in Q$（初期状態）

$F \subset Q$（受理状態の集合）

文字列 $a = a_0a_1\cdots a_{n-1}$ が与えられたとき、各 $i=0,\ldots,n-1$ について帰納的に

$$ q_{i+1} = \delta(q_i, a_i) $$

とおく。$q_n \in F$ であることを、$A$ が文字列 $a$ を受理するという。

見た目が怖いようですが、読んでみるとそんなに怖くない。数学が苦しければ、下の実装＆問題例にある Dfa トレイトを参照してください。$M$ とは machine の頭文字であると思われます（たぶん）

また、$M$ という DFA が受理する文字列全体を、$M$ によって受理される言語 $L(M)$ といいます。

やってみよう（桁DPっぽいやつ）

次のような言語 $L_{3mul}$ を考えます。

$$ L_{3mul} = \{ x \in \{0, 1\}^* \mid x \text{は $3$ の倍数の$2$進数表示}\} $$

これを受理する DFA 、$M_{3mul} = (Q, \Sigma, \delta, q_0, F)$ を構成しましょう。

ただし空文字列 $\varepsilon$ は $0$ に対応すると考えて $\varepsilon \in L_{3mul}$ とします。

状態集合、文字集合、受理状態の集合をそれぞれ次のように定義します。

$$ \begin{aligned} Q &= \{q_0, q_1, q_2\} \\ \Sigma &= \{0, 1\} \\ F &= \{q_0\} \end{aligned} $$

状態 $q_i$ は $x \equiv i \pmod 3$ であることを表しています。

遷移関数 $\delta$ は、次の遷移表の通りになります。

input $0$ $1$
$q_0$ $q_0$ $q_1$
$q_1$ $q_1$ $q_2$
$q_2$ $q_2$ $q_0$

こうして $L_{3mul}$ を受理する DFA $M_{3mul}$ が構成されました。

3の倍数判定機の完成です。

同様に、「$L$ 以下」や「いずれかの桁に $3$ を含む」といったさまざまな識別を行うDFAを、ループで行う基本的な桁DPと全く同じ要領で構成できます。$DP[i][\mathrm{state}]$ として書いていたところ、$\mathrm{state}$ や $i$ を $Q$ として持つということです。

それでは桁DPを書く上で DFA はどのように役に立つのでしょうか。

DFA から DFA を構成

ある文字集合 $\Sigma$ 上の $2$ つの DFA、$M_1 = (Q_1, \Sigma, \delta_1, q_{10}, F_1)$ と $M_2 = (Q_2, \Sigma, \delta_2, q_{20}, F_2)$ が与えられたとします。

この $2$ つがどちらも受理する文字列を、その場合に限り受理する DFA $M = (Q, \Sigma, \delta, q_0, F)$ を構成してみます。$M_1$ “かつ” $M_2$ のイメージです。

$$ \begin{aligned} Q &= Q_1 \times Q_2 \\ \delta((q_{1i}, q_{2i}), a_i) &= (\delta_1(q_{1i}, a_i), \delta_2(q_{2i}, a_i)) \\ q_0 &= (q_{10}, q_{20}) \\ F &= F_1 \cap F_2 \end{aligned} $$

$M$ が $M_1,M_2$ を保持していて、それぞれに同じ文字列を与え、どちらも受理されたら $M$ も受理する、というような形です。

ここで、たとえば $\Sigma = \{0,1,\ldots, 9\}$ として、$M_1$ は与えられた文字列が $3$ の倍数であるかを識別し、$M_2$ は $L$ 以下であるかどうかを判定するとしましょう。

これらから構成された $M$ は、$L$ 以下の $3$ の倍数を受理します。

いったんこれらを書いておけば、桁DPが出るたびに tight や何やを管理したり複雑な条件分岐を書いたりせず、適当な DFA を組み合わせるだけでよくなります！

実装＆問題例

ここから、簡単な要素の組み合わせで複雑な判定や数え上げが行えることを示したいです。DFAを定義しながら、AtCoder の問題を $3$ つ解いていきます。

DFA が行うべき振る舞いを表す DFA トレイトを定義します。Rustです。trait は Java の interface のようなやつです。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

trait Dfa {
    type Alphabet;
    type State;
    fn init(&self) -> Self::State;
    fn next(&self, s: Self::State, a: Self::Alphabet, i: usize) -> Self::State;
    fn accept(&self, s: Self::State) -> bool;
    fn successful(&self, _: Self::State) -> bool {
        false
    }
    fn unsuccessful(&self, _: Self::State) -> bool {
        false
    }
}

next の第三引数 i は、文字 a が文字列中の何番目の文字であるかを表しています。本来はこれを State に持たせて next のたびにインクリメントすればいいんですが、$2$ つの場所で i を管理するのはなんかなあと思ったのと、場合によって多少速くなります。

successful と unsuccessful は枝刈り用の関数で、実装はオプショナルです。Option などのイケてる構造体を使わないのはうーんという感じなんですが、扱いやすいと思いました。

次に、DFA が受理する長さ $n$ の文字列を数える関数を定義します。いわゆる「配るDP」です。

 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
31
32
33

use std::collections::HashMap;
use std:#️⃣:Hash;

fn count<X: Dfa>(dfa: &X, n: usize, modulo: u32, alphabet: &[X::Alphabet]) -> u32
where
    X::Alphabet: Copy,
    X::State: Eq + Hash + Copy,
{
    let mut dp = HashMap::new();
    let mut dp2 = HashMap::new();
    dp.insert(dfa.init(), 1_u64);
    for i in 0..n {
        for (s, k) in dp.drain() {
            let k = k % modulo as u64;
            for &a in alphabet {
                let s1 = dfa.next(s, a, i);
                if dfa.unsuccessful(s1) {
                    continue;
                }
                *dp2.entry(s1).or_insert(0) += k;
            }
        }
        std::mem::swap(&mut dp, &mut dp2);
    }
    let mut sum = 0;
    for (s, k) in dp {
        if dfa.accept(s) {
            sum += k;
            sum %= modulo as u64
        }
    }
    sum as u32
}

HashMap で 状態 => 個数 を管理しています。配列の添え字に状態を持たせた方が速いのはそうなんですが、往々にして状態数はそこまで大きくならないですしというところです。

BTreeMap でもよいですが、状態数が増えたときに HashMap の方が速い気がしました。気のせいという説もあります。

また今回は個数を持ちまわしていますが、これは何かしらの構造に一般化できます。kuretchiさんのブログもご参照ください。個数の代わりに総和 mod M を求める例もあります。

問題に移ります。

TDPC-E 数

$N$ 以下の正整数であって、十進法表記したときの各桁の数の和が $D$ の倍数であるものの個数を $\mathrm{mod} 1,000,000,007$ で求めよ。

まず、$N$ 以下を表現する DFA を実装します。$N$ は上界が $10^{10000}$ と大きいので、文字列（バイト列）（への参照）として持たせます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

use std::cmp::Ordering;

struct Leq<'a>(&'a [u8]);

impl Dfa for Leq<'_> {
    type Alphabet = u8;
    type State = Ordering;
    fn init(&self) -> Self::State {
        Ordering::Equal
    }
    // assumes i moves from 0 to self.0.len() - 1
    fn next(&self, s: Self::State, a: Self::Alphabet, i: usize) -> Self::State {
        s.then(a.cmp(&self.0[i]))
    }
    fn accept(&self, s: Self::State) -> bool {
        s != Ordering::Greater
    }
    fn successful(&self, s: Self::State) -> bool {
        s == Ordering::Less
    }
    fn unsuccessful(&self, s: Self::State) -> bool {
        s == Ordering::Greater
    }
}

tight などのフラグ変数の代わりに、Ordering によって状態が自然に表現されたことは驚きでした。これは $N$ と入力文字列を 0 から i 桁目までで比較した結果を表しています。

x.then(y) は $2$ つの比較結果 x、y を結合します。x 優先であり、x != Ordering::Equal ならば x を、そうでない場合は y を返します。

次は、桁和が $D$ の倍数であることを表す DFA です。状態は毎回 $\mathrm{mod}$ を取ります。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

struct DigitSumMultipleOf(u32);

impl Dfa for DigitSumMultipleOf {
    type Alphabet = u8;
    type State = u32;
    fn init(&self) -> Self::State {
        0
    }
    fn next(&self, s: Self::State, a: Self::Alphabet, _: usize) -> Self::State {
        (s + (a - b'0') as u32) % self.0
    }
    fn accept(&self, s: Self::State) -> bool {
        s == 0
    }
}

受け取る文字列がこれらの双方に受理されることが必要十分です。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

struct And<X, Y>(X, Y);

impl<X: Dfa<Alphabet = A>, Y: Dfa<Alphabet = A>, A: Copy> Dfa for And<X, Y> {
    type Alphabet = A;
    type State = (X::State, Y::State);
    fn init(&self) -> Self::State {
        (self.0.init(), self.1.init())
    }
    fn next(&self, (s0, s1): Self::State, a: Self::Alphabet, i: usize) -> Self::State {
        (self.0.next(s0, a, i), self.1.next(s1, a, i))
    }
    fn accept(&self, (s0, s1): Self::State) -> bool {
        self.0.accept(s0) && self.1.accept(s1)
    }
    fn successful(&self, (s0, s1): Self::State) -> bool {
        self.0.successful(s0) && self.1.successful(s1)
    }
    fn unsuccessful(&self, (s0, s1): Self::State) -> bool {
        self.0.unsuccessful(s0) || self.1.unsuccessful(s1)
    }
}

以上は一度書いたら使い回せるものたちです。桁DPでよく出てくる要素だと思います。

煩雑なようですが、かなりの部分を関数のシグネチャが占めており、これは一瞬で補完してくれます（rust-analyzer に感謝）

あとは And(Leq(N), DigitSumMultipleOf(D)) が受理する文字列を count して終了です。0 を除外するため、結果から 1 を引いておきます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

use proconio::{input, marker::Bytes};

fn main() {
    input! {
        d: u32,
        n: Bytes,
    }
    let dfa = And(Leq(&n), DigitSumMultipleOf(d));
    let alphabet = "0123456789".as_bytes();
    let ans = count(&dfa, n.len(), 1_000_000_007, alphabet);
    println!("{}", ans - 1);
}

提出 257 ms, 2.2MB

案外、十分な速度になりました。

JOI2012yo-F ジグザグ数

（要約）

各桁の数が「…→増加→減少→増加→減少→…」となっている正の整数を「ジグザグ数」と呼ぶ。

ジグザグ数の例）$2947$、$71946$

ジグザグ数でない例）$123$、$71446$

なお、$1$ 桁の正の整数はジグザグ数であるとする。

$A$ 以上 $B$ 以下の $M$ の倍数であるジグザグ数の個数を $\mathrm{mod} 10000$ で求めよ。

x >= A は !(x < A) と表せるので、Not と Lt を実装します。後者は Leq とほとんど同じです。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

struct Not<X>(X);

impl<X: Dfa> Dfa for Not<X> {
    type Alphabet = X::Alphabet;
    type State = X::State;
    fn init(&self) -> Self::State {
        self.0.init()
    }
    fn next(&self, s: Self::State, a: Self::Alphabet, i: usize) -> Self::State {
        self.0.next(s, a, i)
    }
    fn accept(&self, s: Self::State) -> bool {
        !self.0.accept(s)
    }
    fn successful(&self, s: Self::State) -> bool {
        self.0.unsuccessful(s)
    }
    fn unsuccessful(&self, s: Self::State) -> bool {
        self.0.successful(s)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

struct Lt<'a>(&'a [u8]);

impl Dfa for Lt<'_> {
    type Alphabet = u8;
    type State = Ordering;
    fn init(&self) -> Self::State {
        Ordering::Equal
    }
    // assumes i moves from 0 to self.0.len() - 1
    fn next(&self, s: Self::State, a: Self::Alphabet, i: usize) -> Self::State {
        s.then(a.cmp(&self.0[i]))
    }
    fn accept(&self, s: Self::State) -> bool {
        s == Ordering::Less
    }
    fn successful(&self, s: Self::State) -> bool {
        s == Ordering::Less
    }
    fn unsuccessful(&self, s: Self::State) -> bool {
        s == Ordering::Greater
    }
}

次に、$M$ の倍数 DFA です。DigitSumMultipleOf とほとんど同じです。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

struct MultipleOf(u32);

impl Dfa for MultipleOf {
    type Alphabet = u8;
    type State = u32;
    fn init(&self) -> Self::State {
        0
    }
    fn next(&self, s: Self::State, a: Self::Alphabet, _: usize) -> Self::State {
        (s * 10 + (a - b'0') as u32) % self.0
    }
    fn accept(&self, s: Self::State) -> bool {
        s == 0
    }
}

完成です。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

use proconio::{input, marker::Bytes};

fn main() {
    input! {
        a0: Bytes,
        b: Bytes,
        m: u32,
    }
    let mut a = vec![b'0'; b.len()];
    a[b.len() - a0.len()..].copy_from_slice(&a0);

    let dfa = And(ZigZag, And(MultipleOf(m), And(Leq(&b), Not(Lt(&a)))));
    let alphabet = "0123456789".as_bytes();
    let ans = count(&dfa, a.len(), 10000, alphabet);
    println!("{}", ans);
}

a が整数型に収まらないときの 0 詰めで、うまいやり方があれば教えてください。

提出 1566 ms, 3.0 MB

JOI ということもあってか、状態数が多いです。TL（10 sec）に対しては余裕ですが、他の提出と比べるといくらか遅めのようです。

ABC138-F Coincidence

解説の通り、これは次の問題に帰着されます。

次の条件を満たす整数の組 $(x, y)$ の個数を求めよ。

  • $x \geq L$
  • $y \leq R$
  • $x$ と $y$ の MSB（最上位ビット）の位置が同じ
  • $2$ 進数での各桁 $i$ について、$x_i \leq y_i$

$3$ つめと $4$ つめに対応する SameMsb、Subset を実装します。

$2$ つのバイナリ列 $x,y$ を同時に読み込んでいくことを考え、文字集合はバイトの対としています。

 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

struct SameMsb;

impl Dfa for SameMsb {
    type Alphabet = (u8, u8);
    type State = Option<bool>;
    fn init(&self) -> Self::State {
        None
    }
    fn next(&self, s: Self::State, (a0, a1): Self::Alphabet, _: usize) -> Self::State {
        if s.is_none() && (a0, a1) != (b'0', b'0') {
            Some(a0 == a1)
        } else {
            s
        }
    }
    fn accept(&self, s: Self::State) -> bool {
        s != Some(false)
    }
    fn successful(&self, s: Self::State) -> bool {
        s == Some(true)
    }
    fn unsuccessful(&self, s: Self::State) -> bool {
        s == Some(false)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

struct Subset;

impl Dfa for Subset {
    type Alphabet = (u8, u8);
    type State = bool;
    fn init(&self) -> Self::State {
        true
    }
    fn next(&self, s: Self::State, (a0, a1): Self::Alphabet, _: usize) -> Self::State {
        s && a0 <= a1
    }
    fn accept(&self, s: Self::State) -> bool {
        s
    }
    fn unsuccessful(&self, s: Self::State) -> bool {
        !s
    }
}

$x \geq L$、$y \leq R$ という制約を表現するため、$2$ つの文字列それぞれに DFA を独立に走らせる Prod を定義します。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

struct Prod<X, Y>(X, Y);

impl<X: Dfa, Y: Dfa> Dfa for Prod<X, Y> {
    type Alphabet = (X::Alphabet, Y::Alphabet);
    type State = (X::State, Y::State);
    fn init(&self) -> Self::State {
        (self.0.init(), self.1.init())
    }
    fn next(&self, (s0, s1): Self::State, (a0, a1): Self::Alphabet, i: usize) -> Self::State {
        (self.0.next(s0, a0, i), self.1.next(s1, a1, i))
    }
    fn accept(&self, (s0, s1): Self::State) -> bool {
        self.0.accept(s0) && self.1.accept(s1)
    }
    fn successful(&self, (s0, s1): Self::State) -> bool {
        self.0.successful(s0) && self.1.successful(s1)
    }
    fn unsuccessful(&self, (s0, s1): Self::State) -> bool {
        self.0.unsuccessful(s0) || self.1.unsuccessful(s1)
    }
}

これらを適当に組み合わせ、AC です。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


use proconio::input;

fn main() {
    input! {
        l: u64,
        r: u64,
    }
    let r = format!("{:b}", r).into_bytes();  // 2 進法でバイト列化
    let l = format!("{:0width$b}", l, width = r.len()).into_bytes();  // b の長さに 0 詰め

    let dfa = And(Prod(Not(Lt(&l)), Leq(&r)), And(SameMsb, Subset));
    let alphabet = [(b'0', b'0'), (b'0', b'1'), (b'1', b'0'), (b'1', b'1')];
    let ans = count(&dfa, r.len(), 1_000_000_007, &alphabet);
    println!("{}", ans);
}

提出 7 ms, 2.2 MB

まとめ

文字列の識別を DFA として表現することで、複数の条件や状態遷移を分けて記述し、これらの組み合わせで桁DPを構成するフレームワークが出来ました！

いかがでしたか？