kuretchi's blog

kuretchi's blog

競技プログラミングなどなど...

Rust で自動メモ化マクロ

作ってしまいました.かなり雑.Rust 1.15.1 で動きます.

macro_rules! __memoize_internal {
  (@vec $FRetT:ty) => {
    Option<$FRetT>
  };
  (@vec $FRetT:ty, $memo_param_head:ident $(, $memo_param:ident)*) => {
    Vec<__memoize_internal!(@vec $FRetT $(, $memo_param)*)>
  };
  (@indices [$($t:tt)*]) => {
    [$($t)*]
  };
  (
    @indices [$($t:tt)*]
    $memo_param_head:ident
    $(, $memo_param:ident $(($memo_param_expr:expr))*)*
  ) => {
    __memoize_internal!(
      @indices [$($t)* $memo_param_head as usize,] $($memo_param $(($memo_param_expr))*),*
    )
  };
  (
    @indices [$($t:tt)*]
    $memo_param_head:ident($memo_param_expr_head:expr)
    $(, $memo_param:ident $(($memo_param_expr:expr))*)*
  ) => {
    __memoize_internal!(
      @indices [$($t)* $memo_param_expr_head(&$memo_param_head),]
      $($memo_param $(($memo_param_expr))*),*
    )
  };
  (@get $memo:expr, $indices:expr, $i:expr) => {
    $memo
  };
  (@get $memo:expr, $indices:expr, $i:expr, $memo_param_head:ident $(, $memo_param:ident)*) => {
    __memoize_internal!(
      @get $memo.and_then(|memo| memo.get($indices[$i])), $indices, $i + 1 $(, $memo_param)*
    )
  };
  (@resize $memo:expr, $indices:expr, $i:expr) => {};
  (@resize $memo:expr, $indices:expr, $i:expr, $memo_param_head:ident $(, $memo_param:ident)*) => {
    if $memo.len() < $indices[$i] + 1 {
      $memo.resize($indices[$i] + 1, <_>::default());
    }
    __memoize_internal!(
      @resize $memo[$indices[$i]], $indices, $i + 1 $(, $memo_param)*
    )
  };
  (@index $memo:expr, $indices:expr, $i:expr) => {
    $memo
  };
  (@index $memo:expr, $indices:expr, $i:expr, $memo_param_head:ident $(, $memo_param:ident)*) => {
    __memoize_internal!(
      @index $memo[$indices[$i]], $indices, $i + 1 $(, $memo_param)*
    )
  };
}

