LoginSignup
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@yumura_s

JavaScriptで動的計画法を宣言的に書く実験（失敗）

Posted at

「動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集」の記事を読んでいて、「半環上の計算が多いなぁ」とか、「DPは有向非閉路グラフ（DAG）を考えるといいのかぁ」とか思っていて。

つまるところ、(半環, DAG)の組みが書ければ、配るDPは実行できるんじゃないかと思って、実装してみました。

例えば、「Educational DP Contest / DP まとめコンテスト」のA - Frog 1であれば、次のように書けます。なお、pushDP、MinPlusSemiring、genIndices、newIndexが今回実装したもので、それ以外は素のJavaScriptです。

frog1.js
const frog1 = (n, hs) => pushDP({
  /* 半環 */
  semiring: MinPlusSemiring,

  /* DAGの頂点 */
  indices: genIndices(n),
  initializer: i => i === 0 ? MinPlusSemiring.one : MinPlusSemiring.zero,

  /* DAGの辺 */
  children: i => [newIndex(i + 1), newIndex(i + 2)],
  weight: i => j => j < n ? Math.abs(hs[i] - hs[j]) : MinPlusSemiring.zero
});

下記を実行すると30が返ってきます。

.js
frog1(4, [10, 30, 40, 20]); // 30

ちなみに、このDPは比較的キレイに書けるんですが、キレイに書けないDPの方が多かったので実験としては失敗でした。
成功したい人は「Dynamorphism 〜 Haskellでも動的計画法がしたい！ 〜」の記事を読みましょう。

DPテーブルの添字を作る関数

実装したpushDP、MinPlusSemiring、genIndices、newIndexのうち、添字に関するgenIndices、newIndexの実装が簡単なので先に説明しておきます。

newIndex

今回肝となるpushDPではDPテーブルの添字をDAGの頂点とみなしています。たとえば、DPテーブルが2次元配列であれば[2,3]などが頂点になります。

下記のとおり、newIndexはArray.ofの別名に過ぎません。これは、ただ[2,3]と書いても添え字を書いてる感が出ないので、newIndex(2,3)と書けるようにしたかったためです。可読性以外に意味はありません。

.js
const newIndex = Array.of;

genIndices

DAGを扱っているとトポロジカルソートされた頂点の列が稀によく必要になります。

pushDPはDPテーブルの添字を頂点とみなしますが、辞書式順序がそのままトポロジカルオーダーになっていることが多いので、次のような挙動をする関数genIndicesが欲しくなります。

.js
[...genIndices(2)] // [[0],[1]]
[...genIndices(2, 3)] // [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2]]
[...genIndices(2, 2, 2)] // [[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]

DPテーブルの次元数はたかが知れているので、下記のとおり再帰関数としてサクッと実装しました。なお、ジェネレータ関数にしてあるのは、１つずつ添え字を取り出す状況の方が、添え字の列全体を扱う状況よりも多いためです。

.js
const genIndices = function* (...counts) {
  if (counts.length === 0) {
    yield [];
    return;
  }

  const count = counts.pop();
  for (let index of genIndices(...counts)) {
    for (let i = 0; i < count; i++) {
      yield index.concat(i);
    }
  }
};

半環

一応、定義を載せておきます。

$R$を集合とする。２つの元$\bar{0}, \bar{1} \in R$と、２つの二項演算$\oplus, \otimes : R \times R \to R$が下記の条件を満たすとき、$(R, \bar{0}, \oplus, \bar{1}, \otimes)$の組みを半環と呼ぶ。

  • $(R, \bar{0}, \oplus)$が可換モノイド。任意の元$a, b, c \in R$について下記が成り立つ。
    • $(a \oplus b) \oplus c = a \oplus (b \oplus c)$
    • $\bar{0} \oplus a = a \oplus \bar{0} = a$
    • $a \oplus b = b \oplus a$
  • $(R, \bar{1}, \otimes)$がモノイド。任意の元$a, b, c \in R$について下記が成り立つ。
    • $(a \otimes b) \otimes c = a \otimes (b \otimes c)$
    • $1 \otimes a = a \otimes 1 = a$
  • $\otimes$は$\oplus$に対して分配的。任意の元$a, b, c \in R$について下記が成り立つ。
    • $a \otimes (b \oplus c) = (a \otimes b) \oplus (a \otimes c)$
    • $(a \oplus b) \otimes c = (a \otimes c) \oplus (b \otimes c)$
  • $\bar{0}$は$\otimes$の吸収元。任意の元$a \in R$について下記が成り立つ。
    • $\bar{0} \otimes a = a \otimes \bar{0} = \bar{0}$

