プログラミングコンテストプチテクニック(g++)

僕が知ってると楽だと思うもの。C++(g++)使ってる人向け。

いろいろなのごちゃごちゃまぜまぜしてます。

大きい配列

グローバル配列として宣言しないと謎のセグフォします。

ローカル変数で確保すると、[1000][1000]でもうセグフォしちゃったりするので注意。

(JOI予選・本選共にそれで苦しんだ人が少なくなかったようです。)

配列を多めに確保しよう

少し余分に取ることで残念バグとかで死にません。

切り上げ

<cmath>ヘッダのceil()関数を使ってもよいが、

A/Bを切り上げたい時、「(A+B-1)/B」で切り上げられる。

ビットを数える

__builtin_popcount(n)

もうわざわざ実装する必要はありません!

最大公約数・最小公倍数求める

#include <algorithm>ヘッダの__gcd(a,b)を使うと良いです。

a,bの最小公倍数はa/__gcd(a,b)*bとかでやると算術オーバーフローしなくてグッドです。

素数・約数

2≦i≦(int)√nまでで割り切れなければ素数です。だから素数判定はO(√n)で出来ます。

約数についても、nがiで割り切れるということはiはnの約数です。が同様にn/iも約数ですから、約数列挙もO(√n)で出来ます。

実数の二分探索

定数回回しましょう。whileでEPSとかつかうと不思議な力で死ぬことになる。(謎のTLEとか)

(参考:実数探索三種類解説 - nodchipの日記)

スペース区切りの文字列分割

stringstream知ってると知ってないとでは雲泥の差です。自分でパーサとか書くと死ねます。

詳細はググってください。

あと「1,2,3」とかでも、事前に','を' 'に置換しておくことによってパースできます。

ある値の要素番号を取得する。

find(v.begin(),v.end(),検索する値)-v.begin()

とかで0-indexedの要素番号が取り出せます。恐れずに使いましょう。(注:候補が複数ある場合はより先頭のものが帰ってきますし、候補が見つからなかったら悲惨です。

ある値を配列から削除する。

v.erase(remove(v.begin(),v.end(),削除する値),v.end());

で消せます。複数削除対象がある場合は全部消えます。

配列にユニークな番号が振られるヨセフスのお芋シミュレート解法とかで特に役立ちます。

setで一番大きい値を取り出す。

*s.rbegin()

long long (03/26 23:33追加)

溢れそうかなとか思ったら迷わずlong longとか使うと良いです。

longじゃなくてlong longなところがミソです。

scanf("%lld",&n)とかで取ったりしますが、環境によって違います。

稀にlong long使ったことによりTLEとか耳にしますけど、滅多にそういう問題出会わないと思うのでやっぱり恐かったらlong longしましょう。

size_tにまつわる罠 (03/26 23:33追加)

STLの大体のコンテナに.size()っていうメンバ変数がありますが、

これsize_tっていう中身unsigned intな型ものです。

だから、

max( (int)a,v.size() ) // (第一引数と第二引数が違う型だと警告される。)

とかやると、コンパイラが怒ります。

その際は

max<int>( (int)a , v.size() ) //これならok

とかしましょう。型を指定してやりましょう。


もう一つ、

for(int i=0;i<v.size()-1;i++)

とかやってると、コンテナのサイズが0の時にv.size()-1が非常に大きい値になって停止せずに配列外参照とかガリガリしてくれて死にます。よくやらかすので十分に注意しましょう。(unsignedに暗黙キャストされるのが原因)

思いついたら追加するかも。