読者です 読者をやめる 読者になる 読者になる

kmjp's blog

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

TopCoder SRM 689 Div1 Easy ColorfulGarden

ドタバタしたけどなんとかEasy/Medium解いてレート微増。
https://community.topcoder.com/stat?c=problem_statement&pm=14243

問題

2*Nのグリッド上の各セルに文字が配置されている。
セル間の文字を任意の回数swap可能であるとするとき、隣り合うセルが同じ文字にならないようにせよ。

解法

基本的に同じ文字をジグザグに配置していけば、最大N個まで同じ文字を置ける。
その際注意点は、N個同じ文字がある場合最初にそれを配置すること。
例えば2*3のグリッドにabbbccとあるとき、aから順にジグザグに置いてしまうと

acb
bbc
|

のようになってしまう。

class ColorfulGarden {
	public:
	vector <string> rearrange(vector <string> garden) {
		vector<string> R;
		R.push_back(garden[0]);
		R.push_back(garden[1]);
		int N=garden[0].size();
		int num[256]={};
		int y,x,i;
		FOR(i,2) FORR(r,garden[i]) num[r]++;
		string S;
		FOR(i,256) if(num[i]>N) return {};
		FOR(i,256) if(num[i]==N) FOR(x,num[i]) S+=i;
		FOR(i,256) if(num[i]<N) FOR(x,num[i]) S+=i;
		
		FOR(i,N*2) R[((i%N)&1)^(i>=N)][i%N] = S[i];
		
		return R;
	}
}

まとめ

最初アルファベット順に置いてたけど、ラスト5分で気づいてラスト1分位でresubmitした。

広告を非表示にする