macro_rules! memoize {
  (
    #[memo_param($($memo_param:ident $(($memo_param_expr:expr))*),+)]
    $(#[$meta:meta])*
    fn $f:ident($memo:ident: _ $(, $f_param:ident: $FParamT:ty)*) -> $FRetT:ty $f_body:block
  ) => {
    $(#[$meta])*
    fn $f(
      $memo: &mut __memoize_internal!(@vec $FRetT $(, $memo_param)+)
      $(, $f_param: $FParamT)+
    ) -> $FRetT {
      let indices = __memoize_internal!(@indices [] $($memo_param $(($memo_param_expr))*),+);

      if let Some(&Some(ref ret)) =
        __memoize_internal!(@get Some(&$memo), indices, 0 $(, $memo_param)+)
      {
        return ret.clone();
      }

      let ret = $f_body;

      __memoize_internal!(@resize $memo, indices, 0 $(, $memo_param)+);
      __memoize_internal!(@index $memo, indices, 0 $(, $memo_param)+) = Some(ret.clone());

      ret
    }
  };
}

これは何

例えば,$n$ 番目のフィボナッチ数を求める関数:

fn fib(n: usize) -> u64 {
  match n {
    0 => 1,
    1 => 1,
    n => fib(n - 1) + fib(n - 2),
  }
}

これをメモ化したいです.真面目にやるとこんな実装になります:

fn fib(memo: &mut Vec<Option<u64>>, n: usize) -> u64 {
  if let Some(&Some(fib_n)) = memo.get(n) {
    return fib_n;
  }

  let fib_n = match n {
    0 => 1,
    1 => 1,
    n => fib(memo, n - 2) + fib(memo, n - 1),
  };

  if memo.len() < n + 1 {
    memo.resize(n + 1, None);
  }

  memo[n] = Some(fib_n);

  fib_n
}

これを毎回書くのはちょっとつらいです.また,引数が増えるとさらに面倒になります.という訳で,このボイラープレートを自動生成するのが今回紹介する memoize マクロです.

今回の場合は次のように実装できます:

memoize! {
  #[memo_param(n)]
  fn fib(memo: _, n: usize) -> u64 {
    match n {
      0 => 1,
      1 => 1,
      n => fib(memo, n - 1) + fib(memo, n - 2),
    }
  }
}

元のコードとほとんど形が変わっていませんね.

使い方

こんな風に使います.これは竹内関数の実装ですが,説明のためにいろいろと無駄な書き方をしています.雰囲気を感じ取ってくだされば.

memoize! {
  #[memo_param(x_y(|&(x, y)| x as usize * 1000 + y as usize), z)]
  fn tarai(memo: _, x_y: (u64, u64), z: u64, hoge: i32) -> u64 {
    let (x, y) = x_y;
    assert!(y < 1000);
    if x <= y {
      y
    } else {
      let p = tarai(memo, (x - 1, y), z, hoge);
      let q = tarai(memo, (y - 1, z), x, hoge);
      let r = tarai(memo, (z - 1, x), y, hoge);
      tarai(memo, (p, q), r, hoge)
    }
  }
}

#[memo_param(...)] でメモ化する際の引数 (関数の返り値が依存する引数) を指定します.実行時に決まる定数 (問題の入力や,前計算で生成した何らかのテーブルなど) を引数として渡している場合はここで指定しないようにします.

メモはすべて Vec に取るようになっているので1,引数は (ある程度小さい) usize の添字に変換できる必要があります.この変換には as usize を用いています.変換を明示的に指定したい場合は #[memo_param(x(f))] の構文を使うことができます.f が変換する関数で,概ね fn(&T) -> usize2 (ただし Tx の型) であればよいです.

memo の名前は何でも良いですが,必ず第一引数としてください.この型はマクロが生成するので _ とします (&mut Vec<Vec< ... <Option<T>> ... >> のような型になります (ただし T は関数の返り値)).

関数の返り値の型は Clone を実装している必要があります.

使用例

ABC099 C - Strange Bank に対する解答を挙げます.

const MAX_N: u64 = 100000;

let coins = {
  let mut vec = vec![1];
  fn create_table(base: u64, vec: &mut Vec<u64>) {
    let mut crt = base;
    while crt <= MAX_N {
      vec.push(crt);
      crt *= base;
    }
  }
  create_table(6, &mut vec);
  create_table(9, &mut vec);
  vec.sort();
  vec
};

memoize! {
  #[memo_param(price)]
  fn count(memo: _, price: u64, coins: &[u64]) -> usize {
    if price == 0 {
      0
    } else {
      coins
        .iter()
        .filter(|&&coin| coin <= price)
        .map(|&coin| 1 + count(memo, price - coin, coins))
        .min()
        .unwrap()
    }
  }
}

let n = scan!(u64); // 入力
let ans = count(&mut vec![], n, &coins);

println!("{}", ans);

  1. 改良の余地あり.

  2. クロージャでもいけます.何か変なものをキャプチャしていると険しいかも.この辺は適当 (詳しくは実装を見てください).

ラッパーの参照と参照のラッパー

何かをラップした構造体を作ることがよくある.例えば,何らかの 1 ワードの値 hoge を常に引き回す必要があるとき:

struct Value {}

impl Value {
  fn f0(&self, hoge: usize) {}
  fn f1(&self, hoge: usize, fuga: i32) {}
  // ...
}

こんな構造体を作って,Deref を実装する.

struct WithHoge<T> {
  hoge: usize,
  inner: T,
}

impl<T> Deref for WithHoge<T> {
  type Target = T;

  fn deref(&self) -> &T {
    &self.inner
  }
}

しめしめ.これでさっきの例はこう書けるぞ.

impl WithHoge<Value> {
  fn f0(&self) {}
  fn f1(&self, fuga: i32) {}
  // ...
}

と思いきや,これは適切ではない.正しくはこう.

impl WithHoge<&Value> {
  fn f0(self) {}
  fn f1(self, fuga: i32) {}
  // ...
}

Rust の多次元 Vec を初期化するマクロ

小ネタ.

Rust で多次元 Vec (dp[0][1][2] のように使えるもの) を作りたい.例えば None で初期化された $2 \times 3 \times 4$ の Vec<Vec<Vec<Option<T>>>> を作るときはこう書く.

vec![vec![vec![None; 4]; 3]; 2]

うーん.という訳でこんなマクロ.

macro_rules! nested_vec {
  ($e:expr; $n:expr) => {
    vec![$e; $n]
  };
  ($e:expr; $n:expr $(; $m:expr)+) => {
    vec![nested_vec!($e $(; $m)+); $n]
  };
}

こんな風に書ける.

nested_vec![None; 2; 3; 4]

桁 DP の一般化 (オートマトン DP)

桁 DP を用いると,与えられた条件を満たす数 (主に整数) の集合に対応するなんらかの値 (例えば,要素の個数など) を求めることができます.

本記事では,桁を文字,数を文字列と考え,桁 DP の状態と遷移をオートマトン上で扱うことで,様々な桁 DP の問題に一般的なアルゴリズムを与えるオートマトン DP1 を紹介します.

準備

  • 集合 X の冪集合を \mathfrak{P}(X) とします.
  • 有限集合 X の元の個数を \lvert X \rvert とします.
  • 文字集合 \Sigma 上の文字列の集合を \Sigma^* とし,そのうち長さ l である文字列の集合を \Sigma^l とします.
  • 文字列 s \in \Sigma^* と文字 c \in \Sigma について,s の末尾に c を追加した文字列を s . c とします.
  • 空文字列を \epsilon とします (\Sigma^0 = \{\epsilon\}).

できること

文字集合\Sigma とします.

ある文字列集合 S \subseteq \Sigma^* について,何らかの値 f(S) \in T を与える写像 f : \mathfrak{P}(\Sigma^*) \rightarrow T を考えます. 決定性有限オートマトン (以下 DFA) A と,l \in \mathbb{N} が与えられたとき,A が受理する長さ l の文字列の集合 S について,f(S) を,O(\lvert \Sigma \rvert \times \lvert (A \text{の状態集合}) \rvert \times l) 程度の計算量で求めることができます2

ただし,Al の他に以下を要求します.

  • \forall S_1, S_2 \in \mathfrak{P}(\Sigma^*) [S_1 \cap S_2 = \emptyset \Longrightarrow f(S_1) \oplus f(S_2) = f(S_1 \cup S_2)] を満たすような二項演算 \oplus : T \times T \rightarrow T
  • \forall S \in \mathfrak{P}(\Sigma^*)[\forall c \in \Sigma [f(S) \triangleleft c = f(\{s . c \mid s \in S\})]] を満たすような (外部) 二項演算 \triangleleft : T \times \Sigma \rightarrow T
  • f(\Sigma^0)
  • (f(\emptyset))3

方法

DFA A の状態集合を Q,遷移関数を \delta : Q \times \Sigma \rightarrow Q,初期状態を q_0 \in Q,受理状態の集合を F \subseteq Q とします. また,初期状態の A に与えたとき,状態 q \in Q に遷移するような長さ n の文字列の集合を S(q, n) \subseteq \Sigma^n とします.

f(S(q_0, 0)) = f(\Sigma^0) であり,最終的に求めたいものは f(\bigcup_{q \in F} S(q, l)) です.

ここで,S の定義より,

   \displaystyle \forall q_i \in Q [\forall n \in \mathbb{N} [S(q_i, n + 1) = \bigcup_{(q_j, c) \in Q \times \Sigma \land \delta(q_j, c) = q_i} \{s . c \mid s \in S(q_j, n)\}]]

\forall q_i, q_j \in Q [\forall m, n \in \mathbb{N} [m \ne n \Longrightarrow S(q_i, m) \cap S(q_j, n) = \emptyset]] であることと,\oplus の定義より,

   \displaystyle \forall q_i \in Q [\forall n \in \mathbb{N} [f(S(q_i, n + 1)) = \bigoplus_{(q_j, c) \in Q \times \Sigma \land \delta(q_j, c) = q_i} f(\{s . c \mid s \in S(q_j, n)\})]]

\triangleleft の定義より,

   \displaystyle \forall q_i \in Q [\forall n \in \mathbb{N} [f(S(q_i, n + 1)) = \bigoplus_{(q_j, c) \in Q \times \Sigma \land \delta(q_j, c) = q_i} (f(S(q_j, n)) \triangleleft c)]]

以上より,f(\Sigma^0) と,A\oplus\triangleleft のみを用いて, f再帰的に計算できることが分かりました.あとは,これを用いて f(\bigcup_{q \in F} S(q, l)) を計算すればよいです.

実装

trait Dfa {
  type Alphabet;
  type State;

  fn initial_state(&self) -> Self::State;
  fn next_state(&self, state: &Self::State, symbol: &Self::Alphabet) -> Self::State;
  fn is_accept_state(&self, state: &Self::State) -> bool;
}

fn automaton_dp<A, Sigma, Plus, Push, T>(
  dfa: A,
  alphabet: Sigma,
  len: usize,
  mut plus: Plus,
  mut push: Push,
  empty_value: T,
  initial_value: T,
) -> T
where
  A: Dfa,
  A::State: Eq + Hash,
  Sigma: Iterator<Item = A::Alphabet> + Clone,
  Plus: FnMut(&T, &T) -> T,
  Push: FnMut(&T, &A::Alphabet) -> T,
{
  let alphabet = alphabet.into_iter();

  let mut current = HashMap::<A::State, T>::with_capacity(1);
  let mut next = HashMap::<A::State, T>::new();

  current.insert(dfa.initial_state(), initial_value);

  for _ in 0..len {
    for (state, value) in current.drain() {
      for symbol in alphabet.clone() {
        let next_state = dfa.next_state(&state, &symbol);
        let value = push(&value, &symbol);

        if let Some(acc) = next.get_mut(&next_state) {
          *acc = plus(acc, &value);
          continue;
        }
        next.insert(next_state, value);
      }
    }

    mem::swap(&mut current, &mut next);
  }

  let mut acc = empty_value;

  for (state, value) in current {
    if dfa.is_accept_state(&state) {
      acc = plus(&acc, &value);
    }
  }

  acc
}

TODO: 説明

応用例

次の問題を解いてみます.

正の整数を (先頭に 0 をつけずに) 10 進法で書いて桁の数字を順番に見ていくと増加と減少を交互に繰り返しているとき,その数は「ジグザグ数」であると呼ぶことにしよう.たとえば,2947 は桁の数字が 2947 と,増加 → 減少 → 増加 の順になっているのでジグザグ数である.また,71946 は 減少 → 増加 → 減少 → 増加 の順なのでジグザグ数である.一方,123714467144288 はジグザグ数ではない.なお,1 桁の正の整数はジグザグ数であると考えることとする.

x 以上 y 以下の m の倍数のうち,ジグザグ数の総和を求めるプログラムを作成せよ.

  • 1 \le x \le y \le 10^{500}
  • 1 \le m \le 500

ジグザグ数 (Zig-Zag Numbers) 改題

10 進法表記したときに l 桁以下で表現できる正の整数は,leading zero を追加することでちょうど l 桁にすることができ,各桁を文字とみなすことで長さ l の文字列として見ることができます.以下では,l 以下で表現できるすべての正の整数について,そのようにして得られる文字列を考えるものとします.また,

  • 文字集合\Sigma = \{n \mid n \in \mathbb{N} \land 0 \le n \le 9\} とします.
  • y10 進法表記における桁数を l とします (l = \lceil \log_{10}(y + 1) \rceil).
  • z \in \mathbb{Z}_{\ge 0} の上から n 桁目 (最上位を 1 桁目とする) の数字を z[n] とします.

まず,x 以上 y 以下の m の倍数のうち,ジグザグ数のみを受理する DFA A を考えます.A は,次の三つの DFA の積4として表現できます.

  • x 以上 y 以下5の整数のみを受理する DFA
  • m の倍数のみを受理する DFA
  • ジグザグ数のみを受理する DFA

上から順に A_\alpha, A_\beta, A_\gamma とし,A_\chi について,状態集合を Q_\chi,遷移関数を \delta_\chi,初期状態を {q_\chi}_0,受理状態の集合を F_\chi とします.

A_\alpha は以下のように定義します.

  • Q_\alpha := \{\text{loose}, \text{exceeded}, \text{tightU}, \text{tightL}, \text{tightUL}\} \times \mathbb{N}
    • 最上位からある桁まで見たときに,
      • \text{loose}: x 以上 y 以下であることが確定している.
      • \text{exceeded}: x 未満,もしくは y を超えることが確定している.
      • \text{tightU}: 見ていない桁があるとき,x 以上は確定しているが,y 以下は未確定.
      • \text{tightL}: 見ていない桁があるとき,y 以下は確定しているが,x 以上は未確定.
      • \text{tightUL}: 見ていない桁があるとき,x 以上も y 以下も未確定.
    • \mathbb{N} は最上位から何桁まで見たか,を表します.
  • {q_\alpha}_0 := (\text{tightUL}, 0)
  • $\delta_\alpha((q, n), c) := \left( \begin{cases} d(q, n + 1, c) & (n \lt l) \\ \text{exceeded} & (n \ge l) \end{cases}, n + 1 \right)$
    • $d(\text{loose}, n, c) := \text{loose}$
    • $d(\text{exceeded}, n, c) := \text{exceeded}$
    • $d(\text{tightU}, n, c) := \begin{cases} \text{loose} & (c \lt y[n]) \\ \text{tightU} & (c = y[n]) \\ \text{exceeded} & (c \gt y[n]) \end{cases}$
    • $d(\text{tightL}, n, c) := \begin{cases} \text{loose} & (x[n] \lt c) \\ \text{tightL} & (x[n] = c) \\ \text{exceeded} & (x[n] \gt c) \end{cases}$
    • $d(\text{tightUL}, n, c) := \begin{cases} \text{loose} & (x[n] \lt c \lt y[n]) \\ \text{tightU} & (x[n] \lt c = y[n]) \\ \text{tightL} & (x[n] = c \lt y[n]) \\ \text{tightUL} & (x[n] = c = y[n]) \\ \text{exceeded} & (c \lt x[n] \lor y[n] \lt c) \\ \end{cases}$
  • F_\alpha := \{\text{tightU}, \text{tightL}, \text{tightUL}, \text{loose}\} \times \{l\}

A_\beta は以下のように定義します.

  • Q_\beta := \mathbb{Z} / m \mathbb{Z}
  • {q_\beta}_0 := 0
  • \delta_\beta(q, c) := (10q + c) \mod m
  • F_\beta := \{0\}

A_\gamma は以下のように定義します.

  • Q_\gamma := \{\text{empty}, \text{rejected}\} \cup (\{\text{single}, \text{increasing}, \text{decreasing}\} \times \Sigma)
    • 最上位からある桁まで見たときに,
      • \text{empty}: 一桁も見ていないか,見たすべての桁が 0
      • \text{rejected}: ジグザグ数ではないことが確定している.
      • \text{single}: 一桁しか見ていない.
      • \text{increasing}: 一つ上の桁は二つ上の桁より大きい.
      • \text{decreasing}: 一つ上の桁は二つ上の桁より小さい.
    • \Sigma は一つ上の桁を表します.
  • {q_\gamma}_0 := \text{empty}
  • $\delta_\gamma(\text{empty}, c) := \begin{cases} \text{empty} & (c = 0) \\ (\text{single}, c) & (c > 0) \end{cases}$
  • $\delta_\gamma(\text{rejected}, c) := \text{rejected}$
  • $\delta_\gamma((\text{single}, c_\text{prev}), c) := \begin{cases} (\text{increasing}, c) & (c_\text{prev} \lt c) \\ \text{rejected} & (c_\text{prev} = c) \\ (\text{decreasing}, c) & (c_\text{prev} \gt c) \end{cases}$
  • $\delta_\gamma((\text{increasing}, c_\text{prev}), c) := \begin{cases} (\text{decreasing}, c) & (c_\text{prev} \gt c) \\ \text{rejected} & (c_\text{prev} \le c) \end{cases}$
  • $\delta_\gamma((\text{decreasing}, c_\text{prev}), c) := \begin{cases} (\text{increasing}, c) & (c_\text{prev} \lt c) \\ \text{rejected} & (c_\text{prev} \ge c) \end{cases}$
  • F_\gamma := Q_\gamma \setminus \{\text{empty}, \text{rejected\}}

以上で A が定義できました.

次に, T, f, \oplus, \triangleleft を考えます.求めたいものは A が受理する正整数の集合 S \subset \mathbb{Z}_{\gt 0} の総和 \sum S であり,また \triangleleft の定義に \lvert S \rvert が必要であることから,

  • T := (\mathbb{N}, \mathbb{Z}_{\ge 0})
  • f(S) := (\lvert S \rvert, \sum S)
  • f(S_1) \oplus f(S_2) = (\lvert S_1 \rvert, \sum S_1) \oplus (\lvert S_2 \rvert, \sum S_2) := (|S_1| + |S_2|, \sum S_1 + \sum S_2)
  • f(S) \triangleleft c = (\lvert S \rvert, \sum S) \triangleleft c := (|S|, 10 \sum S + c \lvert S \rvert)
    • z \in \mathbb{Z}_{\ge 0} の末尾に桁 c \in \Sigma を追加する操作は,z \mapsto 10z + c という変換と等価であることより.

と定義できます.また,

  • f(\Sigma^0) = f(\{\epsilon\}) = (\lvert \{\epsilon\} \rvert, \sum \{\epsilon\}) = (1, 0)
  • f(\emptyset) = (\lvert \emptyset \rvert, \sum \emptyset) = (0, 0)

が従います.

TODO: 計算量の評価

参考

桁 DP

https://pekempey.hatenablog.com/entry/2018/09/01/203543pekempey.hatenablog.com

桁 DP のアイデアが簡潔にまとめられています.

オートマトン DP

https://twitter.com/noshi91/status/1096627726184665090

本記事でいう f\Sigma^* \rightarrow T写像として定義しています.こうすると,\oplus の結合性と可換性 ,さらに \triangleleft\oplus に対する分配則が明示的に要求されます (これらは本記事の定義では自動的に従います).


  1. 一般的な名称ではない.動的計画法 - yukicoder Wiki文字列マッチング状態 として言及あり.

  2. 遷移が定数時間の場合.

  3. A が受理する長さ l の文字列が存在しない場合に返却されるべき値.

  4. 与えられたすべての DFA が受理する文字列のみを受理する DFA のこと.状態集合はすべての DFA の状態集合の直積とし,それぞれの DFA を並列に実行すればよい.

  5. y 以下の答えと x 未満の答えの差から求めることもできるが,ここでは直接求める.

"遅延伝播" の一般化

よく混乱するので,自分用のメモとして分かりやすくまとめておく.

遅延伝播*1についての説明は省略.

要件

半群 $(S, \bullet)$,モノイド $(O, \circ, e)$ と,(外部) 二項演算 $\triangleleft : S \rightarrow O \rightarrow S$ について,

  • $\forall s \in S. \ s \triangleleft e = s$
  • $\forall s \in S. \ \forall p, q \in O. \ s \triangleleft (p \circ q) = (s \triangleleft p) \triangleleft q$
  • $\forall s, t \in S. \ \forall p \in O. \ (s \bullet t) \triangleleft p = (s \triangleleft p) \bullet (t \triangleleft p)$

を満足すればよい.

$S$ は (連続) 部分列の畳み込み, $O$ と $\triangleleft$ は部分列に対する一様な作用を表現する.

具体例

区間最小値 & 区間加算

  • $(S, \bullet) := (\mathbb{R}, \min)$
  • $(O, \circ, e) := (\mathbb{R}, +, 0)$
  • $\triangleleft := +$
type S = Double
type O = Double

opS :: S -> S -> S
opS = min

opO :: O -> O -> O
opO = (+)

act :: S -> O -> S
act = (+)

要件を確認する.

  • $(\mathbb{R}, \min)$ は半群の要件を満たす.
  • $(\mathbb{R}, +, 0)$ はモノイドの要件を満たす.
  • $\forall s \in \mathbb{R}. \ s + 0 = s$
  • $\forall s \in \mathbb{R}. \ \forall p, q \in \mathbb{R}. \ s + (p + q) = (s + p) + q$
  • $\forall s, t \in \mathbb{R}. \ \forall p \in \mathbb{R}. \ \min(s, t) + p = \min(s + p, t + p)$

区間和 & 区間加算

作用が分配的でないときは,区間の長さを持つ必要がある.

  • $S := \mathbb{R} \times \mathbb{N}$
  • $\forall (l, n), (r, m) \in S. \ (l, n) \bullet (r, m) := (l + r, n + m)$
  • $(O, \circ, e) := (\mathbb{R}, +, 0)$
  • $\forall (s, n) \in S. \ \forall p \in O. \ (s, n) \triangleleft p := (s + np, n)$
type S = (Double, Int)
type O = Double

opS :: S -> S -> S
(l, n) `opS` (r, m) = (l + r, n + m)

opO :: O -> O -> O
opO = (+)

act :: S -> O -> S
(s, n) `act` p = (s + fromIntegral n * p, n)

要件を確認する.

  • $(\mathbb{R} \times \mathbb{N}, \bullet)$ は半群の要件を満たす ($\because$ 半群 $(\mathbb{R}, +)$, $(\mathbb{N}, +)$ の直積).
  • $(\mathbb{R}, +, 0)$ はモノイドの要件を満たす.
  • $\forall (s, n) \in \mathbb{R} \times \mathbb{N}.$
    • $(s + n \times 0, n) = (s, n)$
  • $\forall (s, n) \in \mathbb{R} \times \mathbb{N}. \ \forall p, q \in \mathbb{R}.$
    • $(s + n(p + q), n) = ((s + np) + nq, n)$
  • $\forall (s, n), (t, m) \in \mathbb{R} \times \mathbb{N}. \ \forall p \in \mathbb{R}.$
    • $((s + t) + (n + m)p, n + m) = ((s + np) + (t + mp), n + m)$

区間和 & 区間代入

代入は右零半群で表現できる.これに単位元を添加しモノイドに拡張する.

  • $S := \mathbb{R} \times \mathbb{N}$
  • $\forall (l, n), (r, m) \in S. \ (l, n) \bullet (r, m) := (l + r, n + m)$
  • 適当な $e \notin \mathbb{R}$ を取って,
    • $O := \mathbb{R} \cup \{e\}$
    • $\forall l, r \in O. \ l \circ r := \begin{cases} l & (r = e) \\ r & (\text{otherwise}) \end{cases}$
  • $\forall (s, n) \in S. \ \forall p \in O.$
    • $(s, n) \triangleleft p := \begin{cases} (s, n) & (p = e) \\ (np, n) & (\text{otherwise}) \end{cases}$
type S = (Double, Int)
type O = Maybe Double

opS :: S -> S -> S
(l, n) `opS` (r, m) = (l + r, n + m)

opO :: O -> O -> O
l `opO` Nothing = l
_ `opO` r = r

act :: S -> O -> S
(s, n) `act` Nothing = (s, n)
(_, n) `act` (Just p) = (fromIntegral n * p, n)

これは要件を満たす.証明は省略.

参考

*1:遅延評価とも呼ばれる.遅延セグメント木などを参照のこと.

yukicoder - No.585 工夫のないパズル

https://yukicoder.me/problems/no/585

コンテスト中、A 問題を通した後ずっとこれを実装していて、結局間に合わず 1 完になった。でも ★4 AC は嬉しい。

概要

4 × 4 のスライドパズルを解く問題。いわゆる 15 パズル と似ているが、空きマスがない代わりに行か列を一つ選んでスライドすることができるというルール。右か下に任意マス分スライドするのを 1 回として、100 回以内の自由な操作で揃えればよい。

解説

おもむろに実験すると、最初の $3$ 行 (列でもいいけれど) は簡単にできそうということが分かる。後々の実装を楽にするために整理しておこう。

$i$ 行目 (0-indexed) までが揃っているとして ($0$ 行目は $-1$ 行目まで揃っていると考える)、次の $i + 1$ 行目を $i$ 行目までを崩さず揃えるには、基本的に下のようにすればよい。

今注目している移動させたい数字のマスの初期座標を $(sr, sc)$、移動先を $(tr, tc)$ とし (ただし、$(行, 列)$)、$round(i) = (i \% 4 + 4) \% 4$ とすると、

基本操作

  1. 列 $tc$ を $sr - tr$ 下へスライド
  2. 行 $sr$ を $round(tc - sc)$ 右へスライド
  3. 列 $tc$ を $4 - (sr - tr)$ 下へスライド

f:id:Kuretchi:20171028091512p:plain

ここでは、アルファベットの代わりに 0-15 の数字を使うことにする。今興味がない数字は省略。

ヤバそうなケースもしっかり考えておく。例えば、移動元と移動先が同じ行にある場合は、次のようにする。

移動元と移動先の行が同じ場合 ($sr = tr$)

  1. 列 $sc$ を $1$ 下へスライド
  2. 列 $tc$ を $1$ 下へスライド
  3. 行 $sr + 1 (= tr + 1)$ を $round(tc - sc)$ 右へスライド
  4. 列 $sc$ を $3$ 下へスライド
  5. 列 $tc$ を $3$ 下へスライド

f:id:Kuretchi:20171028091636p:plain

移動元と移動先が同じ列にある場合は、右へずらしてあげるとよい。

移動元と移動先の列が同じ場合 ($sc = tc$)

  1. 行 $sr$ を $1$ 右へスライド
  2. 基本操作 ($sc$ の値を更新しておくこと)

f:id:Kuretchi:20171028091700p:plain

以上の操作で、最初の $3$ 行を揃えることができる。

さて、最後の行を適当に入れ替えたい。簡単のために、隣り合うマスを交換する操作のみを考える。結論から言うと、次の操作で可能。

$r = sr (= tr)$、$c = round(sc + 1)$ とすると、

隣り合うマスの交換

  1. 列 $c$ を下へ $1$ スライド
  2. 行 $r$ を右へ $1$ スライド
  3. 列 $c$ を下へ $3$ スライド
  4. 行 $r$ を右へ $2$ スライド
  5. 列 $c$ を下へ $1$ スライド
  6. 行 $r$ を右へ $1$ スライド
  7. 列 $c$ を下へ $3$ スライド
  8. 行 $r$ を右へ $1$ スライド

f:id:Kuretchi:20171028132131p:plain

この操作によって、自明に列のマスを任意の順番に並べ替えることができるため、以上の考察ですべてのマスを揃えることができた。

ちなみに 適当にググって出てきたページ にも同じようなことが書いてある。

操作の回数については、以上の解法をそのまま実装すると少しギリギリだが、最適化の余地は十分にあるので、いい感じにえいすれば比較的余裕だと思われる。

実装例: C# / Haskell

ソートと要素のインデックス

ここらへんでハマってとてもつらかったので書いておきます。

ソート後のインデックスから、ソート前のインデックスを知りたい

f:id:Kuretchi:20170728115804p:plain:w600

方法1

インデックスとのペアのコレクションを作り、要素をキーとしてソートする。

char arr[5] = { 'D', 'A', 'C', 'E', 'B' };

pair<char, int> arridx[5];
for (int i = 0; i < 5; i++) arridx[i] = make_pair(arr[i], i);
// arridx => { (D, 0), (A, 1), (C, 2), (E, 3), (B, 4) }

sort(begin(arridx), end(arridx),
    [](pair<char, int>& a, pair<char, int>& b) {
        return a.first < b.first; });
// arridx => { (A, 1), (B, 4), (C, 2), (D, 0), (E, 3) }

方法2

インデックスだけのコレクションを作り、ソートしたいコレクションの対応する要素をキーとしてソートする。

char arr[5] = { 'D', 'A', 'C', 'E', 'B' };

int idx[5];
for (int i = 0; i < 5; i++) idx[i] = i;
// idx => { 0, 1, 2, 3, 4 }

sort(begin(idx), end(idx),
    [&arr](int& a, int& b) { return arr[a] < arr[b]; });
// idx => { 1, 4, 2, 0, 3 }

このソートされたインデックスを使って、ソートされた順番で要素にアクセスできる。

for (int i = 0; i < 5; i++) cout << arr[idx[i]] << " ";
// => "A B C D E "

ソート前のインデックスから、ソート後のインデックスを知りたい

f:id:Kuretchi:20170728115811p:plain:w600

コレクションが与えられた後、そのインデックスがクエリとして与えられるが、事前に元のコレクションをソートしておく必要がある場合など。上図では、例えば要素 D について、ソート前のインデックス 0 からソート後のインデックス 3 を得ることができる。

前述の、ソートされたインデックスのコレクションから生成する。

方法1

int after_idx[5];
for (int i = 0; i < 5; i++) after_idx[arridx[i].second] = i;
// after_idx => { 3, 0, 2, 4, 1 }

方法2

int after_idx[5];
for (int i = 0; i < 5; i++) after_idx[idx[i]] = i;
// after_idx => { 3, 0, 2, 4, 1 }