ひとりで勝手にはじめた蟻本読書会 動的計画法 01ナップサック問題 蟻本読書会の続きです。
Contents
最長共通部分列問題
ある列 Z が X と Y 両方の部分列であるとき、Z を X とY の共通部分列と言います。例えば、X = {a, b, c, b, d, a, b}, Y = {b, d, c, a, b, a} とすると、列 {b, c, a} は X と Y の共通部分列です。一方、列 {b, c, a} は X と Y の最長共通部分列ではありません。なぜなら、その長さは 3 であり、長さ 4 の共通部分列 {b, c, b, a} が存在するからです。長さが 5 以上の共通部分列が存在しないので、列 {b, c, b, a} は X と Y の最長共通部分列の１つです。
与えられた２つの文字列 X、Y に対して、最長共通部分列 Z の長さを出力するプログラムを作成してください。与えられる文字列は英文字のみで構成されています。
最長共通部分列問題とは、与えられた列の集合（しばしば、2つの列からなる集合）の最長共通部分列を見つけ出す問題です。部分列は部分文字列異なり元の列の連続した項である必要はありません。例えば、「ABCX」と「AYBZC」との最長共通部分列は「ABC」となります。この問題はファイル比較プログラムの基礎をなし、バイオインフォマティクスにも応用されているものです。
ではどのようにして解けばよいのでしょうか？
この問題は簡単な部分問題に分解することができ、これを繰り返すことで最後は自明な問題に帰着されます。上位の部分問題を解く際には、下位の部分問題の解を再利用することになります。ということは、この問題は動的計画法で解決できます。
X と Y の最長共通部分列問題を考える場合、最初に二つの列の最後の要素のみに限定して考えることにします。この場合、「X と Y の最後の要素は同じである」場合と「X と Y の最後の要素は異なる」場合に分けられます。
「X と Y の列の最後の要素は同じ」場合を先に考えます。この場合はそれぞれの要素から最後の要素を取り除いた列の最長共通部分列を見つけ、その最長共通部分列に最後の要素を追加すればよいことになります。
「X と Y の最後の要素は同じではない」場合の最長共通部分列は以下の長いほうです。
（X 全体）と（最後の要素を取り除いたY）の最長共通部分列
（X の最後の要素を取り除いた）と（Y 全体）の最長共通部分列
X の i 文字目を X[i]、Y の i 文字目を Y[i] とし、X の x 文字目と Y の y 文字目までの最長共通部分列を dp[x][y] とすると以下の式が成り立ちます。
X[x] == Y[y] のとき
→ dp[y][x] = dp[y – 1][x – 1] + 1
X[x] != Y[y] のとき
→ dp[y][x] = dp[y][x – 1], dp[y – 1][x] の大きい方
これだと添字が負数になってしまう場合があるので以下のように変更します。
dp[X.Length + 1, Y.Length + 1] を定義する
配列全体は 0 で初期化（自動的に 0 で初期化される）
X[x] == Y[y] なら a = 1, そうでないなら a = 0
dp[y + 1, x + 1] = （dp[y + 1, x], dp[y, x + 1], dp[y, x] + a の最大値）
すると以下のようになります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { string X = Console.ReadLine(); string Y = Console.ReadLine(); int[,] dp = new int[Y.Length + 1, X.Length + 1]; for (int y = 0; y < Y.Length; y++) { for (int x = 0; x < X.Length; x++) { int a = X[x] == Y[y] ? 1 : 0; int max = Math.Max(dp[y + 1, x], dp[y, x + 1]); max = Math.Max(max, dp[y, x] + a); dp[y + 1, x + 1] = max; } } Console.WriteLine(dp[Y.Length, X.Length]); } } |
編集距離（レーベンシュタイン距離）
長さが M の文字列 S と、長さが N の文字列 T が与えられます。
S に以下の 3 通りの操作を繰り返し施すことで、T に変換したいとします。そのような一連の操作のうち、操作回数の最小値を求めてください。なお。この最小値のことを文字列 S, T の編集距離と呼びます。
変更：文字列 S 中の文字を 1 つ選んで任意の文字に変更する
削除：文字列 S 中の文字を 1 つ選んで削除する
挿入：文字列 S の好きな箇所に好きな文字を 1 文字挿入する入力されるデータ
M N
S
T
M N は文字列の長さ 最大で1000。S と T は文字列。
この問題も動的計画法で解くことができます。計算量は O（NM）（N と M は文字列の長さ）です。
長さ 0 の文字列と長さ L の文字列の距離は L
X の x 文字目までの文字列と Y の y 文字目までの文字列の間の編集距離を d[y, x] とした場合、X[x] と [y] が同じであれば d[y, x] と d[y + 1, x + 1] は同じ値となる。異なるなら d[y, x] に 1 追加したものが d[y + 1, x + 1] となる。
また、X にのみ X[x] を追加した場合は d[y, x] から d[y, x + 1] へと遷移し、Y にのみ Y[y] を追加した場合は d[y, x] から d[y + 1, x] へと遷移する。
したがって d[y + 1, x + 1] は d[y, x + 1]、d[y + 1, 1]、d[y, x] + cost（ただし cost は X[x] == Y[y] なら 0、そうでないなら 1）の中の最小値である。
これらからふたつの文字列間の編集距離は以下のコードで求めることができます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { _ = Console.ReadLine(); string X = Console.ReadLine(); string Y = Console.ReadLine(); int[,] dp = new int[Y.Length + 1, X.Length + 1]; // 一方が空文字列なら、他方の長さが求める距離 for (int i = 0; i < X.Length + 1; i++) dp[0, i] = i; for (int i = 0; i < Y.Length + 1; i++) dp[i, 0] = i; for (int y = 0; y < Y.Length; y++) { for (int x = 0; x < X.Length; x++) { int cost = X[x] == Y[y] ? 0 : 1; int min = Math.Min(dp[y + 1, x] + 1, dp[y, x + 1] + 1); min = Math.Min(min, dp[y, x] + cost); dp[y + 1, x + 1] = min; } } Console.WriteLine(dp[Y.Length, X.Length]); } } |
求職者と求人会社のマッチングを手助けしている Indeed 社は、求職者に最適な求人を提示するサービスを開発することにした。
Indeed 社のデータベースには、独自テストで得られた、各求職者の技術力、語学力、コミュニケーション力が保存されている。またそのデータベースには、各求人会社が応募条件として要求した、それら 3 つの力の最低限必要な値とその会社の年収も保存されている。
データベースのデータがすべて与えられるので、各求職者ごとに、その人が応募可能な会社の中で一番高い年収を示しなさい。N M
a_1 b_1 c_1 w_1
a_2 b_2 c_2 w_2
…
a_N b_N c_N w_N
x_1 y_1 z_1
x_2 y_2 z_2
…
x_M y_M z_M（ただし 1 ≦ N（会社数）, M（求職者数） ≦ 50,000
0 ≦ a_i, b_i, c_i ≦ 100（各会社が求める技術力、語学力、コミュニケーション力）
0 ≦ x_i, y_i, z_i ≦ 100（各求職者の技術力、語学力、コミュニケーション力）
1 ≦ w_1 ≦ 100,000,000 ）（年収）
まず、これではダメ。年収で大きい順にソートして各求職者が各会社が求めるスキルに達しているもので最初にみつかったものの年収を取得しているのですが、N と M が最大 50,000 なので制限時間に間に合いません。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
using System; using System.Collections.Generic; using System.Linq; class Campany { public Campany(int a, int b, int c, int w) { A = a; B = b; C = c; W = w; } public int A { get; } public int B { get; } public int C { get; } public int W { get; } } class Program { static void Main() { int N, M; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; M = vs[1]; } List<Campany> campanies = new List<Campany>(); for (int i = 0; i < N; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); campanies.Add(new Campany(vs[0], vs[1], vs[2], vs[3])); } campanies = campanies.OrderByDescending(_ => _.W).ToList(); List<int> rets = new List<int>(); for (int i = 0; i < M; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); Campany campany = campanies.FirstOrDefault(_ => _.A <= vs[0] && _.B <= vs[1] && _.C <= vs[2]); if(campany != null) rets.Add(campany.W); else rets.Add(0); } foreach(int ret in rets) Console.WriteLine(ret); } } |
では、どうすればいいのか？
各求職者のスキルから最大年収を取得するテーブルを作る！ 3次元配列になりますが、int[,,] incomes = new int[101, 101, 101]; ならメモリー上に生成することができます。
incomes[a, b, c] をスキル a, b, c をもつ求職者の最大年収とします。会社が求めるスキルと年収でテーブルをつくればいいのですが、空白になった部分も埋めなければなりません。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
foreach (Campany campany in campanies) { int A = campany.A; int B = campany.B; int C = campany.C; int W = campany.W; // 会社が求めるスキルを上回っているならその会社の年収が得られる // 年収で降順ソートしているのですでに0以外の値が格納されているのであれば // その行のそれ以降の列にはなにもしない for (int a = A; a <= 100; a++) { for (int b = B; b <= 100; b++) { for (int c = C; c <= 100; c++) { if (incomes[a, b, c] == 0) incomes[a, b, c] = W; else break; } } } } |
問題は会社の数が 50,000 件あり、二重ループはそのまま回しているので制限時間内に間に合うのか心配になりますが、間に合います。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
using System; using System.Collections.Generic; using System.Linq; class Campany { public Campany(int a, int b, int c, int w) { A = a; B = b; C = c; W = w; } public int A { get; } public int B { get; } public int C { get; } public int W { get; } } class Program { static void Main() { int N, M; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; M = vs[1]; } List<Campany> campanies = new List<Campany>(); for (int i = 0; i < N; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); campanies.Add(new Campany(vs[0], vs[1], vs[2], vs[3])); } campanies = campanies.OrderByDescending(_ => _.W).ToList(); int[,,] incomes = new int[101, 101, 101]; foreach (Campany campany in campanies) { int A = campany.A; int B = campany.B; int C = campany.C; int W = campany.W; for (int a = A; a <= 100; a++) { for (int b = B; b <= 100; b++) { for (int c = C; c <= 100; c++) { if (incomes[a, b, c] == 0) incomes[a, b, c] = W; else break; } } } } List<int> rets = new List<int>(); for (int i = 0; i < M; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); rets.Add(incomes[vs[0], vs[1], vs[2]]); } foreach (int ret in rets) Console.WriteLine(ret); } } |
