AtCoder が提供しているABC(AtCoder Beginner Contest)006 D問題をC++で解いてみました。ABC006は、2014年4月5日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 トランプ挿入ソート(Difficulty : 1696(参考値))
問題の詳細は、リンク先をご覧ください。
最長増加部分列(LIS: Longest Increasing Subsequence)を求めることに帰着できます。AtCoder Problems による Difficulty は 1696(参考値)でした。
解答案
数列の連続しない部分列で、最も長い増加列の長さを求めます。増加列に含まれない数字を入れ替えることで、昇順の数列を得ることができます。したがって、数列の長さから最長増加部分列の長さを引いた値が解となります。
この一番長い増加列を最長増加部分列(LIS: Longest Increasing Subsequence)と呼びます。
C++ プログラム例(ABC006D)
最長増加部分列(LIS)を求めるアルゴリズムを実装しました。
- 配列
dp
を無限大(INF)で初期化します。 - 数列の値
c[i]
以上の場所をlower_bound
で検索し、その位置の値をc[i]
で置き換えます。 - INF より小さな値で埋められた配列
dp
の長さが LIS となります。
以下が、C++プログラムです。ポイントとなる行の背景色を変更しました。
#include <bits/stdc++.h>
using namespace std;
#define INF (1 << 30)
int main()
{
int n;
cin >> n;
vector<int> c(n);
for (int i = 0; i < n; ++i) {
cin >> c[i];
}
vector<int> dp(n + 1, INF);
for (int i = 0; i < n; ++i) {
auto it = lower_bound(dp.begin(), dp.end(), c[i]);
*it = c[i];
}
int result = n;
result -= lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
cout << result << endl;
return 0;
}
AC(Accepted=正しいプログラム)と判定されました。
最後に
公式解説には、「実は、多くのコンテストに出題されている、超典型問題です。」記載されていました。学習効果が高いと考えて記事にしました。
引き続き ABC の問題を紹介していきます。