一見面倒くさそうでそうでもなかった。
http://codeforces.com/contest/860/problem/C
問題
N個のテスト用ファイルがあり、それぞれのファイル名と、簡単か否かが与えられる。
これらのテストファイルに対し、ファイル名の変更コマンドを用いて以下のようにしたい。
- N個中で簡単なテストがE個あるとき、ファイル名1~Eが簡単なテストで、(E+1)~Nがそうでないテストである。
ファイル名変更により、同名ファイルが複数ある状態が存在してはならない場合、条件を満たすようファイル名変更を行う最小手順を答えよ。
解法
setを用いて、以下を管理しよう。
元々条件を満たす名前になっているものは最初にはずしておく。
- 簡単なテストが来るべきファイル名のうち、使われてないもの
- 簡単でないテストが来るべきファイル名のうち、使われてないもの
- 簡単なテストが来るべきファイル名のうち、簡単でないテストが来るべきファイル名が付いているもの
- 簡単でないテストが来るべきファイル名のうち、簡単なテストが来るべきファイル名が付いているもの
- 1~N以外の名前のファイルのうち、簡単なテスト
- 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; }
まとめ
ディレクトリが存在しない世界は平和だ。