問題と解法の前に私がわからなかったいくつかの定義について解説します。
部分列とは
数列A{5,1,3,2,4}があるとすると、部分列は
{5,3,2},{1,2,4}などが相当します。
つまり、数列の先頭から部分的に数列を取り出したものになります。
なので、{1,3,5}など途中から前の数字を取り出した数列は部分列に相当しません記号的に定義すると
数列A=a0,a1,…,an−1とすると、
0 ≤ i0 < i1 < … < ik < n かつ ai0 < ai1 < … < aik
となります。
最長増加部分列とは
先ほどのように数列Aから切り出した部分列において、数が増加し続けているものの最大のものをいいます。
数列Aを例にとると
{1,3,2}は1と3が増加しているのみなので、長さは1
{1,2,4}は1,2,4と増加しているので、長さは3となり。
{1,2,4}が最長増加部分列となります。
これらを踏まえてAIZU ONLINE JUDGEの例題を解いてみます。
最長増加部分列の例題
数列 A = {a0, a1, … , an−1} の最長増加部分列 (LIS: Longest Increasing Subsequence) の長さを求めてください。 数列 A の増加部分列は 0 ≤ i0 < i1 < … < ik < n かつ ai0 < ai1 < … < aik を満たす部分列 {ai0, ai1, … , aik} です。最長増加部分列はその中で最も k が大きいものです。
入力
１行目に数列 A の長さを示す整数 n が与えられます。続く n 行で数列の各要素 ai が与えられます。
出力
最長増加部分列の長さを１行に出力してください。
動的計画法と2分探索を用いた解法
最長増加部分列問題は、動的計画法と2分探索を用いることで、効率的に求めることができます。
以下の2つの変数を定義します。
| 変数名例 | 役割 |
| L[n] | L[i]を長さがi + 1であるような増加部分列の最後の要素の最小値とする配列 |
| length | i番目の要素までを使った最長増加部分列の長さを表す整数 |
処理の図解
入力をA = {4,1,6,2,8,5,6,3}に対するLの値の変化を見ていきます。
最初の施行
初めは、比較することもないので、Aの最初の入力値である4をL代入します。
A:4 L:4, , , , , , ,
2度目の施行
Aから1を選択します。
Lは増加部分列の最後の要素の最小値とする配列なので、
4と1を入れ替えます。
AをLに代入する際にAの値でLに対し2分探索を使うことで、Lの条件を満たすことができます。
A:1 L:1, , , , , , ,
3度目の施行
Aは6になります。
6は現在のLISの最後の要素よりも大きいので、
LISの最後の要素[1]に6を代入し、Lengthが1増加します。
A:6 L:1,6, , , , , ,
4度目の施行
Aは2になります。
2度目の施行と同様に2よりも大きいLの要素6と2を入れ替えます。
この時、長さは変わりません。
A:2 L:1,2, , , , , ,
最後まで施行する
以下同様の処理を繰り返します。
処理の途中結果のみ図示します。
A:8 L:1,2,8, , , , ,
A:5 L:1,2,5, , , , ,
A:7 L:1,2,5,7, , , ,
A:3 L:1,2,3,7, , , ,
最終的な、Lengthの値が最長増加部分列の長さということになります。
この動的計画法と2分探索方を用いた計算量は$O(nlog_{n})$になります。
c++での解法
最後にAIZU ONLINE JUDGEの問題を例に解法例を載せます。
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 100000
int n,A[MAX + 1],L[MAX];
/**
最長増加部分列の長さを返す
*/
int lis(){
// 0には初期値を
L[0] = A[0];
int length = 1;
// 1から詮索する
for(int i = 1;i < n;++i){
// LISの最後の要素に追加
if(L[length - 1] < A[i]){
L[length++] = A[i];
}else{
// 2分探索を使い、選択した値をLが昇順になるように代入する
*lower_bound(L,L + length,A[i]) = A[i];
}
}
return length;
}
int main(){
cin >> n;
for(int i = 0;i < n;++i){
cin >> A[i];
}
cout << lis() << endl;
return 0;
}
0 件のコメント:
コメントを投稿