kmjp's blog

競技プログラミング参加記です

Codeforces #277 Div2 E. LIS of Sequence

なかなか面白かった。
http://codeforces.com/contest/486/problem/E

問題

N要素の整数列A[i]が与えられる。
ここで、A[i]のLIS(Longest Increasing Subsequence)を考える。
LISとなる部分列は複数通り考えうる。

各A[i]を以下の3つのパターンに属すか答えよ。

  1. A[i]はどのLISに含まれない。
  2. A[i]はいずれかのLISに含まれうるが、全てのLISには含まれない。
  3. A[i]は全てのLISには含まれる。

解法

まずLISを求める。これは既存のアルゴリズムを利用。
この過程で、A[i]を最後の要素する単調増加列で、A[i]が最大何要素目に来るか求めることができる。

例えばこの値をID[i]とする。ID[i]の最大値はLISの要素数と一致する。

この何要素目かを用いて、まずパターン1と2の分類を行う。
iを大きい順に処理していく。

  • ID[i]がLISの要素数と一致するなら、A[i]はパターン2
  • A[j]>A[i]かつA[j]はパターン2かつID[j]==ID[i]+1となるjがあるなら、A[j]はパターン2
    • すなわち、A[i]の後にA[i]より大きくLISに含まれうる要素があるなら、A[i]もLISに含まれうる、と考える。
    • 条件を満たすjの有無は、各ID[j]におけるA[j]の最大値を覚えておけば容易。
  • 上記どちらでもないものはパターン1

次に、パターン2に含まれる要素群において、各ID値の数をカウントする。
あるIDを持つA[i]が1個しかない場合、全てのLISはそのA[i]を含まざるを得ないので、パターン3である。

int N;
int A[100020];
int id[100020];
int dp[100020];
int num[100020];
int mi[100020];
int pat[100020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	int ma=0;
	cin>>N;
	
	FOR(i,N+1) dp[i]=1<<20;
	FOR(i,N) {
		cin>>A[i];
		id[i] = lower_bound(dp,dp+N,A[i]) - dp;
		ma=max(ma,id[i]);
		dp[id[i]] = A[i];
		num[id[i]]++;
	}
	
	for(i=N-1;i>=0;i--) {
		if(id[i]==ma || A[i]<mi[id[i]+1]) mi[id[i]]=max(mi[id[i]],A[i]), pat[i]=1;
		if(pat[i]==0) num[id[i]]--;
	}
	
	FOR(i,N) if(pat[i]==1 && num[id[i]]==1) pat[i]=2;
	FOR(i,N) _P("%d",pat[i]+1);
	_P("\n");
}

まとめ

あまり自信がなかったが、最終的に通ってよかった。