うーむ、出てたら落としてたな。
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発では通ってなかった…。