kmjp's blog

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

Codeforces #434 Div1 C. Tests Renumeration

一見面倒くさそうでそうでもなかった。
http://codeforces.com/contest/860/problem/C

問題

N個のテスト用ファイルがあり、それぞれのファイル名と、簡単か否かが与えられる。
これらのテストファイルに対し、ファイル名の変更コマンドを用いて以下のようにしたい。

  • N個中で簡単なテストがE個あるとき、ファイル名1~Eが簡単なテストで、(E+1)~Nがそうでないテストである。

ファイル名変更により、同名ファイルが複数ある状態が存在してはならない場合、条件を満たすようファイル名変更を行う最小手順を答えよ。

解法

setを用いて、以下を管理しよう。
元々条件を満たす名前になっているものは最初にはずしておく。

  1. 簡単なテストが来るべきファイル名のうち、使われてないもの
  2. 簡単でないテストが来るべきファイル名のうち、使われてないもの
  3. 簡単なテストが来るべきファイル名のうち、簡単でないテストが来るべきファイル名が付いているもの
  4. 簡単でないテストが来るべきファイル名のうち、簡単なテストが来るべきファイル名が付いているもの
  5. 1~N以外の名前のファイルのうち、簡単なテスト
  6. 1~N以外の名前のファイルのうち、簡単でないテスト

1,2にそれぞれ候補がある場合、まずは4,3のものを名前変更して1,2に充当していこう。
4,3がない場合は5,6から充当していく。
1~6すべてが空になったら終了。

上記手順では、3,4が同数残った場合それ以上処理が進められない。
その場合、3のどれか1個を適当なファイル名にすれば、3がなくなる代わりに1と6が増えるので、また処理を継続できる。

int N;
string F[101010];
int T[101010];
int E;

set<string> A,B;
set<string> AB,BA,FA,FB;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>F[i]>>T[i];
		if(T[i]==1) E++;
	}
	
	for(i=1;i<=N;i++) {
		string s=to_string(i);
		if(i<=E) A.insert(s);
		else B.insert(s);
	}
	
	FOR(i,N) {
		if(A.count(F[i])) {
			A.erase(F[i]);
			if(T[i]==0) AB.insert(F[i]);
		}
		else if(B.count(F[i])) {
			B.erase(F[i]);
			if(T[i]==1) BA.insert(F[i]);
		}
		else {
			if(T[i]==0) FB.insert(F[i]);
			else FA.insert(F[i]);
		}
	}
	
	vector<pair<string,string>> R;
	while(A.size() || B.size() || AB.size() || BA.size()) {
		if(A.size() && BA.size()) {
			R.push_back({*BA.begin(),*A.begin()});
			A.erase(A.begin());
			B.insert(*BA.begin());
			BA.erase(BA.begin());
			continue;
		}
		if(B.size() && AB.size()) {
			R.push_back({*AB.begin(),*B.begin()});
			B.erase(B.begin());
			A.insert(*AB.begin());
			AB.erase(AB.begin());
			continue;
		}
		if(A.size() && FA.size()) {
			R.push_back({*FA.begin(),*A.begin()});
			A.erase(A.begin());
			FA.erase(FA.begin());
			continue;
		}
		if(B.size() && FB.size()) {
			R.push_back({*FB.begin(),*B.begin()});
			B.erase(B.begin());
			FB.erase(FB.begin());
			continue;
		}
		assert(AB.size()==BA.size() && AB.size());
		A.insert(*AB.begin());
		R.push_back({*AB.begin(),"zzzzz"});
		AB.erase(AB.begin());
		FB.insert("zzzzz");
	}
	
	cout<<R.size()<<endl;
	FORR(r,R) cout<<"move "<<r.first<<" "<<r.second<<endl;
	
	
}

まとめ

ディレクトリが存在しない世界は平和だ。