なお、1-添加すれば、半群からモノイドを容易に作れるので、プログラミングに応用する場合は$\oplus$の結合律、可換律、$\otimes$の結合律、$\otimes$、$\oplus$の分配律だけ気にしておけばわりと何とかなるんじゃないでしょうか。

MinPlusSemiring

トロピカル半環 $(\mathbb{R} \cup \{ \infty \}, \infty, \min, 0, +)$とか呼ばれてるやつです。

.js
const MinPlusSemiring = {
  zero:  Infinity,
  plus:  Math.min,
  one:   0,
  times: (x, y) => x + y
};

なお、$(\mathbb{R} \cup \{ -\infty \}, -\infty, \max, 0, +)$も半環です。

.js
const MaxPlusSemiring = {
  zero:  -Infinity,
  plus:  Math.max,
  one:   0,
  times: (x, y) => x + y
};

まあ、一番馴染み深いのは普通の和と積ですよね～。

.js
const PlusTimesSemiring = {
  zero:  0,
  plus:  (x, y) => x + y,
  one:   1,
  times: (x, y) => x * y
};

pushDP

というわけで本命のpushDPの実装を示したいのですが、説明のためにA - Frog 1を解くコードを再掲します。

frog1.js
const frog1 = (n, hs) => pushDP({
  /* 半環 */
  semiring: MinPlusSemiring,

  /* DAGの頂点 */
  indices: genIndices(n),
  initializer: i => i === 0 ? MinPlusSemiring.one : MinPlusSemiring.zero,

  /* DAGの辺 */
  children: i => [newIndex(i + 1), newIndex(i + 2)],
  weight: i => j => j < n ? Math.abs(hs[i] - hs[j]) : MinPlusSemiring.one
});

上記のとおり、pushDPはsemiring, indices, initializer, children, weightを引数に取ります。それぞれの引数は下記のような値を設定します。

  • 半環
    • semiringには半環を設定します。頂点と辺の値を使ってどう計算するかを表します。
  • 頂点関連
    • indicesにはトポロジカルソートされた頂点（添字）の列を設定します。
    • initializerには各頂点の初期値を返す関数を設定します。設定される関数は、頂点（添字）を引数に取り、初期値を返します。なお、入次数が0でない頂点の初期値は半環の零元$\bar{0}$で初期化するのがマナーです。
  • 辺関連
    • childrenには隣接リストの代わりとなる関数を設定します。設定される関数は、頂点（添字）を引数に取り、その頂点に隣接する頂点の列を返します。
    • weightには辺の重みを返す関数を設定します。設定される関数は、有向辺の始点と終点を引数に取り、その重みを返します。

という前提をおいた上で、pushDPの実装は次のとおりになります。

.js
const pushDP = ({semiring, indices, initializer, children, weight} ={}) => {
  const dp = new DPTable(semiring, initializer, weight);

  let index = null;
  for (index of indices) {
    dp.done(index);
    for(let child of children(...index)) {
      dp.update(index, child);
    }
  }
  if (index !== null) {
    return dp.get(index);
  }
};

DPTableが何なのかという疑問はいったん横に置いておくと、pushDP自体がやってることはごく単純です。
引数のindicesに従って各頂点（添字index）に、計算済みのマークを付け（dp.done）、隣接する各頂点（children）について、更新をかけ（dp.update）、最後に処理した添字に対応する値(dp.get(index))を返却して終了します。
本来、計算済みのマーク付けは不要ですが、assertion的なノリで入れてあります。
配るDPの処理の流れを大雑把に書いたものだと思えば、あまり違和感はないんじゃないでしょうか。

DPTable

pushDPの内部で呼び出していた、DPTableですが、ExTableクラスのサブクラスです。

