なかなか面白かった。
http://codeforces.com/contest/486/problem/E
問題
N要素の整数列A[i]が与えられる。
ここで、A[i]のLIS(Longest Increasing Subsequence)を考える。
LISとなる部分列は複数通り考えうる。
各A[i]を以下の3つのパターンに属すか答えよ。
- A[i]はどのLISに含まれない。
- A[i]はいずれかのLISに含まれうるが、全てのLISには含まれない。
- 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"); }
まとめ
あまり自信がなかったが、最終的に通ってよかった。