第4回 ドワンゴからの挑戦状 本戦 : B - だんだん強く

本番出てたらC,Dは解けてなさそう。
https://dwacon2018-final-open.contest.atcoder.jp/tasks/dwacon2018_final_b

問題

N要素の整数列V[i]が与えられる。
この部分列を考える。
基本的にはLISとなるように、すなわち部分列の各要素は直前の要素より大きくなるようにしたい。

しかしK回だけその条件に反してもよいとき、最長の部分列の長さを求めよ。

解法

f(n,k) := Vの部分列のうちV[n]を末尾とするもので、k回問題の条件に反するときの最長部分列
とする。

となる。
kを徐々に増やしながら、f(0,k)～f(N,k)を順に埋めていこう。
maxのうち前者は単純にf(i,k-1)の最大値を覚えておけばよいし、後者はV[i]を座標圧縮しておけばSegTree等で求めることができる。

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=0;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=max(val[entry],v);
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};

SegTree_1<int,1<<20> st;
int pre[101010];
int cur[101010];
int N,K;
int V[101010];
int ma;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	vector<int> C;
	C.push_back(-1);
	FOR(i,N) {
		cin>>V[i];
		C.push_back(V[i]);
	}
	sort(ALL(C));
	C.erase(unique(ALL(C)),C.end());
	FOR(i,N) V[i]=lower_bound(ALL(C),V[i])-C.begin();
	
	for(i=0;i<=K;i++) {
		FOR(x,st.val.size()) st.val[x]=0;
		int pm=0;
		ZERO(cur);
		FOR(x,N) {
			cur[x]=max(pm,st.getval(0,V[x]))+1;
			ma=max(ma,cur[x]);
			st.update(V[x],cur[x]);
			pm=max(pm,pre[x]);
		}
		swap(pre,cur);
	}
	cout<<ma<<endl;
	
	
}

まとめ

これは600ptでもいい気がするな。