ExTableクラスのインスタンスは_extendメソッドによってサイズが拡張される配列_tableをプロパティにもちます。getとsetで当該の添字の値にアクセスできます。拡張時にテーブルの要素はinitializerを使って添字ごとに初期化されます。

DPTableクラスのインスタンスはdone、get、set、updateの４つのメソッドを持ったオブジェクトです。

done、getは見たままのメソッドです。doneは引数の添字に対応する要素が計算済みであるとマークするメソッドで、getは引数の添字に対応する要素の値を返却します。

setとupdateはニコイチです。イメージとしてはupdateの引数に辺$(i, j)$が設定された場合、次の更新を実施します。$dp$がDPテーブルで、$w$が辺の重みのイメージです。

$$dp_j \gets dp_j \oplus (dp_i \otimes w_{i, j})$$

.js
class ExTable {
  constructor(initializer = () => null) {
    this._table = [];
    this._initializer = initializer;
  }
  
  get(index) {
    const [arr, i] = this._extend(index);
    return arr[i];
  }
  
  set(index, value) {
    const [arr, i] = this._extend(index);
    arr[i] = value;
  }

  _extend(index) {
    const head = index.slice(0, index.length - 1);
    const i = index[index.length - 1];

    let arr = this._table;

    for(let j of head) {
      while(arr.length <= j) {
        arr.push([]);
      }
      arr = arr[j];
    }

    while (arr.length <= i) {
      arr.push(this._initializer(...head, arr.length));
    }

    return [arr, i];
  }
}

class DPTable extends ExTable {
  constructor(semiring, initializer, weight) {
    super((...index) => {return {
      value: initializer(...index),
      done: false
    };});

    this._semiring = semiring;
    this._weight = weight;
  }
  
  done(index) {
    const obj = super.get(index);
    if (obj.done) {
      throw new Error(`Cannot done: dp[${index.join()}]`);
    }
    obj.done = true;
  }

  get(index) {
    const {value, done} = super.get(index);
    if (! done) {
      throw new Error(`Cannot get: dp[${index.join()}]`);
    }
    return value;
  }

  set(index, value) {
    const obj = super.get(index);
    if (obj.done) {
      throw new Error(`Cannot set: dp[${index.join()}]`);
    }
    obj.value = this._semiring.plus(obj.value, value);
  }

  update(from, to) {
    const v = this.get(from);
    const w = this._weight(...from)(...to);
    this.set(to, this._semiring.times(v, w));
  }
}

コード全量

以上でコードの全量が揃ったので改めてまとめたものを掲載します。

pushDP.js
const newIndex = Array.of;

const genIndices = function* (...counts) {
  if (counts.length === 0) {
    yield [];
    return;
  }

  const count = counts.pop();
  for (let index of genIndices(...counts)) {
    for (let i = 0; i < count; i++) {
      yield index.concat(i);
    }
  }
};


const MinPlusSemiring = {
  zero:  Infinity,
  plus:  Math.min,
  one:   0,
  times: (x, y) => x + y
};

const MaxPlusSemiring = {
  zero:  -Infinity,
  plus:  Math.max,
  one:   0,
  times: (x, y) => x + y
};

const PlusTimesSemiring = {
  zero:  0,
  plus:  (x, y) => x + y,
  one:   1,
  times: (x, y) => x * y
};


const pushDP = ({semiring, indices, initializer, children, weight} ={}) => {
  const dp = new DPTable(semiring, initializer, weight);

  let index = null;
  for (index of indices) {
    dp.done(index);
    for(let child of children(...index)) {
      dp.update(index, child);
    }
  }
  if (index !== null) {
    return dp.get(index);
  }
};


class ExTable {
  constructor(initializer = () => null) {
    this._table = [];
    this._initializer = initializer;
  }
  
  get(index) {
    const [arr, i] = this._extend(index);
    return arr[i];
  }
  
  set(index, value) {
    const [arr, i] = this._extend(index);
    arr[i] = value;
  }

  _extend(index) {
    const head = index.slice(0, index.length - 1);
    const i = index[index.length - 1];

    let arr = this._table;

    for(let j of head) {
      while(arr.length <= j) {
        arr.push([]);
      }
      arr = arr[j];
    }

    while (arr.length <= i) {
      arr.push(this._initializer(...head, arr.length));
    }

    return [arr, i];
  }
}

