Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-05-07

[][] Yandex.Algorithm 2011 Qualification 2 02:42 はてなブックマーク -  Yandex.Algorithm 2011 Qualification 2 - 練習帳

問題一覧:Dashboard - Yandex.Algorithm 2011: Qualification 2 - Codeforces

結果:Standings - Yandex.Algorithm 2011: Qualification 2 - Codeforces

=.ABCDE
--0:100:50---
580+1/-0480-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;
}