Codeforces #720 Div2 : E. Nastia and a Beautiful Matrix

コードはさほど長くない。
https://codeforces.com/contest/1521/problem/E

問題

正整数の多重集合が与えられる。
N*Nのグリッドの一部のマスに、この多重集合に含まれる正整数を配置したい。
1つのマスには1つの整数までしか配置できない。整数が配置されないマスがあってもよい。
以下の条件を満たす配置のうち、最小のNと配置の一例を求めよ。

• 2*2の領域を見たとき、
  • 正整数が配置されるマスは3つ以下である。
  • 対角上に同じ正整数が2個配置されることはない。

解法

まずNの最小値を考える。以下を両方満たすNを求めよう。

• 1つ目の条件から、多重集合のサイズ分の生成整数を配置しきれるN(約3/4のマスに正整数を配置できる)
• 2つ目の条件から、最頻値を配置しきれるN(同じ値は1行おきに埋めると約半分のマスに配置できる)

(列・行番号を0-originとして)以下の条件を満たすマスに正整数を配置することを考える。
この時点で前者の条件は満たす。
a. 列番号も行番号も偶数
b. 列番号が偶数、行番号は奇数
c. 列番号が奇数、行番号は偶数

後ろ2つに同じ正整数が配置されてはならない。そこで、b→a→cの順で最頻値から順に同じ値を敷き詰めて行くと良い。

int T,M,K;
pair<int,int> P[101010];

int A[1010][1010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	FOR(k,T) {
		cin>>M>>K;
		FOR(i,K) {
			cin>>x;
			P[i]={-x,i+1};
		}
		sort(P,P+K);
		x=0;
		while(1) {
			int tot=x*x-(x/2)*(x/2);
			int ma=x*((x+1)/2);
			if(tot>=M&&ma>=-P[0].first) break;
			x++;
		}
		int N=x;
		vector<pair<int,int>> C[4];
		FOR(y,N) FOR(x,N) {
			A[y][x]=0;
			if(x%2==1&&y%2==0) C[0].push_back({y,x});
			else if(x%2==0&&y%2==0) C[1].push_back({y,x});
			else if(x%2==0&&y%2==1) C[2].push_back({y,x});
			
		}
		FOR(i,K) {
			FOR(x,-P[i].first) {
				y=0;
				if(C[1].size()) y=1;
				if(C[2].size()) y=2;
				assert(C[y].size());
				A[C[y].back().first][C[y].back().second]=P[i].second;
				C[y].pop_back();
			}
		}
		
		
		cout<<N<<endl;
		FOR(y,N) {
			FOR(x,N) cout<<A[y][x]<<" ";
			cout<<endl;
		}
		
	}
}

まとめ

考え方は割とシンプル。