Codeforces #602 Div1 E. Not Same

これもDiv1Eにしては簡単。
http://codeforces.com/contest/1261/problem/E

問題

N要素の整数列Aが与えられる。A[i]は1以上N以下である。
ここから、Aの要素のsubsetを選び、デクリメントする作業を最大(N+1)回行える。
ただし同じsubsetの選び方は重複できないとする。
Aをすべて0にする手順を示せ。

解法

Aを大きい順に処理し、「処理し終わったところは0、それ以外は最低1残す」という手順を繰り返していく。
今未処理のうち最大値がA[x]=yだったとする。
次の1手はA[x]をデクリメントせず、続くy手でデクリメントするものとする。
この場合、次の1手は他の要素はデクリメントしてもしなくてもよい。
そこで、A[i]＞1である要素iはデクリメントすることにしよう。

そうすると残された要素は1以上y-1以下なので、次のy手を同様に処理していけば、いずれ全要素0になる。

int N;
int A[1010];
pair<int,int> P[1010];
string S[1010];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N+1) {
		S[i]=string(N,'0');
	}
	int cur=0;
	FOR(i,N) {
		cin>>A[i];
		P[i]={A[i],i};
	}
	sort(P,P+N);
	reverse(P,P+N);
	
	FOR(i,N) {
		x=P[i].second;
		FOR(y,A[x]) {
			S[i+1+y][x]='1';
		}
		for(j=i+1;j<N;j++) {
			y=P[j].second;
			if(A[y]>1) {
				A[y]--;
				S[i][y]='1';
			}
		}
		
	}
	
	
	
	int num=0;
	FOR(i,N+1) if(count(ALL(S[i]),'1')) num++;
	cout<<num<<endl;
	FOR(i,N+1) if(count(ALL(S[i]),'1')) cout<<S[i]<<endl;
	
	
}

まとめ

これは本番自分でもよく思いついたと思ったけど、結構手間取ってるな。