動的計画法を用いた最長増加部分列（LIS）のアルゴリズムとその応用について解説します。最長増加部分列は、与えられた数列の中から単調に増加する部分列の中で最も長いものを求める問題です。このモデルは、様々な最適化問題に応用可能です。
最長増加部分列の基本概念
最長増加部分列問題は、与えられた数列において、各要素が前の要素よりも大きくなるように選んだ部分列のうち、最も長いものの長さを求める問題です。
例えば、数列 [3, 1, 4, 2, 5, 3] の場合、最長増加部分列は [1, 2, 3] または [1, 4, 5] のように長さ3となります。
基本的なLISアルゴリズム
最も基本的なLISの解法は動的計画法を用います。以下にC++での実装例を示します：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int longestIncreasingSubsequence(const vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
vector<int> dp(n, 1);
int max_length = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
max_length = max(max_length, dp[i]);
}
return max_length;
}
int main() {
vector<int> sequence = {3, 10, 2, 1, 20};
cout << "最長増加部分列の長さ: " << longestIncreasingSubsequence(sequence) << endl;
return 0;
}
計算量の改善
上記のアルゴリズムの時間計算量はO(n²)です。二分探索を用いることで、O(n log n)の計算量でLISを求めることができます：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int longestIncreasingSubsequenceOptimized(const vector<int>& nums) {
vector<int> tails;
for (int num : nums) {
auto it = lower_bound(tails.begin(), tails.end(), num);
if (it == tails.end()) {
tails.push_back(num);
} else {
*it = num;
}
}
return tails.size();
}
int main() {
vector<int> sequence = {3, 10, 2, 1, 20};
cout << "最長増加部分列の長さ（最適化版）: " << longestIncreasingSubsequenceOptimized(sequence) << endl;
return 0;
}
LISの応用問題
1. 建物の問題
ある都市にNの建物があり、それぞれ異なる高さを持っています。怪盗が建物の頂点から滑空して逃走する場合、高い建物から低い建物へしか滑空できません。最も多くの建物の頂点を通過するルートを見つける問題は、LISモデルで解くことができます。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxBuildings(const vector<int>& heights) {
int n = heights.size();
vector<int> dp(n, 1);
int max_path = 1;
// 左から右へのLIS
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (heights[i] > heights[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
max_path = max(max_path, dp[i]);
}
// 右から左へのLIS
vector<int> dp_rev(n, 1);
for (int i = n - 1; i >= 0; i--) {
for (int j = n - 1; j > i; j--) {
if (heights[i] > heights[j]) {
dp_rev[i] = max(dp_rev[i], dp_rev[j] + 1);
}
}
max_path = max(max_path, dp_rev[i]);
}
return max_path;
}
int main() {
vector<int> buildings = {300, 207, 155, 299, 298, 170, 158, 65};
cout << "通過できる建物の最大数: " << maxBuildings(buildings) << endl;
return 0;
}
2. 登山ルートの問題
山にNの観光地があり、それぞれ異なる標高があります。観光地を訪れる際、標高が単調に増加した後単調に減少するルートを考えます。このようなルートの最長のものを求める問題もLISモデルで解くことができます。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxHikingSpots(const vector<int>& elevations) {
int n = elevations.size();
vector<int> up(n, 1), down(n, 1);
// 上り坂のDP
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (elevations[j] < elevations[i]) {
up[i] = max(up[i], up[j] + 1);
}
}
}
// 下り坂のDP
for (int i = n - 1; i >= 0; i--) {
for (int j = n - 1; j > i; j--) {
if (elevations[j] < elevations[i]) {
down[i] = max(down[i], down[j] + 1);
}
}
}
int max_spots = 0;
for (int i = 0; i < n; i++) {
max_spots = max(max_spots, up[i] + down[i] - 1);
}
return max_spots;
}
int main() {
vector<int> mountains = {186, 186, 150, 200, 160, 130, 197, 220};
cout << "訪問できる観光地の最大数: " << maxHikingSpots(mountains) << endl;
return 0;
}
3. 合唱隊形の問題
N人の生徒が一列に並んでおり、その中からK人の生徒を選んで隊形を作ります。隊形は、ある位置までは身長が増加し、その後は減少するようにしたい場合の最小除外人数を求める問題です。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int minStudentsToRemove(const vector<int>& heights) {
int n = heights.size();
vector<int> up(n, 1), down(n, 1);
// 上り坂のDP
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (heights[j] < heights[i]) {
up[i] = max(up[i], up[j] + 1);
}
}
}
// 下り坂のDP
for (int i = n - 1; i >= 0; i--) {
for (int j = n - 1; j > i; j--) {
if (heights[j] < heights[i]) {
down[i] = max(down[i], down[j] + 1);
}
}
}
int max_form = 0;
for (int i = 0; i < n; i++) {
max_form = max(max_form, up[i] + down[i] - 1);
}
return n - max_form;
}
int main() {
vector<int> students = {186, 186, 150, 200, 160, 130, 197, 220};
cout << "除外する必要のある生徒の最小数: " << minStudentsToRemove(students) << endl;
return 0;
}
4. 友好都市の問題
二つの岸にある都市間に航路を引く問題で、交差しない航路の最大数を求めます。これは、一方の岸の都市を座標順に並べたときに、もう一方の岸の対応する都市の座標が単調増加する部分列の最大長を求める問題と同じです。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxNonCrossingRoutes(int n, const vector<pair<int, int>>& cities) {
// 北岸の座標でソート
vector<pair<int, int>> north_sorted = cities;
sort(north_sorted.begin(), north_sorted.end());
// 南岸の座標を抽出
vector<int> south_coords;
for (const auto& city : north_sorted) {
south_coords.push_back(city.second);
}
// 南岸の座標におけるLISを計算
vector<int> dp(n, 1);
int max_routes = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (south_coords[i] > south_coords[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
max_routes = max(max_routes, dp[i]);
}
return max_routes;
}
int main() {
vector<pair<int, int>> city_pairs = {{22, 4}, {2, 6}, {10, 3}, {15, 12}, {9, 8}, {17, 17}, {4, 2}};
int num_cities = city_pairs.size();
cout << "交差しない航路の最大数: " << maxNonCrossingRoutes(num_cities, city_pairs) << endl;
return 0;
}
5. 最大増加部分列和の問題
単調増加する部分列の中で、その和が最大になるものを求める問題です。通常のLISの問題に加えて、各部分列の和を考慮する必要があります。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxIncreasingSubsequenceSum(const vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 0);
int max_sum = 0;
for (int i = 0; i < n; i++) {
dp[i] = nums[i];
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + nums[i]);
}
}
max_sum = max(max_sum, dp[i]);
}
return max_sum;
}
int main() {
vector<int> sequence = {1, 7, 3, 5, 9, 4, 8};
cout << "最大増加部分列和: " << maxIncreasingSubsequenceSum(sequence) << endl;
return 0;
}
まとめ
最長増加部分列モデルは、単純な数列の問題から、建物のルート計画、登山ルートの最適化、合唱隊形の配置、都市間の航路設計、最大和の部分列探索まで、様々な応用が可能です。動的計画法を用いることで、これらの問題を効率的に解くことができます。特に、二分探索を用いた最適化により、計算量を大幅に削減できる場合があります。
このモデルを理解することで、単純な数列の問題から始めて、より複雑な最適化問題へと応用を広げることができます。アルゴリズムの設計においては、問題の本質を捉え、既存のモデルを適切に応用することが重要です。