はてなブックマーク

Competitive Programming Advent Calendar Div2013の12月2日の分です。 ときどき脱線しながらも主にsegment treeの再帰展開について書こうと思います。 はじめに segment treeの資料といえば蟻本やiwiさんのスライドが非常に分かりやすくお勧めです（定番中の定番ですね）。この資料で使われている図をイメージしながら読んでください。同じくiwiさんの平衡二分探索木のスライドもぜひ目を通しておきましょう。 これら以外にもsegment treeについてまとめたブログ記事などは検索すれば色々引っかかります。去年や今年のAdvent Calendarでも初学者向けの記事があるようです。初学者向けの詳しい解説はそちらをご覧ください。 私なりにsegment treeの動作原理を短くまとめると、「区間をたかだかO(log n)個の交わらない区

Competitive Programming Advent Calendar Div2012の12月4日分の記事です。 私はこの1年でいくつかのプログラミングコンテストに主催者寄りの立場で関わって来ました。具体的には、 OUPC HBPC SuperCon Autumn Fest JAG主催のコンテストのいくつか などです。今回はコンテストを開催する側としての個人的な経験を中心に書こうと思います。ただしSuperConは色々特殊なので除きます。またOUPCについては既に書いているのでそれとは重ならないようなことを書きます。最初はどうやってコンテストを開くか具体的なマニュアルを作るつもりで書く気でいたのですが、挫折しました。最近はコンテスト開催経験者も増えていますし、文字通りプロであるAtCoderという会社もあるので詳しい手順が知りたい方はその辺りを当たってみるとよいと思います。記事全体

私はしゃくとり法を書くのが苦手です。なので、しゃくとり法について自分なりに考えてみました。 しゃくとり法って結局何？ 二分探索は「ある点を基準に真偽が入れ替わるとき、その基準となる点を見つけるアルゴリズム」と説明できるし、座標圧縮は「何かの境界となり得ない座標を潰す技法」等と説明できます。 じゃあ、しゃくとり法は何かという答も持っているべきです。今の私なら「ある条件を満たす極小な区間を全て列挙するアルゴリズム」と答えます。 もう少し詳しく言葉にしてみます。 ある関数fは区間X=[l,r](開とか閉とか半開とかは適当)を受け取って真偽値を返します。例えば数列のある区間和がS以上になるかどうか、みたいな。この関数はある種の単調性というべき性質を持っている必要があります。つまりf([l,r])が真ならf([l-1,r])もf([l,r+1])も真だということです。また、f(空)=偽も要求します。

やっと念願かなってTopCoder Algorithm部門で赤コーダーになれた。以前にも書いたようにこの部門が花形だという意識が自分の中にあったのでとても嬉しい。僕はICPC組やJOI組と違ってTopCoderから競技プログラミング始めた人間なので、レーティングの変遷を見ると色々思うところがある。いい機会なのでこの辺でちょっと振り返っておきたい。 開始3ヶ月くらい そもそも初回にいきなりDiv 1に上がれたのが意外だった。一応過去問は何回かやっていたけど、当時はC++覚えたばっかりだったし、STLの使い方も殆どわからず動的計画法なんて名前すら知らなかった。開始3回で黄まで行っているけどあれは運がよかっただけ。 このとき黄コーダーになっていたから当時殆ど存在を知らなかったICPCにいもす先生とhasi君に誘えてもらえたので、やはり自分は運がよかったのだと思う。 開始3ヶ月~開始1年6ヶ月 こ

Competitive Programming Advent Calendarでtayama0324さんが素晴らしい記事を書いておられました。なので自分もそれに触発されて、以前書いた記事の続きを書いてみました。以下はtayama0324さんの記事を読んでいることを前提に話をします。 DPのメリットとメモ化再帰のメリット 基本的にはtayama0324さんが触れているメリットでつきていると思うんですが、自分は次のようなメリットもあると考えています(本筋から離れるだけなので、tayama0324さんも知っていた上で敢えて書かなかっのだと思います)。 DPのメリット 配列の再利用でメモリが節約できることがある。 データ構造を工夫しての高速化が書きやすい。 メモ化再帰のメリット 評価が遅延的に行われる。 ひとつずつ説明します。 配列の再利用 これは非常によく知られていることだと思います。配列ではあ

