AtCoder

ABC006 D問題(トランプ挿入ソート)を解く

AtCoder_ABC006_D

AtCoder が提供しているABC(AtCoder Beginner Contest)006 D問題をC++で解いてみました。ABC006は、2014年4月5日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

D問題 トランプ挿入ソート(Difficulty : 1696(参考値))

問題の詳細は、リンク先をご覧ください。

ABC006 D問題 トランプ挿入ソート

最長増加部分列(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 の問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA