5. Tips¶

5.1. オーバーフローに注意¶

次のコードはyukicoder No.51の解答例である。

\(1 \leq W \leq 10^5, 1 \leq D \leq 10^5\)¶

#include <iostream>

int main()
{
	int W; std::cin >> W;
	int D; std::cin >> D;
	for(int i=0; i<D-1; i++)
	{
		W -= W/((D-i)*(D-i));
	}
	std::cout << W << std::endl;
	return 0;
}

このコードはオーバーフローすることがある。

((D-i)*(D-i))

は全てint型から成るので、この一時的な結果はint型として保存される。しかし、この計算結果は最悪の場合int型の範囲を越えるためオーバーフローする場合がある。

オーバーフローさせないためにはDまたはiをlong long型にすればよい。

もう面倒くさいときは次のマクロ使っちゃえ(笑)

#define int long long

5.2. 小数点切り上げ¶

小数点切り上げにceil関数を使うと誤差が問題になることがある。

次のようなコードを用いれば安全である。

a/b + (a%b==0 ? 0 : 1);

5.3. std::string¶

5.3.1. 文字列検索¶

findメソッドは頭から一致する文字列を検索する。戻り値はstd::string::size_typeで、整数型へのキャストも可能だが、std::string::nposとの比較の際に問題がでうるらしいので面倒くさがらずにsize_type型で受け取るようにすること。

std::string::size_type index =  str.find("abc");
if(index == std::string::npos) std::cout << "not find";

rfindは後ろから検索する。

std::string::size_type index =  str.rfind("abc");

5.3.2. 文字検索¶

文字検索にはfind_first_of、find_last_ofを使う。前者は頭から、後者は後ろから一致する文字を検索する。

std::string::size_type index =  str.find_first_of("abc");
std::string::size_type index2 =  str.find_last_of("abc");

これは’a’または’b’又は’c’に一致する最初の位置を返す。

5.3.3. tokenによる文字列分割¶

std::vector<std::string> split(const std::string &str, char sep)
{
	std::vector<std::string> ret;
	std::stringstream ss(str);
	std::string buf;
	while( std::getline(ss, buf, sep) ) 
	{
		ret.push_back(buf);
	}
	return ret;
}

5.3.4. 文字列挿入¶

std::string str("abc");
str.insert(2, "d");//添字2の要素の前に挿入

5.4. unsigned intの桁数取得¶

unsigned int digit(unsigned int n)
{
	return (n==0 ? 1 : (int)log10(n)+1);
}

5.5. std::vector¶

5.5.1. 特定の値を削除する¶

erase-removeイディオムと呼ばれる方法が使える。

v.erase(std::remove(v.begin(),v.end(),100), v.end());//100に一致する要素を削除する。

std::removeは要素の削除を行わない。指定した値に一致する要素をコンテナの末尾に移動してその先頭iteratorを返すだけである。std::vector::eraseは指定した範囲を実際に削除する。このため上述のコードは所望の動作をする。

5.6. 自作ライブラリ¶

あると便利かな、と思うメソッドを作ってみた。バグあるかもなので注意。

5.6.1. vector中の各要素の数え上げ¶

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

template <class F> std::vector<std::pair<F, int> > count_elements(const std::vector<F> &V)
{
	std::vector<std::pair<F, int> > ret;
	std::vector<F> v = V;
	std::sort(v.begin(), v.end());

	F f0 = v[0];
	int count = 0;
	for(const auto &x: v)
	{
		if(f0==x)
		{
			count++;
		}
		else
		{
			ret.push_back(std::pair<F,int>(f0,count));
			f0 = x;
			count = 1;
		}
	}
	ret.push_back(std::pair<F,int>(f0,count));

	return ret;
}

int main()
{
	std::vector<int> v(5);
	v[0] = 0;
	v[1] = 10;
	v[2] = 0;
	v[3] = 10;
	v[4] = 1;
	auto count = count_elements(v);
	for(auto &x: count) std::cout << x.first << "(" << x.second << " ";
	
	return 0;
}

戻り値はstd::vector<std::pair<F, int> >でfirstに一致する要素がsecond個あることを表す。