kmjp's blog

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

Mail.Ru Cup 2018 Round 1 : C. Candies Distribution

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;
	
}

まとめ

なぜわざわざややこしい方に行ってしまったのか。