kmjp's blog

競技プログラミング参加記です

TopCoderOpen 2021 Wildcard Elimination 1 : Medium ExamSeating

うーむ、出てたら落としてたな。
https://community.topcoder.com/stat?c=problem_statement&pm=17127&rd=18776

問題

50*50以下の任意サイズのグリッドを用意し、その各マスに、アルファベット1文字を埋めるか、空のままにするようにしたい。
この時、以下の条件を満たすものを構築せよ。

  • 各文字の登場回数が入力で与えられるので、それを満たす。
  • 同じ文字の書かれたマスは隣接しない。
  • 空のセルは極力減らす。

解法

グリッドサイズを総当たりすることを考える。
同じ文字を極力多数敷き詰めようとすると、市松模様状に敷き詰めることになる。
そこで、最多登場の文字が市松模様に収まるような、幅・高さの最小値を求めよう。

次に実際の文字を埋めて行く。
最多登場の順から、市松模様状に埋めて行けばよい。
埋め方の順によっては、2番目の登場頻度が多い文字が隣接してしまうので、空マスを2番目に確定させていくとよい。

class ExamSeating {
	public:
	vector <string> distribute(string students) {
		pair<int,int> P[27]={};
		int i,y,x,z;
		FOR(i,27) P[i].second=i;
		FORR(c,students) P[c-'a'].first++;
		sort(P,P+26);
		reverse(P,P+26);
		int mix=51,miy=51;
		for(x=1;x<=50;x++) for(y=1;y<=50;y++) {
			if(x*y<students.size()) continue;
			if((x*y+1)/2<P[0].first) continue;
			if(x*y<mix*miy) {
				mix=x,miy=y;
			}
		}
		if(mix==51) return {};
		cout<<mix<<" "<<miy<<endl;
		P[26]={mix*miy-students.size(),26};
		swap(P[1],P[26]);
		
		vector<string> S;
		FOR(i,miy) S.push_back(string(mix,'-'));
		FOR(i,2) {
			FOR(y,miy) {
				for(x=(i+y)%2;x<mix;x+=2) {
					FOR(z,27) if(P[z].first) {
						P[z].first--;
						if(P[z].second!=26) S[y][x]='a'+P[z].second;
						break;
					}
				}
			}
		}
		return S;
		
		
	}
}

まとめ

EasyもMediumも1発では通ってなかった…。