はてなブックマークアプリ

サクサク読めて、
アプリ限定の機能も多数!

アプリで開く

はてなブックマーク

  • はてなブックマークって?
  • アプリ・拡張の紹介
  • ユーザー登録
  • ログイン
  • Hatena

はてなブックマーク

トップへ戻る

  • 総合
    • 人気
    • 新着
    • IT
    • 最新ガジェット
    • 自然科学
    • 経済・金融
    • おもしろ
    • マンガ
    • ゲーム
    • はてなブログ(総合)
  • 一般
    • 人気
    • 新着
    • 社会ニュース
    • 地域
    • 国際
    • 天気
    • グルメ
    • 映画・音楽
    • スポーツ
    • はてな匿名ダイアリー
  • 世の中
    • 人気
    • 新着
    • 新型コロナウイルス
    • 働き方
    • 生き方
    • 地域
    • 医療・ヘルス
    • 教育
    • はてな匿名ダイアリー
  • 政治と経済
    • 人気
    • 新着
    • 政治
    • 経済・金融
    • 企業
    • 仕事・就職
    • マーケット
    • 国際
    • はてなブログ(政治と経済)
  • 暮らし
    • 人気
    • 新着
    • カルチャー・ライフスタイル
    • ファッション
    • 運動・エクササイズ
    • 結婚・子育て
    • 住まい
    • グルメ
    • お金
    • はてなブログ(暮らし)
    • 掃除・整理整頓
    • 雑貨
    • 買ってよかったもの
    • 旅行
    • アウトドア
    • 趣味
  • 学び
    • 人気
    • 新着
    • 人文科学
    • 社会科学
    • 自然科学
    • 語学
    • ビジネス・経営学
    • デザイン
    • 法律
    • 本・書評
    • 将棋・囲碁
    • はてなブログ(学び)
  • テクノロジー
    • 人気
    • 新着
    • IT
    • セキュリティ技術
    • はてなブログ(テクノロジー)
    • AI・機械学習
    • プログラミング
    • エンジニア
    • Advent Calendar
  • おもしろ
    • 人気
    • 新着
    • まとめ
    • ネタ
    • おもしろ
    • これはすごい
    • かわいい
    • 雑学
    • 癒やし
  • エンタメ
    • 人気
    • 新着
    • スポーツ
    • 映画
    • 音楽
    • アイドル
    • 芸能
    • お笑い
    • サッカー
    • 話題の動画
  • アニメとゲーム
    • 人気
    • 新着
    • マンガ
    • Webマンガ
    • ゲーム
    • 任天堂
    • PlayStation
    • アニメ
    • バーチャルYouTuber
    • オタクカルチャー
  • おすすめ

    マンガ大賞候補作は

『rsk0315.hatenablog.com』

  • 人気
  • 新着
  • すべて
  • log をつけずに解くのが好きな人向けの記事 - えびちゃんの日記

    4 users

    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})\) に対して、区間最小値 \

    • テクノロジー
    • 2022/10/16 08:25
    • mathematics
    • algorithm
    • 不必要に浮動小数点数を使うの怖い - えびちゃんの日記

      3 users

      rsk0315.hatenablog.com

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

      • テクノロジー
      • 2022/06/05 12:39
      • プログラミング
      • できるだけ嘘を書かずに計算量やオーダーの説明をしようとした記事 - えびちゃんの日記

        782 users

        rsk0315.hatenablog.com

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

        • テクノロジー
        • 2021/10/14 00:39
        • アルゴリズム
        • あとで読む
        • 数学
        • プログラミング
        • algorithm
        • programming
        • 計算量
        • 情報科学
        • エンジニア
        • 開発
        • bitset 高速化が定数倍高速化という風潮に対するお気持ち表明 - えびちゃんの日記

          4 users

          rsk0315.hatenablog.com

          「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 や

          • 世の中
          • 2021/06/08 13:31
          • α(n) とお近づきになりたい人のための記事 - えびちゃんの日記

            3 users

            rsk0315.hatenablog.com

            union-find の計算量解析で出てくる \(\alpha(n)\) というのがありますね。 Ackermann 関数の逆関数として知られるやつです。 競プロ er の多くは、次のような認識をしていると思います。 計算量に \(\alpha(n)\) が出てくるなら union-find が関係する以外ないと思っている*1 なぜ union-find でそうなるかはよく知らない どういう解析で \(\alpha(n)\) が出てくるのかわからない \(\alpha(n)\) がどんな性質を持っているかもあまり知らない 実質定数だと思っている 最近、少しお勉強する機会があったので、紹介してみます。 えびちゃんもまだちゃんと仲よしになったわけではないです*2。 \(\star\) 演算子の導入 唐突ですが、\(\star\) 演算子というのを導入します。 関数 \(f(n)\) に対して、

            • 世の中
            • 2021/03/30 16:11
            • ACL の math の解説をするよ - えびちゃんの日記

              7 users

              rsk0315.hatenablog.com

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

              • 学び
              • 2021/01/18 21:48
              • Math
              • アルゴリズム
              • HotEntry
              • algorithm
              • あとで読む
              • 競プロ C++ イディオム FAQ - えびちゃんの日記

                4 users

                rsk0315.hatenablog.com

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

                • 学び
                • 2020/05/10 09:29
                • C++
                • 競プロで踏みがちな C++ の罠 - えびちゃんの日記

                  7 users

                  rsk0315.hatenablog.com

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

                  • テクノロジー
                  • 2019/12/17 05:25
                  • C++
                  • programming
                  • std::lower_bound の罠について - えびちゃんの日記

                    3 users

                    rsk0315.hatenablog.com

                    どうやら罠らしいので書きます. 冷静に考えると、初心者の人はなんで 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)\) だ

                    • テクノロジー
                    • 2019/09/16 09:33
                    • C++
                    • 未定義動作は未定義動作だよという話 - えびちゃんの日記

                      24 users

                      rsk0315.hatenablog.com

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

                      • テクノロジー
                      • 2019/09/10 21:42
                      • C++
                      • あとで読む
                      • programming

                      このページはまだ
                      ブックマークされていません

                      このページを最初にブックマークしてみませんか?

                      『rsk0315.hatenablog.com』の新着エントリーを見る

                      キーボードショートカット一覧

                      j次のブックマーク

                      k前のブックマーク

                      lあとで読む

                      eコメント一覧を開く

                      oページを開く

                      はてなブックマーク

                      • 総合
                      • 一般
                      • 世の中
                      • 政治と経済
                      • 暮らし
                      • 学び
                      • テクノロジー
                      • エンタメ
                      • アニメとゲーム
                      • おもしろ
                      • アプリ・拡張機能
                      • 開発ブログ
                      • ヘルプ
                      • お問い合わせ

                      公式Twitter

                      • 公式アカウント
                      • ホットエントリー

                      はてなのサービス

                      • はてなブログ
                      • はてなブログPro
                      • 人力検索はてな
                      • はてなブログ タグ
                      • はてなニュース
                      • App Storeからダウンロード
                      • Google Playで手に入れよう
                      Copyright © 2005-2023 Hatena. All Rights Reserved.
                      設定を変更しましたx