Competitive Programming Advent Calendar Div2012の12月4日分の記事です。私はこの1年でいくつかのプログラミングコンテストに主催者寄りの立場で関わって来ました。具体的には、 OUPC HBPC SuperCon Autumn Fest JAG主催のコンテストのいくつか などです。…

コンテストのときに使ったりしているライブラリやらスクリプトの一部をgithubに置くことにした。 ライブラリはドキュメントの扱いを決めかねているのでしばらく放置。スクリプトまわりは、今使っているビジュアライザをもうちょっと改良してから上げる予定。…

問題概要 n( 解法 ソースコード中に書いたコメントの焼き直し。 minStr[i] = {digits[0:i]の順序を入れ替えて作ることのできる最小の文字} geq[i][j] = {digits[0:i]の順序を入れ替えて作ることのできるlowerBound[j:j+i]以上の文字で最小のもの} ge[i][j] =…

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

確率や期待値のDPで式を立てたとき、連立一次方程式 Ax = b を解きたくなることはよくあります。競技プログラミングで使うようなものに限っていくつかメモしておきます。 クラメルの公式 行列式を計算することで厳密解を求めます。nが小さい(2や3)ときに式を…

やっと念願かなってTopCoder Algorithm部門で赤コーダーになれた。以前にも書いたようにこの部門が花形だという意識が自分の中にあったのでとても嬉しい。僕はICPC組やJOI組と違ってTopCoderから競技プログラミング始めた人間なので、レーティングの変遷を見…

難易度見積りを完全に読み間違えてご迷惑をおかけしました。問題はAizu Online Judgeの2350~2361に収録されているので解いてもらえると嬉しいです。 ジャッジデータはここでダウンロードできます。不備が見つかった場合は指摘していただけると助かります。 …

競技プログラミング歴2年目 2年経ってまだ黄コーダー…。周囲のレベルが上がっていることは確実(自分がSRMに出始めたときはDPやsetの存在すら知らなかったけどeasy解くだけで黄まですぐいけた)なんだけど、やっぱり赤くなりたい。いやMarathonとかは開始1年で…

日本だとSpaghetti Sourceが超有名。もちろん他にも探せばいくつかある。 TopCoderのAlgorithm Tutorialsも基本的なのは大体網羅されている。いくつかは和訳されている。 CodeForcesの各参加者が書いているブログも結構面白い。最近読んだのはparadin8さんの…

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になっていることだろう。ここで考えているグラフは、各状態を頂…

やっぱり花形のalgorithmで赤くなりたい。

プログラミングコンテストで、特に幾何の問題とか解いてると「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のバージョンやコンパイルオプション…

アルゴリズムまわり 拡張ダイクストラ(そもそも意味が分かっていない。普通のダイクストラと何が違うんだろう)。 素数関連。具体的にはミラーラビンとポラードロー。できれば離散対数も。 幾何全般のライブラリの組み直し。平面幾何はcomplexで、立体幾何はs…

TopCoder 主にアルゴリズム部門に参加しています。部門名の通り正しいアルゴリズムを思いつけば実装は軽めのものが多く、また定数最適化もそんなに必死にやらなくて済むあたりが非常に好みです。チャレンジとかレーティングとかのシステムはゲーム感覚で楽し…