Codeforces 394(#231 Div1) C. Dominoes

問題

10, 11, 00のドミノが合計でn*m個与えられる。
これらを横向きにn*m個に並べる。

それぞれの列ごとにその列の数の和を求める。
この和の最大値が、最小になるようにしたい。最小値を求めよ。

ドミノは回転させることはできるが、縦に使うことはできない。

制約条件

n, m≦10^3

方針

なんか迷走。

10は半分を10, 残りを01と使うとするのが最善。
11, 10, 01をmの倍数の部分は一行に敷き詰めてしまってよい。
mで割った余りの部分が少し考える必要がある。

二列余裕があったら10はできるだけその下に01を置くのが最善。
あとは適当に埋める。という方針で通った。

ソースコード

int sum[2000];
vi ans[1000];
const char *ch[] = {"00", "01", "10", "11"};

int main(){
	int n, m, cnt[4] = {};
	scanf("%d%d", &n, &m);
	rep(i, n) rep(j, m){
		char in[3];
		scanf("%s", in);
		int a = (in[0] - '0') * 2 + in[1] - '0';
		cnt[a]++;
	}
	int s = cnt[1] + cnt[2];
	cnt[1] = s / 2; cnt[2] = s - s / 2;
	
	for(int i = 1; i < 4; i++){
		rep(j, cnt[i] / m) rep(k, m) ans[k].pb(i);
		cnt[i] %= m;
	}
	
	int l = n - ans[0].size(), t = min(cnt[1], cnt[2]);
	if(l > 1) rep(i, t) ans[i].pb(1), ans[i].pb(2);
	cnt[1] -= t; cnt[2] -= t;
	
	for(int i = t; i < m; i++){
		if(cnt[3]) ans[i].pb(3), cnt[3]--;
		else if(cnt[2]) ans[i].pb(2), cnt[2]--;
		else if(cnt[1]) ans[i].pb(1), cnt[1]--;
	}
	while(cnt[1] + cnt[2] + cnt[3] > 0){
		rep(i, m) if(ans[i].size() < n){
			if(cnt[3]) ans[i].pb(3), cnt[3]--;
			else if(cnt[2]) ans[i].pb(2), cnt[2]--;
			else if(cnt[1]) ans[i].pb(1), cnt[1]--;
		}
	}
	
	rep(i, m) while(ans[i].size() < n) ans[i].pb(0);
	rep(i, n) rep(j, m) cout << ch[ans[j][i]] << (j==m-1?"\n":" ");
	
	return 0;
}