Codeforces #606 Div1 C. Beautiful Rectangle

ぼちぼち半年離されてしまう…。
https://codeforces.com/contest/1276/problem/C

問題

N個の整数が与えられる。
このうちいくつかを用いて、H*Wの行列を作ったとする。
行・列に同じ要素が来ないように並べられる、最大個数はいくつか。
実際に構築せよ。

解法

同じ要素は、min(H,W)個だけ含められる。
そこでHを総当たりし、各要素pの登場回数C(p)にたいしsum(min(H,C(p)))を足したときWをどこまで伸ばせるか考えよう。
あとは同じ要素を斜めに順に埋めて行くだけ。

int N;
map<int,int> C;
vector<int> D[404040];
int sum[404040];
 
vector<int> ret[404040];
 
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		C[x]++;
	}
	
	ll S=N;
	int over=0;
	FORR(m,C) D[m.second].push_back(m.first);
	
	int H=0,W=0,ma=0;
	for(i=400000;i>=1;i--) {
		
		ll sum=S+over*i;
		int tw=sum/i;
		if(tw>=i) {
			if(i*tw>ma) {
				ma=i*tw;
				H=i;
				W=tw;
			}
		}
		
		S-=D[i].size()*i;
		over+=D[i].size();
	}
	
	int num=0;
	for(i=400000;i>=1;i--) {
		FORR(d,D[i]) {
			FOR(j,min(H,i)) if(num<ma) {
				ret[num%H].push_back(d);
				num++;
			}
		}
	}
	
	cout<<ma<<endl;
	cout<<H<<" "<<W<<endl;
	FOR(y,H) {
		FOR(x,W) cout<<ret[y][(x-y+W)%W]<<" ";
		cout<<endl;
	}
	
	
}

まとめ

これはCにしても妙に簡単だと思ったら、1250ptだった。