ちょっと考えたことをまとめてみました。どちらのアルゴリズムも区間を扱うものですが、例によって私の好みで半開区間を主に扱います。 二分探索とは何か 自分なりにまとめると、「ある点を境界に真偽が入れ替わるとき、その境界を効率的に求めるアルゴリズ…

OUPCのFour Arithmetic Operationsの解説にも書いていたけど、忘れないようにまとめておく。 A*B を mod M (M>2^31)の世界で計算したくなったとする。当然、A,Bともに大きな値となり、そのままA*B%Mを計算したらA*Bの部分でオーバーフローが起こりうる。 じ…

Competitive Programming Advent Calendarでtayama0324さんが素晴らしい記事を書いておられました。なので自分もそれに触発されて、以前書いた記事の続きを書いてみました。以下はtayama0324さんの記事を読んでいることを前提に話をします。 DPのメリットと…

はじめに この記事はCompetitive Programming Advent Calendar12月10日分の記事です。 誤差が原因でWAになる問題が嫌いな人は決して少なくないと思います。「こんなのは本質的なことではない」という人もいるでしょう。誤差を回避することが本質となるような…

主にC++でbool型を扱うときに注意することを覚えているうちに書いておく。 まず、当たり前のことから。 assert( sizeof(bool) == 1); bool hoge; assert( sizeof(hoge) == 1); const int N = 10; assert( sizeof(bool[N]) == N ); bool piyo[N]; assert( siz…

gccのビルトイン関数のひとつに、__builtin_constant_p(value)というものがある。コンパイル時にvalueが定数となっているときに1を返して、0を返す関数らしい。 例えば、 __builtin_constant_p(3); __builtin_constant_p(sin(2.0)); とかは-O0のときですら1…

以下の内容は間違いを含んでる可能性が高い。 状態数が少ない問題ではDPやメモ化再帰による解法が結構あるけど、少し整理してみよう。 まず、大前提としてDPやメモ化再帰が使える必要条件はDAGになっていることだろう。ここで考えているグラフは、各状態を頂…

プログラミングコンテストで、特に幾何の問題とか解いてると「EPS変えたら通った」みたいなことがよくある。僕のような自分に優しい人間は「まあ本質的な部分は合ってたんだしいいか」と考えてしまいがち。この態度を「甘い」ととる人もいればそうでない人も…

凸関数の最大値は精度良く求められるけど、最大値を与える値の精度はよくないというお話。 具体的な問題で考えてみよう。 関数f(x) = x*(1-x)の最大値と、最大値を与える値を誤差1e-9以下で計算しなさい。 もちろん高校数学の範囲で解けて、厳密解はx=0.5で…

最近eclipse使ってコーディングするようになったけど、自分の貧弱な計算機ではeclipse上でプログラムをコンパイル、実行するのは重くてやってられない。なのでコンパイル、実行は端末上でやることにした(何でIDE使ってるんだっけ)。以下のファイルに適当に名…

衝突の問題さえ回避すれば非常に優秀なデータ構造である。 弱点はメモリを大量に消費すること。メモリの局所化とは対極であること。for_eachみたいなことができない。STLにない(tr1とかextとか__gnu_cxxとかはさておき)等。 そもそもsetやmapと計算量がlog程…

大抵のプログラミングコンテストやオンラインジャッジではC/C++が選択できる。しかも大体gccである(もしくは、選べる)ことが多い。なので、gccで書くときに覚えておくと便利、かもしれないことを書いておく。そもそもgccのバージョンやコンパイルオプション…