はてなブックマーク

競プロ er はよく計算量の見積もりをします。「これこれの計算量は $O(\dots)$ なので十分高速である」といった具合で上から抑えることが多いです。 また、「これこれの計算量は $\Omega(\dots)$ なので TLE しそう」といった具合で下から抑えることもしばしばあります。 note:「これこれの計算量は $O(2^{2^n})$ なので TLE しそう」といった記号の使い方（$O$ で下から抑えようとする）は、不正確な用法なので気をつけましょう。知らずに使っていた人はちゃんと勉強しましょう。 「下から抑える」について 下から抑えるというのは、見積もりたい値はこれ以上であるという値（下界かかい と呼ばれます）を求めるという意味の言い回しです。 ある $a$ を使って $a\le x$ と書けたら「$x$ は $a$ で下から抑えられる」と言います。 逆に、$x\le b$

先日、下記の記事でナップサック問題の DP を愚直に眺めました。 rsk0315.hatenablog.com 今回は、ナップサック問題に限らず様々な DP を愚直に眺める回です。 「○○（何らかの集合）の最大値」のように計算せず、○○の部分について考えていきます。 もちろん DP をする際に○○をそのまま持つと空間計算量がめちゃくちゃになる（ことに伴って時間計算量もめちゃくちゃになる）のですが、典型 DP で暗に構築されている集合を考えておくことで、そうした構造を持つ DP を考える際に理解がスムーズになる気がします。 「何々を全パターン考慮したい」となったときに「こういう漸化式を考えればよいはず」とできるレパートリーが増えそうです。 想定読者は競プロをしていて DP を学び中・苦戦中〜ある程度知っている人で、ある程度数式を読める人です。数式が苦手な人は、数式が得意な人に助けてもらうなど

