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)が不要になります。何故なら、現在見ている値より大きい値を持
M.Hiroi's Home Page
WHAT'S NEW 2025/04/05 Memorandum (数学編) の CSS を変更 CONTENTS Common Lisp Programming お気楽 Common Lisp プログラミング入門 Common Lisp 入門 : 番外編、お気楽 CLOS プログラミング入門 お気楽 ISLisp プログラミング超入門 xyzzy Lisp Programming Common Lisp 入門 C# Programming お気楽 C# プログラミング超入門 お気楽 F# プログラミング超入門 Functional Programming お気楽 Standard ML of New Jersey 入門 お気楽 OCaml プログラミング入門 お気楽 Scheme プログラミング入門 お気楽 Erlang プログラミング入門 お気楽 Haskell プログラミング入門 G
暗号技術のすべて【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インデックスの構造 インデックスの使用方法 ※ 勉強をかねてまとめていることもあり、間違っている箇所がございましたら教えていただけると嬉しいです。 インデックスってなに？ 全体の内容の中から特定部分を探すために使用する、本の索引のような概念のことです。これを用いることで、検索
CODE VS Reborn - y_kawanoのブログ
2019/4/15～2019/5/10にあったゲームAIコンテスト。ぷよぷよみたいな落ち物パズルゲー。 決勝の様子(が見れる予定)：https://live.nicovideo.jp/gate/lv320076507 予選3位/112人・決勝◯位でした。 参加人数は少ないですが参加面子を考えると日本最高峰のゲームAIコンテストだったでしょう。 ルール（適当説明） 基本ぷよぷよですが、4つ揃えるんじゃなくて数字の和を10に揃えたらブロックが消えるみたいなルールです。 連鎖すると敵の盤面にお邪魔ブロックを降らせます。相殺もぷよぷよと同じ仕様です。 ぷよぷよと大きく違うのはスキルがある点です。ブロックを消すとスキルゲージが溜まって、溜まると数字の5を爆発させて連鎖したときと同じように攻撃ができます。 アルゴリズム概要 目標連鎖数を決めてchokudaiサーチで探索して、発火が近くなったら色々考え
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:アタリのゲームソフトのように、お互いがお互いのサブカテゴリーに含まれてしまっているケースがあるという問題です。 これらの問題は、以下の手順を踏むことで解決できます。 カテゴリーにリンクされているページだけでなく、サブカテゴリー内のリンクを順にたどって含まれるすべてのページを収集する ただし、一度たどったカテゴリーに再度到達した場合、それ以上はそのルートを探索しない
こんなプログラムはいやだ: 負の剰余 - bkブログ
こんなプログラムはいやだ: 負の剰余 知人から次の式の計算結果はどうなるかという問題を出されました。 -3 % 5 3 % -5 -3 % -5 降参して答えを尋ねたところ、問題を出した方も答えを知らないことがわかりました。そこで、いくつかの言語処理系で結果を調べてみました。手元の環境 (Intel Xeon 上の Debian GNU/Linux sarge) で調べると2つのグループに分かれました。 C (GCC 3.3.5) Java (Sun JDK 1.5.0_05) PHP 4.3.10-16 Emacs 22.0.50.2 Ruby 1.8.2 Python 2.3.5 Perl 5.8.4
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
共立出版 アリがと蟻 on Twitter: "本書は、力学的な「運動解析」ではなく、コンピュータによる「計算処理」の観点から、3次元回転に関する話題を提供します。また本書では、最適化の数値探索法として「リー代数の方法」を定式化します。恐らくこのような内容の専門書は、我が国では… https://t.co/NUkfN1Pv6P"
やねうら王 on Twitter: "先日、やねうら王ブログの有益な記事をカテゴリー別にまとめた見出しを作ろうと思い、10時間以上費やして全記事を読み返したのだが、これもしかして本を2,3冊書ける程度の分量があるのではなかろうか…。 その10時間以上費やして作成した… https://t.co/s2q3iGYaR9"
Rubias19 porno gratis
GitHub - kera6rhy/codevs_reborn
GitHub - piroz95/CodeVSReborn
talks/2019/05/RustLT5/slides.md at master · togatoga/talks
じゃがりきん on Twitter: "～迷路を簡単に解くアルゴリズム～ https://t.co/PLJq5SwWif"
next_permutationがイマイチよくわからなかったのでまとめてみた - Qiita
VP trees: A data structure for finding stuff fast
untitled