class DPTable extends ExTable {
  constructor(semiring, initializer, weight) {
    super((...index) => {return {
      value: initializer(...index),
      done: false
    };});

    this._semiring = semiring;
    this._weight = weight;
  }
  
  done(index) {
    const obj = super.get(index);
    if (obj.done) {
      throw new Error(`Cannot done: dp[${index.join()}]`);
    }
    obj.done = true;
  }

  get(index) {
    const {value, done} = super.get(index);
    if (! done) {
      throw new Error(`Cannot get: dp[${index.join()}]`);
    }
    return value;
  }

  set(index, value) {
    const obj = super.get(index);
    if (obj.done) {
      throw new Error(`Cannot set: dp[${index.join()}]`);
    }
    obj.value = this._semiring.plus(obj.value, value);
  }

  update(from, to) {
    const v = this.get(from);
    const w = this._weight(...from)(...to);
    this.set(to, this._semiring.times(v, w));
  }
}

使ってみる

pushDPを実際に使ってみました。

キレイに書けないのが多いので実験としては失敗ですね。
これでキレイに書けるんだったら、とっくに誰かやってるはずなんで当たり前といえば当たり前ですが。

フィボナッチ数

こうやって書くとパス総数を求めてる感がありますね～。
あと、children、weightの形から行列積でやれよ感が出てます。

.js
const fib = n => n === 0 ? 0 : pushDP({
  semiring: PlusTimesSemiring,

  indices: genIndices(n),
  initializer: i => i === 0 ? PlusTimesSemiring.one : PlusTimesSemiring.zero,
  
  children: i => [newIndex(i + 1), newIndex(i + 2)],
  weight: i => j => PlusTimesSemiring.one
});

fib(0); // 0
fib(10); // 55
fib(50); // 12586269025

DP まとめコンテスト A - Frog 1

動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集を参考に実装。こうして見るとフィボナッチ数列とだいたい同じ形になっています。

.js
const frog1 = (n, hs) => pushDP({
  semiring: MinPlusSemiring,

  indices: genIndices(n),
  initializer: i => i === 0 ? MinPlusSemiring.one : MinPlusSemiring.zero,
  
  children: i => [newIndex(i + 1), newIndex(i + 2)],
  weight: i => j => j < n ? Math.abs(hs[i] - hs[j]) : MinPlusSemiring.one
});

frog1(4, [10, 30, 40, 20]); // 30
frog1(2, [10, 10]); // 0
frog1(6, [30, 10, 60, 10, 60, 50]); // 40

DP まとめコンテスト B - Frog 2

「A - Frog 1」のchildrenが動的になっただけです。

.js
const frog2 = (n, k, hs) => pushDP({
  semiring: MinPlusSemiring,

  indices: genIndices(n),
  initializer: i => i === 0 ? MinPlusSemiring.one : MinPlusSemiring.zero,

  children: i => [...Array(k).keys()].map(j => newIndex(i + j + 1)),
  weight: i => j => j < n ? Math.abs(hs[i] - hs[j]) : MinPlusSemiring.one
});

frog2(5, 3, [10, 30, 40, 50, 20]); // 30
frog2(3, 1, [10, 20, 10]); // 20
frog2(2, 100, [10, 10]); // 0
frog2(10, 4, [40, 10, 20, 70, 80, 10, 20, 70, 80, 60]); // 40

DP まとめコンテスト C - Vacation

pushDPは宣言的に書けるようにした関係で、DPテーブルを外部から参照できません。「C - Vacation」の問題は、DPテーブルの最終行（最終日）のmaxを取る必要があるので、DPテーブルが参照できないと本来は困ります。

次の実装では、幸福度0で2日分余計に回すことでお茶を濁しています。

.js
const vacation = (n, abc) => pushDP({
  semiring: MaxPlusSemiring,

  indices: genIndices(n + 2, 3),
  initializer: (i, j) => i === 0 ? abc[i][j] : MaxPlusSemiring.zero,
  
  children: (i, j) => [newIndex(i + 1, (j + 1) % 3), newIndex(i + 1, (j + 2) % 3)],
  weight: () => (i, j) => i < n ? abc[i][j] : MaxPlusSemiring.one
});

