torus711 のアレ

主に競技プログラミングの問題について書きます

特集

浮動小数点数の誤差に怯えながらも比較をしたい場合がある話

はじめに 最近出題された某問題の影響で,浮動小数点数の誤差について注目が集まっています.さて,あの問題では入力を受け取っただけ・乗算しただけで誤差が出るという話でしたが,幾何問題など,更に比較などの演算も行いたい場合があります.しかしながら…

競技プログラマでも $O$-notation についてもうちょっとちゃんと考えたかった話

はじめに アルゴリズムの計算量を表現するツールとして,$O$-notation というのは競技プログラミングの文脈でもよく出てきます.その一方で,$O$-notation の導入が「ふわっ」と行われるケースはかなり多く,厳密に定義して導入する場面というのが実は少ない…

Digit DP 入門

はじめに 動的計画法のパターンの一つで,「Digit DP」とか「桁 DP」と呼ばれているものがあります.問題によって異なってくる部分もありますが,問題によらず共通している部分がかなりあるので,その部分を中心に解説してみたいと思います. Digit DP とは…

今すぐ使える C++ コーディングテクニック集

前置き これは、Competitive Programming Advent Calendar Div2013, 第 5 日の記事です。 記事の内容はタイトルの通り、アルゴリズムではなくコーディング自体に関するテクニック集です。(おそらく)競技プログラミング界隈ではこういった知識についてのま…

Windows で競技プログラミングしよう

内容が古いか,時代遅れになっている可能性があります. 例えば当時のわたしは,MSYS2 の存在を知りません. この記事について [twitter:@Tomoki_Imai] さんの 競技プログラミング入門 へのゆるふわ寄稿です。 Windows 環境で競技プログラミングをするために…