TopCoder(delta2323) / Codeforces(delta) / twitter
2011-05-07
■ [実践][Codeforces] Yandex.Algorithm 2011 Qualification 2 
問題一覧:Dashboard - Yandex.Algorithm 2011: Qualification 2 - Codeforces
結果:Standings - Yandex.Algorithm 2011: Qualification 2 - Codeforces
= | . | A | B | C | D | E |
- | - | 0:10 | 0:50 | - | - | - |
580 | +1/-0 | 480 | -2 | - | - | - |
部屋内18位(Room 29),全体570位
Rating:1452 → 1541 (+89)
Qualfication Roundの2回目.順位だけ見ると惜しい気もしますが,ボーダーの978点に達するにはBを当てるか,後4人Hackする必要があったので,少し厳しいような気もします.BのHackが大量に行われ,多い人は20回近く成功していました.
A. Double Cola
要約
5人が1列に並んでいる.怪しげなコーラがありそれを飲むと2人に分身してしまう.先頭の人がそのコーラを飲み2人に分身し,(その2人とも,)列の後ろに並び直す事を繰り返す.n個目のコーラを飲むのは5人のうち誰かを答えよ.nは1以上10^9以下.
方針
コーラを飲んだ人もそのまま列に残っていていると,列は
SLPRH | SSLLPPRRHH | SSSSLLLLPPPPRRRRHHHH | ・・・
となり,これのn番目を求めれば良い.
コード(c++)
#include <iostream> #include <vector> #include <string> #include <cctype> typedef long long ll; using namespace std; string names[5] = {"Sheldon", "Leonard", "Penny", "Rajesh", "Howard" }; int main(){ ll n; while(cin >> n){ n--; ll unit = 5; while(n >= unit){ n-=unit; unit *=2; } unit /=5; ll div = n/unit; cout << names[div] <<endl; } return 0; }
B. Sets
要約
正数の集合がn個あり,それらは互いに共通部分を持たない.それらの中から2個を選び,和集合をとった結果が与えられている(つまり,全部でnC2=n(n-1)/2個の集合が与えられている).それらから元々の整数の集合達を復元せよ.数式で書くと,
- A[0], ..., A[n-1] ⊂ [2, 200]
- A[i] ≠ Φ
- A[i] ∩ A[j] = Φ (for all i ≠ j)
という条件のもと,A[i] ∪ A[j] 達( 1 <= i, j < n)が与えられているので,A[i]達を求めよ.
nは2以上200以下,和集合を取った後の集合のそれぞれの要素数は2個以上200個以下,それぞれの要素の値は2以上200以下.
方針
与えられた和集合のうち適当な2つの共通部分を取ると,A[i]達のうちのどれかが出てくるか,空集合となる.全通りを試すとA[i]は(n-1)(n-2)/2個表れるので,さらにユニーク操作を行えば答えが得られる.(n=2の場合0個になるので,これは例外ケースと気づける・・・気づけないですね.)ただ,これをそのまま実装するとTLEを起こします.和集合の要素数の最大数をkとするとこのアルゴリズムは大体O(kn^{4})となる.
そこで,一つの和集合を固定して,その和集合とそれ以外和集合に対して操作を行い方法で,O(kn^2)のアルゴリズムを狙う.
A[0]∪A[1] <= 固定する A[0]∪A[2] ・ ・ ・ A[n-2]∪A[n-1]
適当に番号を付け替えて,一番最初の和集合をA[0]∪A[1]とする.残りの和集合達とそれぞれ共通部分を取れば,A[0], A[1]がわかる.一方を適当に選びそれをA[0]とし,今度は「A[0]と共通部分を持つ和集合に対し,A[0]との差集合を取る」という操作を行う.A[0]と共通部分を持つのはA[0]∪A[2], ..., A[0]∪A[n-1]なので,そこからA[0]を引けばA[1], ..., A[n-1]が得られる.これにより,O(klog k n^{2})のアルゴリズムとなる.
コード例(c++)
このコードはTLEを起こします
#include <iostream> #include <vector> #include <string> #include <cctype> #include <fstream> #include <sstream> #include <algorithm> using namespace std; int INF = 10000000; void intersection(vector<int>& a, vector<int> & b, vector<int> & ret){ int posa = 0; int posb = 0; while(posa < a.size()-1 || posb < b.size() -1){ if(a[posa] > b[posb]){ posb ++; }else if(a[posa] < b[posb]){ posa ++ ; }else{ ret.push_back(a[posa]); posa++;posb++; } } } int main(){ int n; while(cin >> n){ int m = n * (n -1) /2; vector<vector<int > > table(m); for(int i = 0;i < m;i++){ int num ;cin >> num; table[i].resize(num); for(int j = 0;j< num;j++){ cin >> table[i][j]; } table[i].push_back(INF); sort(table[i].begin(), table[i].end()); } vector<vector<int> > rets; if(n ==2){ cout << 1 << " " << table[0][0] <<endl; cout << table[0].size() - 2 << " " ; for(int i = 1;i < table[0].size()-1 ;i++){ cout <<table[0][i] << " "; } cout <<endl; goto next; } for(int i = 0;i<m;i++){ for(int j = i + 1;j<m;j++){ vector<int > ret; intersection(table[i], table[j], ret); if(!ret.empty()){ rets.push_back(ret); } } } sort(rets.begin(), rets.end()); rets.erase(unique(rets.begin(), rets.end()), rets.end()); for(int i = 0;i<n;i++){ cout << rets[i].size() << " "; for(int k = 0;k<rets[i].size();k++){ cout << rets[i][k] << " " ; } cout << endl; } next:; } return 0; }
2つめの方法で行ったコードがこちら
#include <iostream> #include <vector> #include <string> #include <cctype> #include <fstream> #include <sstream> #include <algorithm> using namespace std; int INF = 10000000; void intersection(vector<int>& a, vector<int> & b, vector<int> & ret){ int posa = 0; int posb = 0; a.push_back(INF); b.push_back(INF); while(posa < a.size()-1 || posb < b.size() -1){ if(a[posa] > b[posb]){ posb ++; }else if(a[posa] < b[posb]){ posa ++ ; }else{ ret.push_back(a[posa]); posa++;posb++; } } a.pop_back(); b.pop_back(); } void setminus(vector<int> & a, vector<int> & b, vector<int> & ret){ for(int i = 0; i < b.size();i++){ if(find(a.begin(), a.end(), b[i]) == a.end()){ ret.push_back(b[i]); } } } int main(){ int n; while(cin >> n){ int m = n * (n -1) /2; vector<vector<int > > table(m); for(int i = 0;i < m;i++){ int num ;cin >> num; table[i].resize(num); for(int j = 0;j< num;j++){ cin >> table[i][j]; } sort(table[i].begin(), table[i].end()); } if(n == 2){ cout << 1 << " " << table[0][0] <<endl; cout << table[0].size() - 1 << " " ; for(int i = 1;i < table[0].size();i++){ cout <<table[0][i] << " "; } cout <<endl; }else{ vector<vector<int> > rets; for(int j = 1;j<m;j++){ vector<int > ret; intersection(table[0], table[j], ret); if(!ret.empty()){ rets.push_back(ret); } } vector<int> a0 = rets[0]; for(int j = 1;j<m;j++){ vector<int> ret; intersection(a0, table[j], ret); if(!ret.empty()){ vector<int> ai; setminus(a0, table[j], ai); rets.push_back(ai); } } sort(rets.begin(), rets.end()); rets.erase(unique(rets.begin(), rets.end()), rets.end()); for(int i = 0;i<n;i++){ cout << rets[i].size() << " "; for(int k = 0;k<rets[i].size();k++){ cout << rets[i][k] << " " ; } cout << endl; } } cout << endl; } return 0; }