vacation(3, [[10, 40, 70], [20, 50, 80], [30, 60, 90]]); // 210
vacation(1, [[100, 10, 1]]); // 100
vacation(7, [[6, 7, 8], [8, 8, 3], [2, 5, 2], [7, 8, 6], [4, 6, 8], [2, 3, 4], [7, 5, 1]]); // 46

DP まとめコンテスト D - Knapsack 1

ナップサック問題。競プロやってる人には慣れたものかもしれないですが、私はいまいち理解しきれていません。

.js
const knapsack1 = (n, w, wvs) => pushDP({
  semiring: MaxPlusSemiring,

  indices: genIndices(n + 1, w + 1),
  initializer: (i, u) => i === 0 ? MaxPlusSemiring.one : MaxPlusSemiring.zero,

  children: (i, u) => [u, i < n ? u + wvs[i][0] : Infinity].filter(u => u <= w).map(u => newIndex(i + 1, u)),
  weight: (i, u_i) => (j, u_j) => u_i === u_j ? MaxPlusSemiring.one : wvs[i][1]
});

knapsack1(3, 8, [[3, 30], [4, 50], [5, 60]]); // 90
knapsack1(5, 5, [[1, 1000000000], [1, 1000000000], [1, 1000000000], [1, 1000000000], [1, 1000000000]]); // 5000000000
knapsack1(6, 15, [[6, 5], [5, 6], [6, 4], [6, 6], [3, 5], [7, 2]]); // 17

DP まとめコンテスト E - Knapsack 2

添字を入れ替えたナップサックの実装は、DPテーブルの最終行を最後に処理する必要があります。先に述べたとおりpushDPで実装するとDPテーブルを外部から参照できませんので、工夫というか、無理をする必要があります。

具体的には次のような実装になります。

.js
const knapsack2 = (n, w, wvs) => {
  const maxV = wvs.map(([_, v]) => v).reduce((acc, v) => acc + v, 0);

  const semiring = {
    zero:  [Infinity, 0],
    plus:  (x, y) => [Math.min(x[0], y[0]), Math.max(x[1], y[1])],
    one:   [0, 0],
    times: (x, y) => [x[0] + y[0], x[0] + y[0] <= w ? x[1] + y[1] : 0]
  };
  
  return pushDP({
    semiring: semiring,

    indices: genIndices(n + 1, maxV + 1),
    initializer: (i, v) => v === 0 ? semiring.one : semiring.zero,

    children: (i, v) => i < n ? [v, v + wvs[i][1]].filter(v => v <= maxV).map(v => newIndex(i + 1, v)) : [newIndex(i, v + 1)],
    weight: (i, v_i) => (j, v_j) => (i === n || v_i === v_j) ? semiring.one : wvs[i]
  })[1];
};


knapsack2(3, 8, [[3, 30], [4, 50], [5, 60]]); // 90
knapsack2(1, 1000000000, [[1000000000, 10]]); // 10
knapsack2(6, 15, [[6, 5], [5, 6], [6, 4], [6, 6], [3, 5], [7, 2]]); // 17

上記のコードでは要件にあう半環を無理やり作り出して対応しています。すなわち、0を含む自然数で添字付けられた集合族$(R_w)_{w \in \mathbb{N}}$ を次のとおり定義します。

$$R_w = \{ (n, m) |
n, m \in \mathbb{N}, n \leq w \} \cup \{(n, 0) | n \in \mathbb{N}, n > w \} \cup \{ (\infty, 0)\}$$

ここで、二項演算$\oplus_w, \otimes_w : R_w \times R_w \to R_w$を次のとおり定義します。

$$(x_0, x_1) \oplus_w (y_0, y_1) = (\min(x_0, y_0), \max(x_1, y_1))$$

.math
(x_0, x_1) \otimes_w (y_0, y_1) = \begin{cases}
(x_0 + y_0, x_1 + y_1) ~~\text{if}~~ x_0 + y_0 \leq w \\
(x_0 + y_0, 0) ~~~~~~~~~~~~ \text{otherwise}
\end{cases}

さて、このとき$(R_w, (\infty, 0), \oplus_w, (0, 0), \otimes_w)$は半環になり、この半環を使うと添字を入れ替えたナップサックが実装できます。

