Codeforces #850 : Div1 B. Letter Exchange

良くもなく悪くもなく。
https://codeforces.com/contest/1785/problem/B

問題

3文字の文字列がN個与えられる。
合計でw,i,nがN個ずつある。
2つの文字列の間で1文字swapすることを繰り返し、各文字列がw,i,nが1文字ずつ含むようにしたい。
最小何回swapが必要か、またその手順を示せ。

解法

各文字列、どの文字を手離してどの文字を取り入れればよいかは一意に定まる。
もし2つの文字列の間で、互いに1回swapすれば互いの条件を満たせるものがあれば優先的にそれらを処理しよう。
残るのは、w→i→n→wの順で3つの文字列の間で3文字を3回swapしてrotateするか、w→n→i→wの順でswapするパターンなので、これらを愚直に処理しよう。

int T;
int M;

set<int> WI,WN,IW,IN,NW,NI;
vector<pair<pair<int,int>,pair<char,char>>> R;
int hoge(set<int>& A,set<int>& B,char a,char b) {
	if(A.empty()||B.empty()) return 0;
	R.push_back({{*A.begin(),*B.begin()},{a,b}});
	A.erase(A.begin());
	B.erase(B.begin());
	return 1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>M;
		WI.clear();
		WN.clear();
		IW.clear();
		IN.clear();
		NW.clear();
		NI.clear();
		FOR(i,M) {
			cin>>s;
			x=count(ALL(s),'w');
			y=count(ALL(s),'i');
			k=count(ALL(s),'n');
			if(x>1&&y==0) WI.insert(i);
			if(x>1&&k==0) WN.insert(i);
			if(y>1&&x==0) IW.insert(i);
			if(y>1&&k==0) IN.insert(i);
			if(k>1&&x==0) NW.insert(i);
			if(k>1&&y==0) NI.insert(i);
		}
		R.clear();
		
		while(1) {
			if(hoge(WI,IW,'w','i')) continue;
			if(hoge(WN,NW,'w','n')) continue;
			if(hoge(IN,NI,'i','n')) continue;
			if(WI.size()&&IN.size()&&NW.size()) {
				x=*WI.begin(); WI.erase(WI.begin());
				y=*IN.begin(); IN.erase(IN.begin());
				k=*NW.begin(); NW.erase(NW.begin());
				R.push_back({{x,y},{'w','i'}});
				R.push_back({{y,k},{'w','n'}});
				continue;
			}
			if(WN.size()&&NI.size()&&IW.size()) {
				x=*WN.begin(); WN.erase(WN.begin());
				y=*NI.begin(); NI.erase(NI.begin());
				k=*IW.begin(); IW.erase(IW.begin());
				R.push_back({{x,y},{'w','n'}});
				R.push_back({{y,k},{'w','i'}});
				continue;
			}
			
			
			break;
		}
		
		
		assert(WI.empty());
		assert(WN.empty());
		assert(IN.empty());
		assert(IW.empty());
		assert(NI.empty());
		assert(NW.empty());
		
		
		cout<<R.size()<<endl;
		FORR2(id,ch,R) {
			cout<<id.first+1<<" "<<ch.first<<" "<<id.second+1<<" "<<ch.second<<endl;
		}
		
		
	}
}

まとめ

コード量そこそこあるし手間ではあるけど、難しくはないね。