アルゴリズムと計算量の問題

難易度 1教科書の例題レベル大学数学アルゴリズムと計算量

文字列 $Z$ から $0$ 個以上の文字を取り除き、残った文字を元の順に並べて得られる文字列を $Z$ の部分列という（取り除く文字は連続していなくてよい）。 $2$ つの文字列の両方の部分列であるものを共通部分列といい、共通部分列のうち長さが最大のものを最長共通部分列という。

$2$ つの DNA 塩基配列を表す文字列
$X = GATCA, Y = TACGA$
の最長共通部分列の長さを求めよ。

この問題で使うもの

最長共通部分列（説明と入口の問題）

この問題を解けるようになるまで（2 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

最長共通部分列の表 $L [i] [j]$ （ $X$ の先頭 $i$ 文字と $Y$ の先頭 $j$ 文字の最長共通部分列の長さ）を動的計画法で埋める技能を使う。

ヒント 2

$x_{i} = y_{j}$ なら $L [i] [j] = L [i - 1] [j - 1] + 1$ 、そうでなければ $L [i] [j] = max (L [i - 1] [j], L [i] [j - 1])$ 。 $L [i] [0] = L [0] [j] = 0$ から始める。

ヒント 3

$1$ 行目（G）は $0, 0, 0, 1, 1$ 、 $2$ 行目（A）は $0, 1, 1, 1, 2$ 、 $3$ 行目（T）は $1, 1, 1, 1, 2$ になる。残りの $2$ 行を同じように埋め、右下の値を読む。

答えと解説

答えを見る

3

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

$X = x_{1} x_{2} \dots x_{5} = GATCA$ 、 $Y = y_{1} y_{2} \dots y_{5} = TACGA$ とし、 $L [i] [j]$ を「 $X$ の先頭 $i$ 文字と $Y$ の先頭 $j$ 文字の最長共通部分列の長さ」とする。

初期値: 一方が空文字列なら共通部分列は空文字列だけなので、 $L [i] [0] = L [0] [j] = 0$ 。

漸化式: $i, j \geq 1$ のとき
$L [i] [j] = {L [i - 1] [j - 1] + 1 max (L [i - 1] [j], L [i] [j - 1]) (x_{i} = y_{j}) (x_{i} \neq = y_{j})$

これを $i = 1$ の行から順に、各行は左から右へ埋める（上・左・左上の値がすでに求まっているので計算できる）。

$i = 1$ （ $x_{1} = G$ ）: $y_{4} = G$ で一致して $L [1] [4] = L [0] [3] + 1 = 1$ 。それより左は $0$ 、右は $max$ で $1$ 。行は $0, 0, 0, 1, 1$ 。
$i = 2$ （ $x_{2} = A$ ）: $j = 1$ は $max (0, 0) = 0$ 。 $j = 2$ （A）一致で $L [1] [1] + 1 = 1$ 。 $j = 3, 4$ は $max$ で $1, 1$ 。 $j = 5$ （A）一致で $L [1] [4] + 1 = 2$ 。行は $0, 1, 1, 1, 2$ 。
$i = 3$ （ $x_{3} = T$ ）: $j = 1$ （T）一致で $L [2] [0] + 1 = 1$ 。 $j = 2, 3, 4$ は $max$ で $1, 1, 1$ 。 $j = 5$ は $max (L [2] [5], L [3] [4]) = max (2, 1) = 2$ 。行は $1, 1, 1, 1, 2$ 。
$i = 4$ （ $x_{4} = C$ ）: $j = 1, 2$ は $max$ で $1, 1$ 。 $j = 3$ （C）一致で $L [3] [2] + 1 = 2$ 。 $j = 4, 5$ は $max$ で $2, 2$ 。行は $1, 1, 2, 2, 2$ 。
$i = 5$ （ $x_{5} = A$ ）: $j = 1$ は $1$ 。 $j = 2$ （A）一致で $L [4] [1] + 1 = 2$ 。 $j = 3, 4$ は $max$ で $2, 2$ 。 $j = 5$ （A）一致で $L [4] [4] + 1 = 3$ 。行は $1, 2, 2, 2, 3$ 。

表にまとめると（行が $i$ 、列が $j$ ）
$G A T C A T 00111 A 01112 C 01122 G 11122 A 12223$

右下の値 $L [5] [5] = 3$ が答えである。実際、 $TCA$ （あるいは $ACA$ ）は $X, Y$ の両方の部分列になっている。

答え: $3$

別解

長さ 3 の共通部分列として TCA がある。X = GATCA では 3, 4, 5 文字目、Y = TACGA では 1, 3, 5 文字目として取り出せる。

長さ 4 の共通部分列がないことを確かめる。X の長さ 4 の部分列は、1 文字を取り除いた次の 5 通りしかない。
- ATCA（G を除く）
- GTCA（2 文字目の A を除く）
- GACA（T を除く）
- GATA（C を除く）
- GATC（最後の A を除く）

Y = TACGA について、それぞれ部分列かどうかを調べる。
- ATCA: A(2 文字目) の後に T がないので、部分列でない。
- GTCA: G(4 文字目) の後に T がないので、部分列でない。
- GACA: G(4 文字目)、A(5 文字目) の後に C がないので、部分列でない。
- GATA: G、A の後に T がないので、部分列でない。
- GATC: A の後に T がないので、部分列でない。

どれも Y の部分列でないので、長さ 4 以上の共通部分列は存在しない。したがって最長共通部分列の長さは 3 である。

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が答えを見ずに 3 回解き、3 回とも同じ答えになりました
プログラムで答えを計算し直し、一致を確認しました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる