差分

このページの2つのバージョン間の差分を表示します。

--- programming_algorithm:dynamic_programming:longest_common_subsequence [2019/01/09] – ikatakos
+++ programming_algorithm:dynamic_programming:longest_common_subsequence [2025/02/21] (現在) – [最長増加部分列の長さ] ikatakos
@@ 行 1: / 行 1: @@
 ======最長増加部分列・最長共通部分列======
-ある数列や文字列  $A=\{a_1,a_2,...,a_n\}$  がある時、部分列（Subsequence）とは、 $A$  からいくつかの要素を抽出した列。飛び飛びでもよいが、順番は元から変わってはいけない。
+競技プログラミングでは、「最長増加部分列（LIS）」や「最長共通部分列（LCS）」を求めるものが出題されることがある。\\
+これらは動的計画法により高速に求めることができる。
- $A$ の部分列 $B=\{a_i,a_j,...,a_k\} $、ただし$ 1 \le i \lt j \lt ... \lt k \le n$
+===== 用語の意味 ======
-|元の数列| $\{5,3,7,4,1,4,6\}$ |
+== 部分列 ==
-|部分列の例| $\{5,7,4\},\{1,6\}$ |
+ある数列や文字列  $A=(a_1,a_2,...,a_N)$  がある時、部分列（Subsequence）とは、 $A$  からいくつかの要素を抽出した列。\\
+飛び飛びでもよいが、順番は元から変わってはいけない。
-部分列にまつわる問題では、「最長増加部分列」や「最長共通部分列」を求める問題が出題される。これらは動的計画法により高速に求めることができる。また長さだけなら、なお高速に求める方法がある。
+  *  $A=(3,1,4,1,5)$  とすると、
+    *  $(3,1,1,5)$  や  $(1,)$  などが部分列
+    *  $(5,3)$  や  $(1,1,4)$  は、元と並びが変わっているため部分列ではない
+別の言い方をすると、以下の手順で構築できる列  $C$  が部分列である。
-=====最長増加部分列の長さ=====
+  *  $A$  の長さを  $N$  として、 $1 \le i_1 \lt i_2 \lt ... \lt i_k \le N$  を満たす添字列  $(i_1,...,i_k)$  を決める
+  * $C=(a_{i1},a_{i2},...,a_{ik})$ とする
-数列の部分列のうち、隣接する2要素を見ると常に右の方が大きいものを増加部分列という。同じ値を許すかは定義によるが、ここでは許さないとする。
+空の列  $()$  を部分列に含むかどうかは定義による。
-そのうち最長のものを最長増加部分列（Longest Increase Subsequence）という。
- $A$ の増加部分列 $B=\{a_i,a_j,...,a_k\} $、ただし$ 1 \le i \lt j \lt ... \lt k \le n $かつ$ a_i \lt a_j \lt ... \lt a_k$
+== 最長増加部分列 ==
-|元の数列|$\{5,3,7,4,1,4,6\}$|
+$A$ の部分列のうち単調増加なものを $A$ の「増加部分列」という。
-|増加部分列の例|$\{5,7\},\{3,6\}$|
-|最長増加部分列| $\{3,4,6\},\{1,4,6\}$ |
-この長さを求めましょう、という問題。（このアルゴリズムでは、最長増加部分列自体は求まらない）
+同じ値を許すかは定義によるが、ここでは許さない（狭義単調増加）とする。
-  * [[http://judge.u-aizu.ac.jp/onlinejudge/commentary.jsp?id=DPL_1_D|最長増加部分列 | 動的計画法 | Aizu Online Judge]]
+増加部分列のうち、長さが最も長いものを  $A$  の「最長増加部分列」（Longest Increase Subsequence, LIS）という。
-  -  $A$  の要素を1つずつ順番に処理する。現在処理中の要素を $a_j$ とする。
+LISの具体的な要素は複数通り考えられる場合もあるが、長さは  $A$  により一意に決まる。
-  - $L[i] $を、「$ a_1$～ $a_j$  の要素から長さが $i+1$ の増加部分列を作ったとき、末尾要素が取り得る最小値」とし、更新していく。
-  - 最後まで処理した後の  $L$  の値が埋まっている所の長さが、最長増加部分列長となる。
+|元の数列|$(5,3,7,4,1,4,6)$|
+|増加部分列の例| $(5,7),(3,6),(3,4,6)$ |
+|最長増加部分列の例| $(3,4,6),(1,4,6)$ |
+== 最長共通部分列 ==
+  * [[http://www.cs.t-kougei.ac.jp/SSys/LCS.htm|最長共通部分列 - 東京工芸大学]]
+  * [[wpjp>最長共通部分列問題]]
+つの列  $A$  と  $B$  に共通する部分列を、 $A$  と  $B$  の「共通部分列」という。
+そのうち長さが最長のものを「最長共通部分列」（Longest Common Subsequence, LCS）という。
+LCSの具体的な要素は複数通り考えられる場合もあるが、長さは一意に決まる。
+  * $A=(1,2,3,4,5,6,7,8,9)$
+  *  $B=(1,3,5,7,9,11,8,2,1)$
+  * 共通部分列の例
+    *  $(1,2)$
+    *  $(3,7,8)$
+  * 最長共通部分列の例
+    *  $(1,3,5,7,9)$
+===== 最長増加部分列 =====
+==== 最長増加部分列の長さ ====
+動的計画法で求める。このアルゴリズムでは、最長増加部分列の内容自体は求まらない。
+大きく分けて、二分探索を用いる方法と、セグメント木を用いる方法がある。前者の方が実装は楽。
+=== 二分探索を用いる方法 ===
+  * [[https://ei1333.github.io/library/dp/longest-increasing-subsequence.hpp.html|Longest Increasing Subsequence(最長増加部分列) | Luzhiled’s Library]]
+以下のDPをまず考える。
+  * $\mathrm{DP[i,j]}:=(a_1,...,a_i)$ から取れる長さ $j$ の増加部分列のうち、末尾要素が取り得る最小値
+ある増加部分列の末尾に新たな要素  $x$  を追加できるかどうかは、現在の末尾要素が  $x$  未満かどうかさえ分かれば判定できる。\\
+長さが同じなら末尾要素が小さい方が、追加できる  $x$  の範囲が広いので、長さ毎に末尾が最も小さいものだけ記録しておけば十分となる。
+以下の具体的なアルゴリズムでも示されるが、このDPは  $i-1$  と  $i$  では更新箇所が1箇所しかない。\\
+よって、DPを2次元配列で持つのではなく、 $i$  の次元は省略し、 $j$  を添字に持つ1次元配列を破壊的に更新していくことで、より高速に求められる。
+  -  $L=[-\infty]$  を用意する。
+  -  $i=1,2,...,N$  の順に以下を1つずつ処理する。現在処理中の要素を  $a_i$  とする。
+    -  $Lの末尾要素 \lt a_i$  の場合、 $L$  の末尾に  $a_i$  を追加する。
+    - それ以外の場合、 $L$  上で二分探索して  $a_i$  以上の値が初めて出てくるindex  $k$  を求め、 $L[k]←a_i$  で置き換える。
+  - 最後まで処理した後、 $L$  の最大のindexが、最長増加部分列の長さとなる。
+計算量  $O(N \log{N})$  で求めることができる。
+狭義単調増加の場合はbisect_left（ $a_i$  __以上__が初めて出てくるindex）だが、広義単調増加の場合はbisect_right（ $a_i$  __を超える__値が初めて出てくるindex）を用いる。
+  A = (3, 4, 8, 5, 1, 6, 2, 7)
+  i  Ai   L
+          [-∞]
+   3   [-∞, 3]
+   4   [-∞, 3, 4]
+   8   [-∞, 3, 4, 8]
+   5   [-∞, 3, 4, 5]
+   1   [-∞, 1, 4, 5]
+   6   [-∞, 1, 4, 5, 6]
+   2   [-∞, 1, 2, 5, 6]
+   2   [-∞, 1, 2, 5, 6, 7]    →  LIS長は 5
+Lを  $\infty$  で初期化した長さ  $N$  の配列として初期化する流儀もある。\\
+末尾に加えるか更新するかの場合分けが不要となりコードは短くなるが、代わりに毎回二分探索をおこなう必要がある。
+++++ Python実装例 |
 <sxh python>
 from bisect import bisect_left
-def lis(A: list):
+def longest_increasing_subsequence(A: list):
-    L = [A[0]]
+    L = [-1<<60]
-    for a in A[1:]:
+    for a in A:
         if a > L[-1]:
             # Lの末尾よりaが大きければ増加部分列を延長できる
             L.append(a)
         else:
-            # そうでなければ、「aより小さい最大要素の次」をaにする
+            # そうでなければ、「a以下の値が初めて出てくるindex」をaにする
-            # 該当位置は、二分探索で特定できる
             L[bisect_left(L, a)] = a
-    return len(L)
+    return len(L)-1
 # -----------------------------------------
@@ 行 52: / 行 125: @@
 </sxh>
-=====最長共通部分列の長さ=====
+++++
-  * [[http://www.cs.t-kougei.ac.jp/SSys/LCS.htm|最長共通部分列 - 東京工芸大学]]
+=== セグメント木（or BIT）を用いる方法 ===
-  * [[wpjp>最長共通部分列問題]]
-つの文字列A,Bがある時、「Aの部分列でもあり、Bの部分列でもある」文字列を共通文字列という。
+二分探索を用いる方法は、実装がシンプルではあるが、拡張性の面ではやや低い。\\
+最長増加部分列を求めるのにはセグメント木を使う方法もあり、そちらは多少、ひねったバリエーション問題にも対応できる。
+  * たとえば少し改変すると、最長増加部分列の個数を数え上げたりできる
+    * [[https://qiita.com/Euglenese/items/3411953cc7cf5707e32d|yukicoder No.992 最長増加部分列の数え上げ #競技プログラミング - Qiita]]
+以下のDPを定義する。
+  *  $DP[i]=a_i$  を末尾に必ず使用するような増加部分列の中で、最長のものの長さ
+ $DP[i]=0$ （ $i=1,...,N$ ）で初期化した上で、このDP配列をセグメント木に載せる。
+ $i$  ではなく、 $a_i$  が小さい順に処理する。同率の場合は、indexが後の方から処理する。\\
+（※広義単調増加の場合は、前の方から処理する）
+ $a_i$  について処理する際、 $DP$  配列の「 $[1,i)$  の区間における最大値 + 1」が、 $DP[i]$  となる。\\
+区間最大値はセグメント木やBITで取得できるので、これで  $DP[i]$  を計算し、更新する。
+最終的に、 $DP$  全体の中での最大値が答えとなる。
+こちらも計算量のオーダーは  $O(N \log{N})$  となる。\\
+二分探索と比べて定数倍や必要なメモリは重くなるが、一般的な競技プログラミングの制約の前ではまぁ、だいたい気にしなくていい。
+  i    1  2  3  4  5  6  7  8
+  A = (3, 4, 7, 5, 1, 5, 7, 3)
+  i  Ai   DP
+          [0, 0, 0, 0, 0, 0, 0, 0]
+   1   [0, 0, 0, 0, 1, 0, 0, 0]  [1, i)の最大値（波線区間） + 1 で、DP[i] を更新
+           ~~~~~~~~~~
+   3   [0, 0, 0, 0, 1, 0, 0, 2]
+   3   [1, 0, 0, 0, 1, 0, 0, 2]
+   4   [1, 2, 0, 0, 1, 0, 0, 2]
+   5   [1, 2, 0, 0, 1, 3, 0, 2]
+   5   [1, 2, 0, 3, 1, 3, 0, 2]
+   7   [1, 2, 0, 3, 1, 3, 4, 2]
+   7   [1, 2, 3, 3, 1, 3, 4, 2]    → LIS長は4
+==== 最長増加部分列の復元 ====
+具体的な最長増加部分列の1つを求める場合。
+二分探索を用いる方法で、 $L$  の他に、以下の情報も持ってDPする。
+  *  $prev[i]$ :  $a_i$  を更新したとき、 $L[k]$  に格納したとして、その時点の  $L[k-1]$  の値（先頭の場合は  $-\infty$ ）
+最後までDPしたら、復元する。
+  *  $x=L[末尾]$  で初期化する。また、LIS復元用の配列  $S$  を空で初期化する。
+  *  $A$  を逆順に走査する。 $a_i=x$  となる  $i$  が見つかったら、 $S.append(x)$ 、 $x ← prev[i]$  とする
+  *  $x=-\infty$  になったら終了。 $S$  を反転したものがLISとなる。
+prevの記録・LISの復元は  $O(N)$  でできるので、計算量は変わらず  $O(N \log{N})$  となる。
+==== バリエーション ====
+=== 最長増加部分列の個数 ===
+条件として、「部分列として同じであっても取り出した位置が異なる場合は別カウント」とする。
+セグメント木を使う方法を拡張する。
+  *  $DP[i]=a_i$  を末尾に必ず使用するような増加部分列の中で、(最長のものの長さ, その個数)
+セグメント木なら、これは適切にマージできる。（長さが同じなら個数を合算し、どちらかが大きいならそちらを継承する）
+ $a_i$  について処理する際、 $[0,i)$  の区間を求め、(最長の長さ+1, 個数) が  $DP[i]$  となる。
+計算量のオーダーは  $O(N \log{N})$  となる。
+===== 最長共通部分列 =====
+つの文字列 $S,T$ がある時、「 $S$  の部分列でもあり、 $T$  の部分列でもある」文字列を共通文字列という。
 そのうち最長のものを最長共通部分列（Longest Common Subsequence）という。
-|A|abcbdabc|
+|S|abcbdabc|
-|B|bdcaba|
+|T|bdcaba|
 |LCS|bcba,bdabなど|
-この長さを求めましょう、という問題。（このアルゴリズムでは、最長共通部分列自体は求まらない）
+==== 最長共通部分列の長さ ====
+文字列  $S,T$  が与えられたとき、2つの最長共通部分列の長さを求めましょう、という問題。
+以下のDPを考える。
+  *  $\mathrm{DP}[i,j]:=S[:i]$  と  $T[:j]$  の最長共通部分列の長さ
+    * ただし  $S[:i]$  は  $S$  の先頭  $i$  文字を指す
+ $\mathrm{DP}[i,j]$  を求めるには、
+  *  $S_i=T_j$  の時
+    *  $\mathrm{DP}[i-1,j-1]$  で作られる共通部分列の末尾に1文字追加できる。 $\mathrm{DP}[i-1,j-1]+1$
+  *  $S_i \neq T_j$  の時
+    * どちらかを1文字削ったものと同じとなる。\max(\mathrm{DP}[i-1,j],\mathrm{DP}[i,j-1])$
+ $\mathrm{DP}[i,j]$  を埋めるには、 $\mathrm{DP}[i-1,j-1],\mathrm{DP}[i-1,j],\mathrm{DP}[i,j-1]$  が埋まっている必要がある。\\
+ $\mathrm{DP}[0,*]$  と  $\mathrm{DP}[*,0]$  は  $0$  確定なので埋めておき、
+あとは '''for i in (1,...,|S|)  for j in (1,...,|T|)''' の2重ループで処理すればよい。
+ $\mathrm{DP}[|S|,|T|]$  が最長共通部分列の長さとなる。\\
+計算量は  $O(|S||T|)$ 。
+  S = XMJYAUZ
+  T = MZJAWXU
+1 2 3 4 5 6 7
+          M Z J A W X U
+   | 0 0 0 0 0 0 0 0
+X | 0 0 0 0 0 0 1 1
+M | 0 1 1 1 1 1 1 1
+J | 0 1 1 2 2 2 2 2
+Y | 0 1 1 2 2 2 2 2
+A | 0 1 1 2 3 3 3 3
+U | 0 1 1 2 3 3 3 4
+Z | 0 1 2 2 3 3 3 4
+++++ DPの持たせ方を変えた別解法 |
+前述のDPよりわかりにくいし、（おそらく）解ける問題の範囲が広がったりはしないので、スルーしていい。
   - Bの要素を1つずつ順番に処理する。現在処理中の要素を $b_k$ とする。
@@ 行 118: / 行 302: @@
     * 延長できる場合、 $L$  に追加する
-=====具体的な最長共通部分列=====
+++++
+==== 最長共通部分列の復元 ====
   * [[wp>Longest_common_subsequence_problem]]
- $(|S|+1) \times (|T|+1)$  の配列上でDPを行い、途中の計算結果を保存しておくことで、最長共通部分列と共に、その具体例を構築することが出来る。
+長さを求める際のDPの結果から、具体的な最長共通部分列の1例を復元できる。
-===DPテーブルの構築===
+DPテーブルから逆向きに復元する。$(i,j)=(|S|,|T|)$ で初期化する。\\
+また、復元結果を記録する配列  $U$  を空で初期化する。
-$S_{1 ... i} $と$ T_{1 ... j}$ のLCSの長さを $L_{i,j}$ とする。
+== $\mathrm{DP}[i,j]=\mathrm{DP}[i,j-1]$ または $\mathrm{DP}[i,j]=\mathrm{DP}[i-1,j]$ の時 ==
-$L_{0,j}=0,L_{i,0}=0$ とする。
+同じである数字の方に $(i,j)$ を移動する。両方同じ場合は適当に1つ選んで移動する。
-== $S_{i+1}=T_{j+1}$  の時==
+== それ以外の時 ==
-LCS長は1文字拡張できる。$L_{i+1,j+1}=L_{i,j}+1$
+ $S_i=T_j$  となっている。$U $にその文字を加え、$ (i-1,j-1)$ に移動する。
-==それ以外の時==
+$\mathrm{DP}[i,j]=0$ になったら終了。\\
+$U$ をひっくり返すと、最長共通部分列となる。
-LCS長は、片方の末尾を1文字削った2通りの長い方となる。 $L_{i+1,j+1}=max(L_{i+1,j},L_{i,j+1})$
-これで、$i=1 .. |S|$、 $j=1 .. |T|$  の2重ループでDPテーブルを小さい方から埋めていくことで、 $L_{|S|,|T|}$  が最終的なLCS長となる。
-===具体例の構築===
-具体的な文字列は、DPテーブルから逆向きに復元する。 $(i,j)=(|S|,|T|)$  とする。
-== $L_{i,j}=L_{i,j-1}$  または  $L_{i,j}=L_{i-1,j}$  の時==
-同じである数字の方に $(i,j)$ を移動する。両方同じ場合は、具体例が1つ構築できればいい場合は適当に1つ選んで移動する。
-==それ以外の時==
- $S_i=T_j$  であるはずなので、それをLCSに加え、 $(i-1,j-1)$  に移動する。
 <code>
@@ 行 164: / 行 336: @@
 Z | 0 1 2 2 3 3 3④  黒丸の数字を拾っていくと、LCS（の1つ）は MJAU と復元できる
 </code>
+==== バリエーション ====
+=== 一方に出てくる文字に重複がない場合 ===
+ $S,T$  いずれか一方に出てくる文字が全て異なることが分かっていれば、より少ない計算量で求められる。\\
+ここでは  $S$  の文字が全て異なるとする。
+ $S$  に出てくる順に、文字を数値に置き換える。 $T$  もその置換に従って置き換える。 $S$  に出てこない文字は取り除く。
+  S =  B R O W N C A T
+        ↓
+  S'=  1 2 3 4 5 6 7 8
+  T =  W H I T E C O W
+        ↓
+  T'=  4 x x 8 x 6 3 4    Sに出てこない文字（x）は、取り除く
+最長共通部分列の長さは、 $T'$  の最長増加部分列の長さとなり、 $O(|S|+|T| \log{|T|})$  で求められる。
+=== 最長共通部分列の個数 ===
+== 取り出し位置の個数 ==
+「共通部分列として同じであっても、 $S,T$  から取り出した位置が異なる場合は別カウント」の場合の個数を数える。
+  * [[https://drken1215.hatenablog.com/entry/2019/06/21/230200|AtCoder ABC 130 E - Common Subsequence (青色, 500 点) - けんちょんの競プロ精進記録]]
+    * ※上記記事は、最長とは限らない「共通部分列」の数え上げだが、参考として。
+長さを求めるものとは別に、個数を数えるDP配列を用意する。
+  *  $\mathrm{DP}_l[i,j]:=S[:i]$  と  $T[:j]$  から作られる最長共通部分列の長さ
+  *  $\mathrm{DP}_c[i,j]:=S[:i]$  と  $T[:j]$  から作られる最長共通部分列の個数
+ $\mathrm{DP}_c[0,*]=\mathrm{DP}_c[*,0]=1$ 、他は  $0$  で初期化する。
+遷移では、以下のようにすればよい。 $\mathrm{DP}_c[i,j]$  を求める。 $(1 \le i \le |S|,1 \le j \le |T|)$
+  * まずは  $DP_l[i,j]$  を通常の手順で更新する。
+  * 次の各条件を調べ、 $DP_c[i,j]$  を更新する。
+    *  $S_i=T_j$  なら、 $\mathrm{DP}_c[i,j]+=\mathrm{DP}_c[i-1,j-1]$
+    *  $\mathrm{DP}_l[i,j]=\mathrm{DP}_l[i,j-1]$  なら、 $\mathrm{DP}_c[i,j]+=\mathrm{DP}_c[i,j-1]$
+    *  $\mathrm{DP}_l[i,j]=\mathrm{DP}_l[i-1,j]$  なら、 $\mathrm{DP}_c[i,j]+=\mathrm{DP}_c[i-1,j]$
+    *  $\mathrm{DP}_l[i,j]=\mathrm{DP}_l[i-1,j-1]$  なら、 $\mathrm{DP}_c[i,j]-=\mathrm{DP}_c[i-1,j-1]$
+つめの更新で減算しているのは、 $\mathrm{DP}_c[i-1,j-1]$  で数えられている最長共通部分列が
+「→↓」と「↓→」の2通りの経路で重複して  $\mathrm{DP}_c[i,j]$  に足し込まれるのを防ぐためである。
+== 文字列としての個数 ==
+「 $S,T$  から取り出した位置が異なっても、文字列として同じ場合は1カウント」の場合の個数を数える。
+上記の4種類のDP遷移のうち、下3つを、 $S_i=T_j$  である場合は行わないようにすればよい。つまり、
+  *  $S_i=T_j$  なら、 $\mathrm{DP}_c[i,j]+=\mathrm{DP}_c[i-1,j-1]$
+  *  $S_i \neq T_j$  かつ、
+    *  $\mathrm{DP}_l[i,j]=\mathrm{DP}_l[i,j-1]$  なら、 $\mathrm{DP}_c[i,j]+=\mathrm{DP}_c[i,j-1]$
+    *  $\mathrm{DP}_l[i,j]=\mathrm{DP}_l[i-1,j]$  なら、 $\mathrm{DP}_c[i,j]+=\mathrm{DP}_c[i-1,j]$
+    *  $\mathrm{DP}_l[i,j]=\mathrm{DP}_l[i-1,j-1]$  なら、 $\mathrm{DP}_c[i,j]-=\mathrm{DP}_c[i-1,j-1]$
+でよい（未検証）
+++++ お気持ち |
+一応、 $|S|=|T|=20$  程度のランダムテストで愚直解と一致することは確認しているが、
+この遷移で上手くいく適当な証明が思いつかないので、イメージだけ。\\
+基本的に、部分列の数え上げで重複を除く場合は
+「同じ部分列となる場合は取り出し位置の辞書順が最小（または最大）となるものだけを数える」
+のように遷移ルールを考えると上手くいくことが多い。\\
+今回の場合も、イメージとしては辞書順最大のもののみを数えている（のだが、
+「 $S,T$  の2種類の取り出し位置がある中での『辞書順』って何だ？」あたりが上手く整理できない）
+図で表すと、以下のようになる。
+  DP_lの結果に対し、同じ文字が交差する箇所に [ ] を付けたもの
+        a   c   b   a   b   c   a
+  0   0   0   0   0   0   0
+  a  0 [1]  1   1  [1]  1   1  [1]
+  b  0  1   1  [2]  2  [2]  2   2
+  c  0  1  [2]  2   2   2  [3]  3
+  a  0 [1]  2   2  [3]  3   3  [4]
+  c  0  1  [2]  2   3   3  [4]  4
+  b  0  1   2  [3]  3  [4]  4   4
+  a  0 [1]  2   3  [4]  4   4  [5]
+  a  0 [1]  2   3  [4]  4   4  [5]
+上のようなフィールドがあったとして、「取り出し位置の数え上げ」は以下に言い換えられる。
+  * 左上からスタート、右下がゴール。
+  * 以下の移動しかできない。
+    * 今いるところと同じ数字の、右のマスに移動する
+    * 今いるところと同じ数字の、下のマスに移動する
+    * 今いるところより1大きい、斜め右下の [ ] のマスに移動する
+  * 左上から右下まで移動したとき、斜め右下への移動はちょうど5回（フィールド右下の数字）だけ行われる。
+  * 問題: 斜め右下移動が発生したマスの組としてあり得るものの個数を求めよ。
+「文字列としての数え上げ」の遷移は、斜め右下移動をする際、
+「最も遅くその行、列にたどり着いた経路」のみ残すというルールとすることに相当する。
+「同じ列・行で先に右下に移動した経路からは遷移しない」ことで、重複を除いている。
+        a   c   b   a   b   c   a
+→0→ 0→ 0→ 0→ 0→ 0→ 0
+     v↘         ↘          ↘
+  a  0 [1]→1→ 1✖[1]→1→ 1✖[1]    ✖: 遷移しないことで重複を防いでいる箇所
+     v  v    ↘       ↘
+  b  0  1→ 1  [2]→2✖[2]→2→ 2
+     v  v↘     v         ↘
+  c  0  1  [2]→2→ 2→ 2  [3]→3
+     v↘✖  v    ↘           ↘
+  a  0 [1]  2→ 2  [3]→3→ 3  [4]
+  :
+++++