Fが解けなかったのは残念だが一応レートは増。
http://codeforces.com/contest/1054/problem/C
問題
N要素の数列A[i]がある。各要素は1~Nの値を取る。
A[i]の手前にA[i]未満の数はL[i]個、A[i]の後にA[i]未満の数はR[i]個あるという情報が与えられる。
条件を満たすA[i]を構築せよ。
解法
2つ解法がある。
1つめは、「左右に自身より大きな値の未確定要素がない」というような要素が存在する場合、Nから降順で値を割り当てていく。
自分の解法はこちら。
2つめは、A[i]=N-L[i]-R[i]を割り当て、条件を満たすか判定する方法。こっちの方が実装が楽かもな。
int N; int L[1010],R[1010]; int A[1010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) cin>>L[i]; FOR(i,N) cin>>R[i]; for(i=N;i>=1;i--) { vector<int> V; FOR(x,N) if(L[x]==0 && R[x]==0 && A[x]==0) V.push_back(x); FORR(v,V) { A[v]=i; } FORR(v,V) { FOR(x,N) { if(x<v && A[x]==0) R[x]--; if(x>v && A[x]==0) L[x]--; } } } FOR(x,N) if(A[x]==0) return _P("NO\n"); cout<<"YES"<<endl; FOR(i,N) cout<<A[i]<<" "; cout<<endl; }
まとめ
なぜわざわざややこしい方に行ってしまったのか。