みんなのプロコン本選 : D - KthLIS

うーん、これは本番出てても時間内には解けなさそう。
http://yahoo-procon2017-final-open.contest.atcoder.jp/tasks/yahoo_procon2017_final_d

問題

N要素の数列Aが与えられる。
この数列の部分列のうちLISを成すもので、辞書順に並べたときに小さい順にK番目に来るものを求めよ。
なお、部分列を抜き出した位置が異なっても、得られる数列が同じものは同一とみなす。

解法

Aの先頭に0、末尾に無限大相当の大きな数を入れておく。
こうするとどんなLISも先頭と末尾を含むのでやりやすくなる。

まず以下を求めよう。これはLISを求める一般的な操作の過程で求められる。
f(i) := A[0..i]の部分列のうち、単調増加でかつA[i]が末尾にくるものの最長列の要素数
上記の通り末尾は必ずLISに含まれるので、f(N-1)はLISの要素数に相当する。

次に以下を求める。
g(i) := AのLISのうち、A[i]番目を含むもので、A[(i+1)...(N-1)]の部分列は何通り選べるか。

まず「同一とみなす」を無視して考える。
すると以下の比較的単純なDPとなる。

• g(N-1)=1
• g(i) := sum(g(j)) (jはj＞i、A[j]＞A[i]、f(j)=f(i)+1)

ただ、これはA[i]=A[k]＜A[j]、f(i)+1=f(k)+1=f(j)、となるi＜j＜kがあると同じ数列を二重にカウントしてしまい破たんする。

• g(i) := sum(g(j)) (jはj＞i、A[j]＞A[i]、f(j)=f(i)+1、また上記を満たすkが存在するとき、j＜k)

として同じ要素の多重カウントを回避しよう。

g(i)が求められれば、あとは辞書順最小の数列を求める一般的なテク通り、「ここでこの値をとるケースがK個以上あるならこの値をとる、K個未満なら、次の値を検討する」ということを繰り返していけばよい。
なお、「この値(A[i])をとるケースがK個以上あるなら」の判断にはg(i)ではなくg(i)+g(k)を用いるようにしよう。

なお、Editorialではこのsumの計算をSegTreeなどで高速化することを推奨しているが、なくても通る。

int N, A[303030];
int R[303030];
int B[303030];
int nex[303030];

vector<pair<int,int>> E[303030];
ll K;
const ll ma=1LL<<61;
ll dp[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	A[0]=0;
	FOR(i,N) cin>>A[i+1];
	A[N+1]=1<<30;
	N+=2;
	
	FOR(i,N+2) R[i]=1+(1<<30);
	FOR(i,N) {
		B[i]=lower_bound(R,R+N+1,A[i])-R;
		R[B[i]]=A[i];
		E[B[i]].push_back({A[i],i});
	}
	FOR(i,N+1) {
		map<int,int> M;
		sort(ALL(E[i]));
		reverse(ALL(E[i]));
		FORR(r,E[i]) {
			x = r.second;
			nex[x]=N;
			if(M.count(A[x])) nex[x]=M[A[x]];
			M[A[x]]=x;
		}
	}
	dp[N-1]=1;
	for(i=B[N-1]-1;i>=0;i--) {
		FORR(r,E[i]) {
			x = r.second;
			FORR(r2,E[i+1]) if(r2.second>x && A[r2.second]>A[x] && r2.second<nex[x]) {
				dp[x] = min(ma,dp[x]+dp[r2.second]);
			}
		}
	}
	
	if(dp[0]<K) return _P("None\n");
	int cur=0;
	FOR(i,B[N-1]) {
		FORR(e,E[i]) {
			if(e.second>cur && nex[e.second]<N) {
				dp[e.second] = min(ma,dp[e.second]+dp[nex[e.second]]);
				dp[nex[e.second]]=0;
			}
		}
		reverse(ALL(E[i]));
		FORR(e,E[i]) {
			x = e.second;
			if(x<cur || A[x]<=A[cur]) continue;
			if(K<=dp[x]) {
				cur=x;
				if(cur) cout<<A[cur]<<" ";
				break;
			}
			else {
				K -= dp[x];
			}
		}
	}
	cout<<endl;
	
}

まとめ

こういうので多重カウントを除くのなかなかに苦手。