Looksery Cup 2015 : B. Looksery Party

Cをしょうもないミスで逃して50位に入れず…。
なんとかレートは微増でTシャツゲット。Aは簡単なので省略します。
http://codeforces.com/contest/549/problem/B

問題

N人の間で、各人が誰を電話帳に加えているかの情報が与えられる。
(なお、自分は必ず電話帳に入っている)

N人のうち何人かがパーティーに参加しており、参加者は電話帳にいる全員にメッセージを送る。
i番の人の受け取ったメッセージ数がA[i]にならないようなパーティー参加パターンを答えよ。

解法

概ね二通り考えられる。
自分は前者。

乱拓解

各人は必ず自分を電話帳に入っているため、その人のパーティー参加の有無を切り替えれば、その人のメッセージ受け取り数は必ず変化する。
よって、メッセージ数がA[i]ちょうどの人が残っている間、ランダムでその中の一人のパーティー参加を切り替えればよい。

各人において満たすべき条件は緩いので、これですんなり通る。

貪欲解

A[i]を「あとこの数だけ受け取ってはいけないメッセージ数」と考える。
A[i]==0の人がいなければ、それ以上パーティー参加者を増やさなければ良い。

A[i]==0の人がいる場合、その人を参加させれば、A[i]は確実に0以外になる。
あとは貪欲にA[i]==0の人がいる限りこの処理を繰り返せばよい。

int N;
string mat[101];
int A[101];
int C[101],T[101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(y,N) {
		cin>>mat[y];
		FOR(x,N) mat[y][x]-='0';
	}
	
	FOR(i,N) cin>>A[i], A[i]=-A[i];
	
	srand(time(NULL));
	FOR(i,101010) {
		
		vector<int> V;
		FOR(i,N) if(A[i]==0) V.push_back(i);
		
		if(V.empty()) {
			x=0;
			FOR(i,N) x+=C[i];
			_P("%d\n",x);
			FOR(i,N) if(C[i]) _P("%d ",i+1);
			_P("\n");
			return;
		}
		
		x=V[rand()%V.size()];
		
		FOR(y,N) {
			if(mat[x][y]) {
				if(C[x]) A[y]--;
				else A[y]++;
			}
		}
		C[x]^=1;
	}
	_P("-1\n");
}

まとめ

これだけゆるい乱拓も珍しい。