はじめに この記事はCompetitive Programming Advent Calendar12月10日分の記事です。 誤差が原因でWAになる問題が嫌いな人は決して少なくないと思います。「こんなのは本質的なことではない」という人もいるでしょう。誤差を回避することが本質となるような問題がコンテストに出てもきっと人気は出ないでしょう。自分も以前は誤差死の起きうる問題は嫌いでしたが、最近はそれを回避するのも面白さだと感じるになってきました。 しかし面白いとかつまらないとか好きとか嫌いとか以前に非ACは悔しいものです。なので今回は、誤差死などを回避するために地味なネタである浮動小数点数について書こうと思います。 A+B problem とりあえず、いろんなオンラインジャッジで最初の1問目として見ることの多いA+B problemを解いてみましょう。よくあるのは整数の和を出力させる問題ですが、

以下の内容は間違いを含んでる可能性が高い。 状態数が少ない問題ではDPやメモ化再帰による解法が結構あるけど、少し整理してみよう。 まず、大前提としてDPやメモ化再帰が使える必要条件はDAGになっていることだろう。ここで考えているグラフは、各状態を頂点、状態遷移を有向辺としたグラフである。確率とかの問題だと辺に遷移確率の重みがつくと考えれば良い。 特に、最小値を求める系の問題では必要十分と言ってもいいかもしれない(何か三角不等式っぽいのが成り立っていればいいような気がする。でも組み合わせの数を求める系だと上手く行かないのでやっぱり嘘か？)。 DPというのは、DAGに対してトポロジカル順序の小さい順に値を決定していくことに他ならない。 メモ化再帰というのは、もらうDPの特殊形式で余計な所を評価しないlazyなアルゴリズムと言えるかもしれない。 こうして書いてみると、DPの欠点が明らかになる。そ

プログラミングコンテストで、特に幾何の問題とか解いてると「EPS変えたら通った」みたいなことがよくある。僕のような自分に優しい人間は「まあ本質的な部分は合ってたんだしいいか」と考えてしまいがち。この態度を「甘い」ととる人もいればそうでない人もいるだろう（妥協すべきラインというのはどこかに存在するので）。 ロバストな計算幾何というのは研究分野が存在するくらいなので、本質的に難しいものだと思われる。でも、最低限これくらいは知っといたほうがいいんじゃないの、というのはあると思うので思考をメモしておく。タイトルに（１）とついてるのは後から追加するかもしれない、という意味。 浮動小数点数（IEEE 754）の仕様とかは色々調べるのが面倒なので後で書く。TopCoderの問題では非正規化数のせいでTLEとか出たし、知っておいて損はないと思う。最低限持っておく知識としては、仮数部が52ビットなので、一回

凸関数の最大値は精度良く求められるけど、最大値を与える値の精度はよくないというお話。 具体的な問題で考えてみよう。 関数f(x) = x*(1-x)の最大値と、最大値を与える値を誤差1e-9以下で計算しなさい。 もちろん高校数学の範囲で解けて、厳密解はx=0.5で最大値0.25をとる。 これを三分探索で解いてみよう。 const double EPS = 1e-10; double f(double x){ return x*(1.0-x); } int main(){ double low = 0.0, high = 1.0; while(high - low > EPS){ double width = high - low, ml = low + width/3.0, mr = low + 2.0*width/3.0; if(f(ml) >= f(mr)){ high = mr; }

Competitive Programming Advent Calendar 2014の記事です。 自分はかつてTopCoder Marathon Matchに参加していた時期があったのですが、今回はその感想を書きます。 続きを読む Competitive Programming Advent Calendar Div2013の12月2日の分です。 ときどき脱線しながらも主にsegment treeの再帰展開について書こうと思います。 はじめに segment treeの資料といえば蟻本やiwiさんのスライドが非常に分かりやすくお勧めです（定番中の定番ですね）。この資料で使われている図をイメージしながら読んでください。同じくiwiさんの平衡二分探索木のスライドもぜひ目を通しておきましょう。 これら以外にもsegment treeについてまとめたブログ記事などは検索すれば色々引っかかります

概要 過去の事を思い出しながら経過を書き起こしてみる。 序盤 問題を読んでみる。大きな要素は経路、商品の個数、値段の3つ。 どう考えても一番大きな要素は経路。 まずはpositive scoreが出るようなモノを作ってみる。スコアは2くらい。 とりあえず個数や値段はかなり適当に決めて、経路の探索を頑張ってみる。 各ステップごとに経路を修正するのはstringを扱う関係上時間がかかりそうなので、最初に良い経路を探して決め打ちする。 前処理で、各セルに一番近い家と距離を求めておく。 一番近い家がまだ訪ねていなければその家を目指し、既に訪ねていれば離れるようにする。 離れる方向の選び方は色々あるので若干の乱択性を加える。 多スタート法で10回くらい探索するとスコアは10くらい。 商品の個数の選び方を変える。10日間で売上が負なら個数を必ず減らし、完売していたら割と高い確率で個数を増やす。 探索回