練習帳

■ [実践][Codeforces] Yandex.Algorithm 2011 Qualification 2 02:42

問題一覧：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;
}

ツイートする