DP まとめコンテスト F - LCS

復元DP（意外と解説がない！動的計画法で得た最適解を「復元」する一般的な方法）。

「復元DPはimmutableな片方向連結リストとお友達」という考えで下記の通り実装していますが、無理のし過ぎで何が何だかわかりません（RestoreSemiringとIndexListSemiringは後述します）。

.js
const lcs = (s, t) => {
  semiring = new RestoreSemiring(MaxPlusSemiring);
  
  const [_, list] = pushDP({
    semiring: semiring,
  
    indices: genIndices(s.length + 1, t.length + 1),
    initializer: (i, j) => (i === 0 && j === 0) ? semiring.one : semiring.zero,
  
    children: (i, j) => [newIndex(i + 1, j), newIndex(i, j + 1)].concat((i < s.length && j < t.length && s[i] === t[j]) ? [newIndex(i + 1, j + 1)] : []),
    weight: (i1, j1) => (i2, j2) => (i1 === i2 || j1 === j2) ? semiring.one : [1, IndexListSemiring.newIndex(i1, j1)]
  });
  
  return semiring.restore(list).map(([i, j] = []) => s[i]).join("");
};

lcs("axyb", "abyxb"); // "axb"
lcs("aa", "xayaz"); // "aa"
lcs("a", "z"); // ""
lcs("abracadabra", "avadakedavra") // "aaadara"

復元できるということは、複数ある入辺のうち一つを選ぶということなので、任意の元$x, y \in R$に対して$x \oplus y = x$、または$x \oplus y = y$が成り立つような選択的な（全順序のminimumかmaximumを和とする）半環上のDPになるはずです。

そのような選択的な性質を満たす２つの半環

.math
(A, 0_A, \oplus_A, 1_A , \otimes_A); ~~ \forall x, y \in A [x \oplus_A y = x \lor x \oplus_A y = y] \\
(B, 0_B, \oplus_B, 1_B , \otimes_B); ~~ \forall x, y \in B [x \oplus_B y = x \lor x \oplus_B y = y]

があるとき、$(A \times B, (0_A, 0_B), \oplus_{A \times B}, (1_A, 1_B) \otimes_{A \times B})$も半環になり、やはり選択的な性質を持ちます。ここで、拡張された二項演算は下記の通り定義されます。

.math
(x_A, x_B) \oplus_{A \times B} (y_A, x_B) = \begin{cases}
(x_A, x_B \oplus_B y_B) ~~\text{if}~~ x_A = y_A \\
(x_A, x_B) ~~~~~~~~~~~~~~\text{if}~~ x_A \oplus_A y_A = x_A \\
(y_A, y_B) ~~~~~~~~~~~~~~~\text{otherwise}
\end{cases}

$$(x_A, x_B) \otimes_{A \times B} (y_A, x_B) = (x_A \otimes_A y_A, x_B \otimes_B y_B)$$

IndexListSemiringは添字のリストの集合の辞書順のminimumを和、リストの左右を入れ替えた結合を積とした選択的な半環です。RestoreSemiringは選択的な半環をコンストラクタの引数に取り、IndexListSemiringをくっつけた新たな選択的な半環を作り出します。添字のリストの集合に記録しておきたい添字を積み上げることで、復元を実現しています。

う～ん。複雑。

.js
const IndexListSemiring = {
  zero: new Proxy([new Proxy([], {get: () => Infinity}), null], {get: (zero, n) => n === "1" ? IndexListSemiring.zero : zero[n]}),
  plus: (xss, yss) => {
    let x, y;
    let [xs, ys] = [xss, yss];

    while(xs.length > 0 && ys.length > 0) {
      [x, xs] = [xs[0], xs[1]];
      [y, ys] = [ys[0], ys[1]];
      const len = Math.min(x.length, y.length);
      
      for (let i = 0; i < len; i++) {
        if (x[i] !== y[i]) {
          return x[i] < y[i] ? xss : yss;
        }
      }
      
      if (x.length !== y.length) {
        return x.length < y.length ? xss : yss;
      }
    }
    
    return xs.length <= ys.length ? xss : yss;
  },

  one: [],
  times: (xs, ys) => {
    if (xs === IndexListSemiring.zero || ys === IndexListSemiring.zero) {
      return IndexListSemiring.zero;
    }
    
    return IndexListSemiring._times(IndexListSemiring.toArray(ys), xs);
  },

  _times: (arr, list) => {
    for (let i = arr.length - 1; i >= 0; i--) {
      list = [arr[i], list];
    }
    return list;
  },
  
  newIndex: (...index) => [index, []],

  toArray: list => {
    const arr = [];
    let v;
    while (list.length > 0) {
      [v, list] = [list[0], list[1]];
      arr.push(v);
    }
    return arr;
  }
};

