Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2010-01-12

[][][][] SRM168 07:05 はてなブックマーク -  SRM168 - 練習帳

・SRM164は迷宮入りしたため一度放置

234.61/250

#include <cstring>
#include <vector>
#include <iostream>

using namespace std;

class NumberGuesser{
public:
int guess(string leftOver){
  int n=0;
  for(int i=0;i<3;i++){
    n+=leftOver[i]-'0';
  }
  return 9-n%9;	
}
};

・適当に数字を入れ替えた2つの数について差をとれば必ず9の倍数になる。

2010-01-08

[][][][] SRM165 07:47 はてなブックマーク -  SRM165 - 練習帳

132.50/250

・そのままだとi*(i-1)がオーバーフローを起こす

→下のコードだとmax_calcを用いてiの動く範囲を制限してiが大きくなりすぎないようにしているが、iはlong long int型にしたほうが良い。

→top coderをやっていて初めてオーバーフローを考慮しないといけない設計に出くわした


#include <string>
#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

class ParallelSpeedup{
public:

int numProcessors(int k, int overhead){
	int min_temp=k;		
	unsigned int work=0;
	int ans=1;

	int max_calc=(int)( pow ( (double)2*k/overhead, ( (double)1/3) ) +1);

	if(k>2){
	for(int i=1;i<max_calc;i++){</pp>
		work=i*(i-1)*overhead/2+(int)ceil( ( ( double ) k )/i);
		if(min_temp > work){
			min_temp=work;
			ans=i;
		}		
	}
	}
	return ans;
}
};

2010-01-03

[] 2進数表示したときの1の数を数えるアルゴリズム 09:49 はてなブックマーク -  2進数表示したときの1の数を数えるアルゴリズム - 練習帳

Miminoさんのソース

int ones(int n){
	int res=0;
	while(n){n-=-n&n;++res;}
	return res;
}

・-n&nで、nを2進数表現したとき、下の位から数えて最初にある1のみが残り他が0になる。それをnから引けば一番位の小さい1を0に出来る。

pieguyさんのソース

int card(int a){
	if(a==) return 0;
	return (a&1)+card(a>>1);
}

・再帰は直感的な感じがせず、うまく使えない。

・x/=2とx>>1ではどっちが速い?

[] 15 Exercises for Learning a new Programming Language 09:00 はてなブックマーク -  15 Exercises for Learning a new Programming Language - 練習帳

http://www.freelancingjob.com/articles/article_description.php?art_id=96

[][][][] SRM166 08:30 はてなブックマーク -  SRM166 - 練習帳

・タイムは諦めてベクタやソートを使う練習と割り切る

→大小関係の作成のためにわざわざ新しくベクタ(binary_order)を作る必要はない、sortの多重定義で第3引数に大小判定に用いる関数を指定するものがある。

・大小判定のif文の使い方がひどい

90.62/250

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;
	struct binary_order{
		int num;
		binary_order(int n) : num(n){};
	};

	int binary(int n){
		int ans=0;
		while(n>1){
			if(n%2){ans++;}
			n=n/2;
		}
		ans+=n;
		return ans;
	}


	bool operator<(const binary_order &x, const binary_order &y){
		if(binary(x.num)<binary(y.num)){</pp>
			return 1;
		}else if(binary(x.num)==binary(y.num) && x.num< y.num ){
			return 1;
		}else{
			return 0;
		}
	}

class BinaryCardinality{
public:
vector <int> arrange(vector <int> numbers){
	vector<int> ans;
	int len=numbers.size();
	
	vector<binary_order> v;
	binary_order* p=NULL;
	for(int i=0;i<len;i++){</pp>
		p=new binary_order(numbers[i]);
		v.push_back(*p);
	}
	
	sort(v.begin(),v.end());
	
	for(int i=0;i<len;i++){</pp>
		ans.push_back(v[i].num);
	}
	return ans;


}
};

2010-01-02

[][][][] SRM167 08:19 はてなブックマーク -  SRM167 - 練習帳

新年一発目

170.03/250

#include <vector>
#include <string>

using namespace std;

class Animation{
public:

vector <string> animate(int speed, string init){
	vector<string> ans;
	ans.clear();
	int len=init.length();
	int const max_time = 1+(len+1/speed);
	string buffer;
	buffer.clear();
	
	for(int i=0;i<max_time+1;i++){</pp>
		buffer.clear();
		
		for(int j=0;j<len;j++){</pp>
			if((j-speed*i>=0&&init[j-speed*i]=='R') ||  (j+speed*i<len &&init[j+speed*i]=='L') ){</pp>
				buffer.push_back('X');
			}else{
				buffer.push_back('.');				
			}
		}
		ans.push_back(buffer);	
		const string empty(len,'.');
		if(buffer==empty){
			break;
		}
	}
	return ans;
}
};

直感で問題を選んだら番号がかなり飛んでしまった。

エラーがまったくでなかったのは初めてかもしれない