サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
マンガ大賞候補作は
rsk0315.hatenablog.com
\(\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})\) に対して、区間最小値 \
競プロにおいて、「何かしらの整数を大小比較して、左辺が大きければどうのこうの」みたいなことをしたい局面はそれなりにあります。 特に、境界付近でも正確に評価できる必要がある状況も多いです。 そうした状況で浮動小数点数を使うのはできるだけ避けたいですという気持ちがあります。 導入 まず、浮動小数点数は誤差が出ます*1。 初心者のうちは「浮動小数点数では \(1\div 10\) を正確には計算できない」と聞いても、「たとえば assert_eq!(1.0 / 10.0, 0.1); とかはエラーにならないし、問題なく計算できているのでは?」みたいな誤解をすることもあります。 実際には、0.1 と書いた部分も計算前の時点で 0.1000000000000000055511151231257827021181583404541015625 のような値になっており、所望の状態にはなっていません。 1
計算量についてのお話です。対象は、プログラミング経験はあるが計算量のことを知らない初心者から、計算量のことを知っているつもりになっている中級者くらいです。 数式を見たくない人にとっては読むのが大変かもですが、深呼吸しつつ落ちついて読んでくれるとうれしいです。 それから、この記事が自分には合わないな〜と思ったときは、(別の記事を Qiita とかで検索するよりも)この記事の一番下の 参考文献 にある本を読むことをおすすめします。Amazon の試し読みで無料で読めます*1。 TL; DR 関数の増加度合いのことをオーダーと呼ぶよ 計算量は、入力サイズ(など)を受け取ってアルゴリズムの計算回数(など)を返す関数だよ その関数のオーダーについての議論がよく行われるよ オーダーを上から抑えるときは \(O\)、下から抑えるときは \(\Omega\) を使うよ オーダーを上下両方から抑えたいときは
「bitset で 64 倍高速化できます」「64 は定数なのでオーダーは変わりません」のような説明は、競プロ界隈でたびたび見かけます。 59 日目の解説です。std::bitset などを使った高速化テクニックは過去に AGC にも出題されたことがある重要事項ですので、理解しておくようにしましょう。 なお、X[i] < Y[i] の制約がなくても本問題を解くことができます。 #競プロ典型90問 pic.twitter.com/zpIVYdc5VL— E869120@本発売 (@e869120) 2021年6月6日 AGC の解説 とかも。 「定数倍高速化を軽視する風潮に対するお気持ち表明」や「競プロのような入力に上限がある場合でもオーダーを信仰する風潮に対するお気持ち表明」などは、一旦おいておきます。 今回のメインは、「長さ \(n\) の bit 列の bitwise AND/OR や
union-find の計算量解析で出てくる \(\alpha(n)\) というのがありますね。 Ackermann 関数の逆関数として知られるやつです。 競プロ er の多くは、次のような認識をしていると思います。 計算量に \(\alpha(n)\) が出てくるなら union-find が関係する以外ないと思っている*1 なぜ union-find でそうなるかはよく知らない どういう解析で \(\alpha(n)\) が出てくるのかわからない \(\alpha(n)\) がどんな性質を持っているかもあまり知らない 実質定数だと思っている 最近、少しお勉強する機会があったので、紹介してみます。 えびちゃんもまだちゃんと仲よしになったわけではないです*2。 \(\star\) 演算子の導入 唐突ですが、\(\star\) 演算子というのを導入します。 関数 \(f(n)\) に対して、
ACL (AtCoder Library) の内部実装を知りたい人向けの記事です。 お友だちに「ねーね、ACL のこの関数ってどういう仕組みなの? 知ってたりしない?」と聞かれたとき、「え... なんかほら、わかんないけど、魔法で動くからいいんだよ」としか言えないと情けない気がしません? しました。なので書きます。 こういうシチュエーションはなくても、何かを実装したいときに「あ、これ ACL の実装のやつと同じ発想じゃん」となることはありえるので、知っていて損はないかなと思います。 めちゃくちゃ長くなったので、一度に全部読むのには適さないかもしれません。 数式部分の LaTeX コードなども含めて数えられていますが、26000 文字を超えています。 全体像 個別の説明 internal::safe_mod internal::barrett Barrett reduction の話 正当性
今までいろんな人に何回も説明した内容は、これからも何回も説明することになりそうなので、記事としてまとめておいてみます。 自分としてもこの記事へのリンクを貼ればよい上、読んだ人が(辞書で隣の単語もまとめて覚えるみたいな感じで)別のことも知れたらよさそうだと思ったので。 「これはこう書けるよ」系の紹介をするのではなく、「このおまじないがわかりません」系の解説をしたいと思っています。 わからないことがあれば、#助けて競プロer のタグでツイートするか、PROCON-QA で質問するといいと思います。 よく見る質問については追記しようと思います。直接えびちゃんにリプライしてくれてもいいです。 以下では std:: をつけて表記しますが、using namespace std; などをしている人は、(ここで紹介されたイディオムを書く際に)省略して構いません。 たとえば、std::cin を cin
定型文 この記事は 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が発生するとは限らないです.「なんかうまくいく」とか「必ず実行時エラーになる」とかは保証されていません. 「未定義動作が起きます」という文より,「こういうコードを書いた場合の動作は定義されていません」という文の方が実態に即している気がします. 気づきにくい要因として,コンパイラが以下のような動作をすることが仕様で許されているというのがあります. 未定義動作は起こらないと仮定してよい 起こらないのだから,無視して最適化してよい 無視して最適化された結果として「なんかいい感じに動く」ということはありますが,当然常にうまくいくわけではありません. 甘えるのはやめましょう. ある環境でたまたま動いたコードが別の環境で動かなかったときに「環境依存のコード」と言
このページを最初にブックマークしてみませんか?
『rsk0315.hatenablog.com』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く