class RestoreSemiring {
  constructor(semiring) {
    /* semiring.plus(x, y) === x or semiring.plus(x, y) === y */
    this._semiring = semiring;
    this.zero = [semiring.zero, IndexListSemiring.zero];
    this.one  = [semiring.one,  IndexListSemiring.one];
  }
  
  plus([x, xs] = [], [y, ys] = []) {
    if (x === y) {
      return [x, IndexListSemiring.plus(xs, ys)]
    }
    
    const z = this._semiring.plus(x, y);
    return [z, x === z ? xs : ys];
  }
  
  times([x, xs] = [], [y, ys] = []) {
    return [this._semiring.times(x, y), IndexListSemiring.times(xs, ys)];
  }
  
  restore(xs) {
    const arr = IndexListSemiring.toArray(xs);
    arr.reverse();
    return arr;
  }
};

DP まとめコンテスト G - Longest Path

とりあえずトポロジカルソートで対応します。

.js
const longestPath = (n, m, es) => {
  const parent   = Array(n).fill(0).map(_ => []);
  const children = Array(n).fill(0).map(_ => []);
  for (let [from, to] of es) {
    parent[to - 1].push(newIndex(from - 1));
    children[from - 1].push(newIndex(to - 1));
  }
  
  return pushDP({
    semiring: MaxPlusSemiring,

    indices: genTSortIndices(genIndices(n), i => parent[i]),
    initializer: i => parent[i].length === 0 ? 0 : MaxPlusSemiring.zero,

    children: i => children[i],
    weight: i => j => 1
  });
};

longestPath(4, 5, [[1, 2], [1, 3], [3, 2], [2, 4], [3, 4]]); // 3
longestPath(6, 3, [[2, 3], [4, 5], [5, 6]]); // 2
longestPath(5, 8,[[5, 3], [2, 3], [2, 4], [5, 2], [5, 1], [1, 4], [4, 3], [1, 3]]); // 3

トポロジカルソートを実行するgenTSortIndices は、次のとおり実装してあります。
「頂点集合（実際には出次数0の頂点のみあれば良い）」と「転置グラフの隣接リスト」を引数に取っています。

.js
const genTSortIndices = function* (indices, parent) {
  const table = new ExTable((...index) => {
    const p = parent(...index);

    return {
      parent: Array.isArray(p) ? p.values() : p,
      visited: false
    };
  });

  for (let index of indices) {
    if (table.get(index).visited) {
      continue;
    }
    table.get(index).visited = true;
    const stack = [index];

    while (stack.length > 0) {
      const p = table.get(stack[stack.length - 1]).parent.next()

      if (p.done) {
        yield stack.pop();
      } else if(! table.get(p.value).visited) {
        table.get(p.value).visited = true;
        stack.push(p.value);
      }
    }
  }
};

DP まとめコンテスト H - Grid 1

剰余類環上のパスの数え上げ。

.js
const grid1 = (h, w, grid) => {
  const semiring = new PlusTimesSemiringModulo(1000000007);
  
  return pushDP({
    semiring: semiring,

    indices: genIndices(h, w),
    initializer: (i, j) => (i === 0 && j === 0) ? semiring.one : semiring.zero,

    children: (i, j) => [newIndex(i + 1, j), newIndex(i, j + 1)].filter(([i, j] = []) => i < h && j < w && grid[i][j] !== "#"),
    weight: (i1, j1) => (i1, j1) => semiring.one
  });
}

grid1(3, 4, ["...#", ".#..", "...."]); // 3
grid1(5, 2, ["..", "#.", "..", ".#", ".."]); // 0
grid1(20, 20,[
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
  "....................",
  "...................."
]); // 345263555

