AtCoder ARC #212 : D - Two Rooms

ちょっと手間取ったけど解けて良かった。
https://atcoder.jp/contests/arc212/tasks/arc212_d

問題

N人の人を２つのグループに分けたい。
人x,yの親密度A[x][y]が与えられる。(なお、A[x][y]=A[y][x]である)

各人に対し、同じグループ内の人との親密度の和が、別グループの人との親密度の和以上となるようにしたい。
条件を満たすグループわけを求めよ。

解法

各人に対し、(同じグループ内の人との親密度の和)-(別グループの人との親密度の和)が０以上となるようにしたい。
そこで、上記値が負の人がいたらその人のグループを反対にすることを考える。
当然この人に関しては、条件を満たすようになる。

重要なのはA[x][y]=A[y][x]で、この人のグループ変更により、他の人が「(同じグループ内の人との親密度の和)-(別グループの人との親密度の和)」が減るケースはあるにせよ、各人の「(同じグループ内の人との親密度の和)-(別グループの人との親密度の和)」の総和は改善する方向になる。
よって、条件を満たさない人を見つけてグループを反対にすることを繰り返せば、いずれ全員が情報を満たすようになる。

int N;
int A[55][55];
int C[55];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(y,N) FOR(x,N) cin>>A[y][x];
	for(i=1;i<N;i++) {
		while(1) {
			FOR(x,i+1) {
				int sum=0;
				FOR(y,i+1) {
					if(C[x]==C[y]) sum+=A[x][y];
					else sum-=A[x][y];
				}
				if(sum<0) {
					C[x]^=1;
					break;
				}
			}
			if(x==i+1) break;
		}
	}
	
	FOR(x,N) cout<<"XY"[C[x]];
	cout<<endl;
	
}

まとめ

証明不十分で行ってしまった…。