kuretchi's blog

kuretchi's blog

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

"遅延伝播" の一般化

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

遅延伝播*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 }