LISの計算について - noshi91のメモ
LISは競プロでも低くない頻度で出現する題材です。 一般に知られている計算方法では単純な配列を用いてO(NlogN)でLISの計算が可能ですが、BITを用いることで同じ計算量でより直感的に(個人差あり)LISの計算が可能なのでそれについて少し書きます。 与えられた数列をAとします。 まずDP配列 B を用意し ・B_i ＝A_iを最後尾にしたLISの最大長さ と定義します。 すると ・B_i ＝max( {B_k | 0<=k<i, A_k<A_i } ) + 1 と計算することができます。これは2次元クエリなので一般にNlog^2N掛かってしまいますが、B_iを計算する順番を工夫することによってもっと簡単に高速化が可能です。 すなわちBを0で初期化し、Aの値が小さい順にB_iを計算していきます。すると、条件のうち(A_k<A_i)が不要になります。何故なら、現在見ている値より大きい値を持
暗号技術のすべて【PDF版】 | SEshop.com
本製品は電子書籍【PDF版】です。 ご購入いただいたPDFには、購入者のメールアドレス、および翔泳社独自の著作権情報が埋め込まれます。 PDFに埋め込まれるメールアドレスは、ご注文時にログインいただいたアドレスとなります。 Amazon Payでのお支払いの場合はAmazonアカウントのメールアドレスが埋め込まれます。 本製品を無断で複製、転載、譲渡、共有および販売を行った場合、法律により罰せられる可能性がございます。 ご購入の前に必ずPDF利用案内をお読みください。 本書はデータサイズが約264MBございます。モバイルデータ通信での環境下や、スマートフォン等でのご使用がいただけない場合がございます。お使いの機器の空き容量や通信環境をご確認の上ご購入ください。 『ハッカーの学校』の著者が徹底解説 暗号技術の絡み合いを解き明かす 【本書のポイント】 1）古典暗号から現代暗号までを体系的に解説
ABC129 Fにみるたのしいダブリング - 競プロをはじめた家事手伝いロボットのブログ
深夜テンション(カラータイルをTLで見かけて3時になってしまったので) ダブリングとは? 2倍する or 1足す を 回繰り返すだけで に到達できることを利用したもの全般 半分にする or 1引く を繰り返して を とかにする とみるほうが自然かも 例 : 繰り返し二乗法 auto pow = [](auto a, auto n){ auto ret = 1; while(n){ if(n & 1)ret *= a; // 1引く a *= a; // 半分にする n >>= 1; } return ret; } ABC129 F ネタバレです 桁数で場合分けをしたあとを考えましょう( 桁) 求めたいものは です。 ここで、 を1減らすのと半分にすることを考えます。上の繰り返し二乗法でしたように、最終的(ここではbase caseです 今回は まで等差数列を短くできたとき)に答えの入る変数
B-treeインデックス入門 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? B-treeがMySQLで使用されている背景から、B-treeインデックスの構造、そしてそれに基づいたインデックスの使用方法の入門編です。以下の流れに沿ってまとめていきます。 インデックスってなに？ B-treeってなんでインデックスに使われているの？ B-treeインデックスの構造 インデックスの使用方法 ※ 勉強をかねてまとめていることもあり、間違っている箇所がございましたら教えていただけると嬉しいです。 インデックスってなに？ 全体の内容の中から特定部分を探すために使用する、本の索引のような概念のことです。これを用いることで、検索
Rustでマラソンをするときに使えそうなスニペット達
はじめに Rustでマラソン形式の競技プログラミングコンテストに出場したときに何度か使ったコードを紹介します。 Rustで出場できるマラソンはあまりない印象ですが、参考になれば幸いです また、自分の記事ですがalgoの方に興味がある方は Rustで競技プログラミング スターターキット もしRustでのスニペット管理に興味ある方は Rustで競技プログラミングをするときの"スニペット管理"をまじめに考える(cargo-snippetの紹介) を御覧ください。 この記事で紹介しているスニペットはすべて、hatoo/competitive-rust-snippetsで管理しています。 PCG 2023/08/07 PCGのほうが好きになったのでPCGのセクションを足しました。 XorShiftのところは以前のまま置いておきます。 外部クレートは使えないので簡単にPCGで乱数生成器を用意します。
今日から使えないビット演算（CODE VS Reborn編） - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 0. はじめに この記事は，チームラボ・リクルートさんがスポンサーするCODE VS Reborn (https://codevs.jp/ ) に関する記事になります． CODE VS Rebornはぷよぷよとボンバーマンを合わせたようなゲームのAIを作るコンテストです． 1. ゲームのルール 今回のゲームは, CODE VS 2.0 のリメイク版であるCODE VS for STUDENTのリメイク版で, 対戦形式の落ちものパズルです．ルールの詳細は以下の PDF に記されています. https://static.codevs.jp/
トポロジカルソートと強連結成分分解でWikipediaの特定カテゴリー配下のページをすべて取得する - 終末 A.I.
Wikipediaの特定カテゴリー配下のページをすべて取得するためには、整理されていないグラフデータ特有のいくつかの問題に向き合う必要があります。 一つは、Category:カツラ科と糸井の大カツラのように、サブカテゴリーにはページへのリンクが含まれているが、カテゴリー本体にはページへのリンクが含まれていないケースがあるという問題。 もう一つは、Category:インフォグラム・エンターテインメントームソフトとCategory:アタリのゲームソフトのように、お互いがお互いのサブカテゴリーに含まれてしまっているケースがあるという問題です。 これらの問題は、以下の手順を踏むことで解決できます。 カテゴリーにリンクされているページだけでなく、サブカテゴリー内のリンクを順にたどって含まれるすべてのページを収集する ただし、一度たどったカテゴリーに再度到達した場合、それ以上はそのルートを探索しない
アルゴリズムとデータ構造から理解するRedis / Learn Redis from Internal Algorithms and Data Structures
2019年新卒研修で使った資料です。 内部実装の雰囲気を感じとりながら、Redisについて理解を深める研修を行いました。 以下の内容について学びました。 1. Redisの概要 2. 社内での利用方法 3. 正しい用法用量 Redis についての前提知識は必要としていません。…
二値文字列の転倒数が従う群構造 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 概要 二値文字列の転倒数が従う群構造を紹介します。これによって範囲転倒数クエリが、累積和やSegment Treeで計算できます。Segment Treeでできます、という言及は今までに見たことがありましたが、累積和もできるという話は聞いたことがなかったのでまとめます。 二値文字列の転倒数とは、0と1からなる二値文字列 $s$ が与えられて、$s$ をソートするために必要な隣り合った0と1のswap数 $f(s)$ のことです。例えば、$s=101011$ を $001111$ にソートするためには、 $3$ 回のswapが必要なので、
CodeChef GPD Gotham PD - kazuma8128’s blog
問題文 https://www.codechef.com/problems/GPD 問題概要 頂点数 N の根付き木が与えられる. 各頂点には正整数のキーが付いている. 以下の二種類の Q 個のクエリをオンラインで処理せよ. クエリ１：頂点 v の子に, キー k の付いた新しい頂点 u を増やす クエリ２：頂点 v から根までのパスに含まれる頂点に付いたキーの中で, k でXORしたときの最大の値と最小の値を求める 制約：1 ≤ N ≤ 10^5, 1 ≤ Q ≤ 2*10^5, 1 ≤ (各キー) ≤ 2^31-1 解法 まず, トライ木を使うと, 要素の挿入 (insert) , 要素の削除 (erase) , ある値でXORしたときの最大値/最小値の取得が O(ビット数) でできます. 詳しくは以下のページなどを参照 www.geeksforgeeks.org これを使って根からD
非負整数値を扱う Trie について - kazuma8128’s blog
はじめに 非負整数を二分木のトライ木で管理するアレに関する日本語記事があんまり無いっぽいので雑にメモ. （というかそもそも専用の呼び名ないのかな？） とりあえずここでは Binary Trie って呼んどきます. Binary Trie とは 整数をビット列とみなしてトライ木っぽく持つ set 的なことができるデータ構造です. 正確には要素の重複を許す multiset っぽく実装することが多そう. 整数集合を管理できますが, 平衡二分木よりも実装が楽なので最高です. こんな感じ ノードに書いてある数字は部分木に含まれる要素の個数です. できること ビット長を B とすると, 以下の操作が全て O(B) でできます. insert(x) : 値 x を集合に（一つ）追加 erase(x) : 値 x を集合から（一つ）削除 max_element/min_elemet() : 集合内の最大
ヤフーにおけるアルゴリズム教育の取り組み
ヤフー株式会社は、2023年10月1日にLINEヤフー株式会社になりました。LINEヤフー株式会社の新しいブログはこちらです。LINEヤフー Tech Blog こんにちは。サイエンス1本部の真鍋です。 私は博士後期課程を修了後、2016年の4月にヤフーに新卒入社し、約半年間の新卒研修を経て現在のチームに配属となりました。それ以来2年半ほど、キーワード検索エンジンの実装と、検索結果ランキングの改善に取り組んでいます。 より具体的には、ヤフーショッピングの商品検索に関わっています。検索結果ランキングは主に機械学習で生成されたモデルによっているのですが、このモデルに商品のどんな属性や、ユーザーの皆さんのどんな行動を入力したらいいかを考え、その実現に必要なコードを実装するのが主な仕事です。快適なサービスを提供するために計算コストを削減したり、これら全てのことがスムーズに進むように運用コストを削減
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
近似最近傍探索の最前線
Rubias19 porno gratis
GitHub - piroz95/CodeVSReborn
talks/2019/05/RustLT5/slides.md at master · togatoga/talks
next_permutationがイマイチよくわからなかったのでまとめてみた - Qiita
VP trees: A data structure for finding stuff fast
乱択アルゴリズム紹介(行列乗算の検査&多項式等価性の検査) - Preferred Networks Research & Development
数列の任意の範囲で大きいほうから任意の個数のsumをO(1)で求める（注：O(logワードサイズ)です） - 誤読