torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

特集

グリッド上で移動したり方向転換したりしたい話

はじめに 最近[いつ?],グリッド状の盤面の上で方向転換したくなる問題がしばしば出題されています*1*2.方向転換に限らず,グリッド上で 4 近傍に移動する ある方向を向いている状態から方向転換する より複雑な移動(後述で例示)をする などはしばしば見…

普段使っているテンプレを晒してみる

はじめに 本記事は競プロ Advent Calendar 2023,第 4 日目の記事として書かれました. 本記事では,わたしが普段競技プログラミングに取り組む際に使っているテンプレ (C++) の紹介をします.使用言語が Python や Rust や Haskell の方,すみません. 動機…

有理数 mod はこわくない

導入 最近(どれぐらい?)の AtCoder の問題で,「有理数を $\bmod$ で扱え」といった問題がしばしば出題されます*1.わたしは数学が苦手なのでこの手の問題は最初から諦めていたのですが,そろそろそういうことも言っていられなくなってきた気がするので,…

列挙問題と Reverse Search

はじめに 競技プログラマ的な視点で「列挙問題」について解説してみる,という記事です.競技プログラミング要素はこれだけです(ごめん).元々脈絡無く用意していた記事ですが,Competitive Programming (1) Advent Calendar 2020 の枠が変に空いていたの…

Weighted-Union Heuristic

はじめに 界隈で「データ構造をマージする一般的*1なテク」と呼ばれている技法があります.``Introduction to Algorithms'' [1] では Data Structure for Disjoint Sets の章で ``Weighted-Union Heuristic'' として挙げられています. hatena diary の終了…

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

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

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

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

Digit DP(桁 DP)入門

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

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

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

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

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