はてなブックマーク

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

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

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