動的計画法 (dynamic programming, DP) はイメージ・メンタルモデルを掴むまでのハードルが中々高いような気がします。 一例を示しますが、必ずしも全部の問題を一貫して説明できるとは限らないので、いくつかのイメージを持っているといいかもしれません（どれかしらに固執する必要はないということ）。 数式がそれなりに出てきますが、苦手な人は深呼吸とかしながら落ちついて読んでもらえるとうれしいです。 数式に関して補足 Python 風な擬似コードで軽く説明しておきます。 $$\sum_{x\in S} f(x)$$ これは、下記の関数の返り値と同じものを表していると思ってください。$\sum$ はシグマ (sigma) と読みます。 def sigma(S, f): res = 0 for x in S: res += f(x) return res 慣れている人は sum(map

導入 rsk0315.hatenablog.com こういう話はある*1んですが、最初からバグらせやすい書き方をしておいて「バグが出たー」と言われてもそれはそうとなってしまうので、そういうのを控えるくらいのことはするべきだと思います。 書き方が悪いせいで「十分に複雑なコード」になってしまっているものもあります（もちろん概念自体が複雑なものを実装するときは複雑になって当然ですが）。 「控えるべき書き方」とか「書くときに気をつけるべきこと」とかを紹介します。 あくまで自分の主観であって、読み手の人の方針に反するのであれば強制する気はないです。「こういう書き方もあるよー」くらいに捉えてください。 導入 紹介 控えたいこと フラグ変数を乱用しない デバッグは標準エラー出力に書く 出力パートは一箇所にまとめる 計算パートと入出力パートは分ける いくつかの具体例だけで考察を終わらせない 書きながら気を

\(\Theta(n \polylog(n))\) 時間で解くのは簡単だけど、実際には \(\Theta(n)\) 時間で解けるよーという問題はちょくちょくあります。 競プロ界隈では log を削ることに意欲的な人は一部だけな気がします*1が、話として知っておいても損はあまりない気がするので、挙げてみます。 ここではざっくり紹介するに留め、詳細は各自調べてもらうようなスタンスになっています。 紹介 RMQ 中央値 篩による素数判定 過半数 行最小値 接尾辞配列 最深共通祖先 Decremental neighbor query Level ancestor SWAG Gray code の利用 ±1 配列の転倒数 周期検出 周期検出 2 その他メモ おわり 紹介 RMQ 長さ \(n\) の配列 \(a = (a_0, a_1, \dots, a_{n-1})\) に対して、区間最小値 \

言語さんサイドにも問題があるというのはそうかも。 とはいえ、理解が足りないまま「わかりにくい」と言っている人はかわいそうなので、解説をします。 名前について なんで「x 以上の最小値を得る関数」が lower_bound と呼ばれているのかわからん*1 まず、それを得る関数ではないです。イディオムとしてそう覚えてしまっているような人が多いため、こうなってしまう人が多い気はします。 実際には値ではなくイテレータを返すもので、「x と等価 (equivalent) な値がある区間の下限の位置」が返ってきます。ここでの equivalent というのは == とは違う概念なのですが、とりあえず（int のような型では）== と同一視してよいので、詳細は後述とします。 また、upper_bound についても同様で、「x より大きい最小値を得る関数」ではなく、「x と等価な値がある区間の上限の位置

競プロにおいて、「何かしらの整数を大小比較して、左辺が大きければどうのこうの」みたいなことをしたい局面はそれなりにあります。 特に、境界付近でも正確に評価できる必要がある状況も多いです。 そうした状況で浮動小数点数を使うのはできるだけ避けたいですという気持ちがあります。 導入 まず、浮動小数点数は誤差が出ます*1。 初心者のうちは「浮動小数点数では \(1\div 10\) を正確には計算できない」と聞いても、「たとえば assert_eq!(1.0 / 10.0, 0.1); とかはエラーにならないし、問題なく計算できているのでは？」みたいな誤解をすることもあります。 実際には、0.1 と書いた部分も計算前の時点で 0.1000000000000000055511151231257827021181583404541015625 のような値になっており、所望の状態にはなっていません。 1

計算量についてのお話です。対象は、プログラミング経験はあるが計算量のことを知らない初心者から、計算量のことを知っているつもりになっている中級者くらいです。 数式を見たくない人にとっては読むのが大変かもですが、深呼吸しつつ落ちついて読んでくれるとうれしいです。 それから、この記事が自分には合わないな〜と思ったときは、（別の記事を Qiita とかで検索するよりも）この記事の一番下の 参考文献 にある本を読むことをおすすめします。Amazon の試し読みで無料で読めます*1。 TL; DR 関数の増加度合いのことをオーダーと呼ぶよ 計算量は、入力サイズ（など）を受け取ってアルゴリズムの計算回数（など）を返す関数だよ その関数のオーダーについての議論がよく行われるよ オーダーを上から抑えるときは \(O\)、下から抑えるときは \(\Omega\) を使うよ オーダーを上下両方から抑えたいときは

ACL (AtCoder Library) の内部実装を知りたい人向けの記事です。 お友だちに「ねーね、ACL のこの関数ってどういう仕組みなの？ 知ってたりしない？」と聞かれたとき、「え... なんかほら、わかんないけど、魔法で動くからいいんだよ」としか言えないと情けない気がしません？ しました。なので書きます。 こういうシチュエーションはなくても、何かを実装したいときに「あ、これ ACL の実装のやつと同じ発想じゃん」となることはありえるので、知っていて損はないかなと思います。 めちゃくちゃ長くなったので、一度に全部読むのには適さないかもしれません。 数式部分の LaTeX コードなども含めて数えられていますが、26000 文字を超えています。 全体像 個別の説明 internal::safe_mod internal::barrett Barrett reduction の話 正当性

今までいろんな人に何回も説明した内容は、これからも何回も説明することになりそうなので、記事としてまとめておいてみます。 自分としてもこの記事へのリンクを貼ればよい上、読んだ人が（辞書で隣の単語もまとめて覚えるみたいな感じで）別のことも知れたらよさそうだと思ったので。 「これはこう書けるよ」系の紹介をするのではなく、「このおまじないがわかりません」系の解説をしたいと思っています。 わからないことがあれば、#助けて競プロer のタグでツイートする か、PROCON-QA で質問する （サイト閉鎖しちゃったね）といいと思います。 よく見る質問については追記しようと思います。直接えびちゃんにリプライしてくれてもいいです。 以下では std:: をつけて表記しますが、using namespace std; などをしている人は、（ここで紹介されたイディオムを書く際に）省略して構いません。 たとえば、

定型文 この記事は Competitive Programming (1) Advent Calendar 2019 の 17 日目の記事です． adventar.org まえがき えー，未定義動作という言葉を知っていますか？ 必要に応じて 昔の記事 を読むといいかもしれません． C++ を書く上でよく「環境依存」という言葉を聞くかと思いますが，これは C++ 用語ではなく，俗語です． それが使われる文脈での適切な用語は「処理系定義」「未規定」「未定義」などです（状況に応じてどれかが選ばれます）． 基本的に，未定義な動作になるコードを書いた場合，どうなるかがわからなくてつらいんですが，今回はそういう話には触れない予定です． 競技プログラミングの上では，（特にコンテスト中なら）未定義であってもジャッジでうまく動いて AC すれば丸く収まるためです． （もちろん，次に同じようなコードを書いてう

どうやら罠らしいので書きます． 冷静に考えると、初心者の人はなんで set は要素の有無の判定が高速なのか、どのくらい高速か、などはわかってないはずで、そうなると、std::lower_bound で求めようとするとどうしてだめなのかがわからなくて当然という気がしてきたかも— えびちゃん (@rsk0315_h4x) 2019年9月9日 ざっくりはこのリプライツリーにあるんですが，より丁寧めに書いてみようと思います． このツリーだけで理解できる人は読まなくてもいい記事かもしれません． 罠 以下のコードの最悪計算量の見積もりを正しくできますか？ std::lower_bound(s.begin(), s.end(), x); ただし，s, x の型は以下であって，s の要素数は \(n\) とします． std::set<int> s; int x; 答え合わせ \(O(\log n)\) だ

人々は未定義動作に多くを期待しがちではという気持ちがあるので書きます． まず「これこれは未定義動作です」と言ったとき，目に見えるやばいこと*1が発生するとは限らないです．「なんかうまくいく」とか「必ず実行時エラーになる」とかは保証されていません． 「未定義動作が起きます」という文より，「こういうコードを書いた場合の動作は定義されていません」という文の方が実態に即している気がします． 気づきにくい要因として，コンパイラが以下のような動作をすることが仕様で許されているというのがあります． 未定義動作は起こらないと仮定してよい 起こらないのだから，無視して最適化してよい 無視して最適化された結果として「なんかいい感じに動く」ということはありますが，当然常にうまくいくわけではありません． 甘えるのはやめましょう． ある環境でたまたま動いたコードが別の環境で動かなかったときに「環境依存のコード」と言