AtCoder ABC #360 : G - Suitable Edit for LIS

細かいミスが多い。
https://atcoder.jp/contests/abc360/tasks/abc360_g

問題

整数列Aが与えられる。
1要素を選んで任意の整数値に書き換えられるとき、LIS長の最大値を求めよ。

解法

LISでよく使う、以下のテーブルを考える。
dp(i,n) := Aのi要素目まで考えたとき、長さnの最長増加列における末尾の値の最小値

このテーブルを2面使う。
dp1(i,n) := Aのi要素目まで考えたとき、長さnの最長増加列における末尾の値の最小値。まだ整数値書き換えをしていない。
dp2(i,n) := Aのi要素目まで考えたとき、長さnの最長増加列における末尾の値の最小値。まだ整数値書き換えをした。

この時、dp1(i,n)→dp1(i+1,n)やdp2(i,n)→dp2(i+1,n)はよくあるLISの状態遷移を取れる。
加えて今回、値の書き換えにより
dp2(i+1,n+1) = dp1(i,n)+1
とする遷移が可能となる。
毎回すべてのiに対しこの遷移を行うとO(N^2)となってTLEするが、dp2(i,n+1) != dp2(i,n)+1であるnを覚えておいて、そこだけこの遷移を行うようにすると良い。

int N;
int A;
vector<int> V[2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	V[0].resize(N+2);
	V[1].resize(N+2);
	FOR(i,N+2) V[0][i]=V[1][i]=1<<30;
	V[0][0]=V[1][0]=0;
	set<int> dif={1};
		
	
	FOR(i,N) {
		cin>>A;
		x=lower_bound(ALL(V[1]),A)-V[1].begin();
		V[1][x]=A;
		FORR(c,dif) V[1][c]=min(V[0][c-1]+1,V[1][c]);
		dif.clear();
		y=lower_bound(ALL(V[0]),A)-V[0].begin();
		V[0][y]=A;
		if(V[1][x]!=V[0][x-1]+1) dif.insert(x);
		if(V[1][y+1]!=V[0][y]+1) dif.insert(y+1);
		
	}
	
	int ma=0;
	FOR(i,N+2) if(V[1][i]<1<<30) ma=i;
	cout<<ma<<endl;
	
}

まとめ

しょうもないミスを繰り返した。昨日のARCでこれやらかさなくてよかったな。