読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

UVa 111 - History Grading

UVa

- 問題概要

n個の整数c_1,c_2,,,c_nが与えられます。
これはi番目のイベントがc_i番目に発生することを示している。
学生の提出したテストが続いて与えられ、
i番目のイベントがr_i番目に発生したと記述されています。
最も長い正しい年代順の部分列長を答えよという問題です。

- 解法1

始めに、年代順に整数を並び替えます。
例)
1 3 2 4 → 1 3 2 4
3 1 2 4 9 5 10 6 8 7 → 2 3 1 4 6 8 10 9 5 7
各整数列を上記のように並び替え、
正しい整数列と学生のテストの整数列の最長共通部分列長を求めればOKです。
この方法を使うとO(n^2)で求められます。

- 解法2

最長共通部分列の問題から最長増加部分列の問題に変換します。
最長増加部分列は2分探索を用いるとO(n\log n)になるからです。
c_iは並び替えずに使用します。
r_iを並び替えたものをr'_jとすると、
学生のテストではj番目に発生するイベントが正しい年代順ではc_{r'_j}に発生することになります。
少し分かりづらいですがc_{r'_j}の最長増加部分列が解になります。

- ソースコード

解法2で解いてます。
vectorは必ずしも全てつながっているとは限らないのでstd::fillが使えないのですね。
初めて知りました。

#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
#include<complex>

using namespace std;

#define reE(i,a,b) for(auto (i)=(a);(i)<=(b);(i)++)
#define rE(i,b) reE(i,0,b)
#define reT(i,a,b) for(auto (i)=(a);(i)<(b);(i)++)
#define rT(i,b) reT(i,0,b)
#define rep(i,a,b) reE(i,a,b);
#define rev(i,a,b) for(auto (i)=(b)-1;(i)>=(a);(i)--)
#define itr(i,b) for(auto (i)=(b).begin();(i)!=(b).end();++(i))
#define LL long long
#define all(b) (b).begin(),(b).end()

#define input_init stringstream ss; string strtoken, token; istringstream is
#define input_line  getline(cin, strtoken);is.str(strtoken);is.clear(istringstream::goodbit)
#define input_token(num) ss.str(""); ss.clear(stringstream::goodbit); getline(is, token, ','); ss << token; ss >> num

typedef complex<double> P;
typedef vector<P> Poly;

const LL INF = 1 << 30;
const double eps = 1e-8;
int n,tmp;
vector<int> dp;
vector<int>c, r;
int solve(){
	itr(i, dp)*i = INF;
	rT(i, n)*lower_bound(dp.begin(), dp.end(), c[r[i]]) = c[r[i]];
	return(distance(dp.begin(),lower_bound(dp.begin(), dp.end(), INF)));
	
}

int main(){
	cin >> n;
	c.resize(n);
	dp.resize(n);
	r.resize(n);
	rT(i, n){
		cin >> tmp;
		c[i] = tmp-1;
	}
	while (cin >> tmp){
		r[tmp - 1] = 0;
		reT(i, 1, n){
			cin >> tmp;
			r[tmp - 1] = i;
		}
		cout << solve() << endl;
	}

	return(0);
}