PlusTimesSemiringModuloは剰余類環の半環の部分を次のとおり実装してあります。

.js
class PlusTimesSemiringModulo {
  constructor(n) {
    this._n = n;
    
    this.zero = 0;
    this.one = 1;
  }
  
  plus(x, y) {
    const z = x + y;
    return z < this._n ? z : z - this._n;
  }
  
  times(x, y) {
    return (x * y) % this._n;
  }
  
  from(x) {
    const y = x % this._n;
    return y < 0 ? y + this._n : y;
  }
}

DP まとめコンテスト I - Coins

諦めました（笑）

.js
const coins = (n, ps) => pushDP({
  semiring: PlusTimesSemiring,

  initializer: (i, j) => (i === 0 && j === 0) ? PlusTimesSemiring.one: PlusTimesSemiring.zero,
  indices: (function* () {
    for (let i = 0; i < n; i ++) {
      for (let j = 0; j <= i; j++) {
        yield newIndex(i, j);
      }
    }

    for (let j = Math.ceil(n / 2); j <= n; j++) {
      yield newIndex(n, j);
    }
  })(),

  children: (i, j) => i === n ? [newIndex(i, j + 1)] : [newIndex(i + 1, j), newIndex(i + 1, j + 1)],
  weight: (i1, j1) => (i2, j2) => i1 === n ?  PlusTimesSemiring.one : j1 !== j2 ? ps[i1] : (1.0 - ps[i1])
});

coins(3, [0.30, 0.60, 0.80]); // 0.612
coins(1, [0.50]); // 0.5
coins(5, [0.42, 0.01, 0.42, 0.99, 0.42]); // 0.3821815872

DP まとめコンテスト J - Shusi

遷移がややこしいですね。トポロジカルソートで無理やり実行しているので更にややこしいという。

.js
const sushi = (n, sara) => {
  const goal = Array(3).fill(0);
  for (let i of sara) {
    goal[i - 1]++;
  }
  
  const nonNeg = (...arr) => arr.filter(index => index.every(x => x >= 0));

  return pushDP({
    semiring: PlusTimesSemiring,

    initializer: (n1, n2, n3) => (n1 === 0 && n2 === 0 && n3 === 0) ? 0 : n / (n1 + n2 + n3),

    indices: genTSortIndices([goal], (n1, n2, n3) => nonNeg(
      newIndex(n1 - 1, n2,     n3),
      newIndex(n1 + 1, n2 - 1, n3),
      newIndex(n1,     n2 + 1, n3 - 1)
    )),
    
    children: (n1, n2, n3) => nonNeg(
      newIndex(n1 + 1, n2,     n3),
      newIndex(n1 - 1, n2 + 1, n3),
      newIndex(n1,     n2 - 1, n3 + 1)
    ),
    
    weight: (m1, m2, m3) => (n1, n2, n3) =>
      m1 + 1 === n1 ? n1 / (n1 + n2 + n3) :
      m2 + 1 === n2 ? n2 / (n1 + n2 + n3) :
    /*m3 + 1 === n3*/ n3 / (n1 + n2 + n3) 
  });
};

sushi(3, [1, 1, 1]); // 5.5
sushi(1, [3]); // 3
sushi(2, [1, 2]); // 4.5
sushi(10, [1, 3, 2, 3, 3, 2, 3, 2, 1, 3]); // 54.480644574882206

ABC 099 C - Strange Bank

貰う DP と配る DP、メモ化再帰、個数制限なしナップサック問題のやつ。これも辺がややこしいです。

.js
const strangeBank = n => pushDP({
  semiring: MinPlusSemiring,

  indices: genIndices(n + 1),
  initializer: i => i === 0 ? 0 : MinPlusSemiring.zero,

  weight: i => j => 1,
  children: function* (i) {
    yield newIndex(i + 1);
    
    for (let j = 6; i + j <= n; j *= 6) {
      yield newIndex(i + j);
    }
    
    for (let j = 9; i + j <= n; j *= 9) {
      yield newIndex(i + j);
    }
  }
});

strangeBank(127); // 4
strangeBank(3); // 3
strangeBank(44852); // 16

おわりに

身も蓋もないことを言ってしまえば、そもそもメモ化再帰の時点で宣言的なんですよね。

1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?