O(sqrt(N))のアルゴリズム - cos65535の日記
これはCompetitive Programming Advent Calendar Div2012に投稿された記事です。 さて、みたいな数値を見ると、は無理だからかとか、もしくはだとと思ってしまう人は多いでしょう。ですが、まで行かなくてももう少し悪い計算量が想定解の場合もあります。というわけで、今回はだとかという、ルートが入ったあまり見ない計算量のアルゴリズムを紹介します。 等差数列の和 となるようなyを見つける問題はO(1)で解けますが、Nになるまで愚直に足していけばで解けます。こんなもんどこで使うんだと思う人もいるかもしれませんが、手計算が面倒な場合とか証明したい場合に使います。 素数判定 素数判定はまでの数値で試し割りすることによって判定できます。もちろんミラーラビン法などを使えばもっと高速に判定できますが*1手軽に使えるというメリットがあります。 floorの分割 みたいな式があ
Critical Issues at Exascale for Algorithm and Software Design
The document discusses critical issues for algorithms and software at exascale, including the need for communication-avoiding and synchronization-reducing algorithms to address the dramatically increased concurrency and costs of data movement. It provides examples of how algorithms like QR factorization can be parallelized using dynamic scheduling of task graphs to reduce synchronization. Mixed pr
［SQEXOC 2012］FFXIVで使われているAI技術〜敵NPCはどうやって経路を探索しているのか？
［SQEXOC 2012］FFXIVで使われているAI技術〜敵NPCはどうやって経路を探索しているのか？ ライター：米田 聡 スクウェア・エニックスが2012年11月23日と24日の両日開催した「スクウェア・エニックス オープンカンファレンス」の最後には「AIセッション」が用意されていた。AIセッションは前半と後半に分かれ，前半は「ファイナルファンタジーXIV: 新生エオルゼア」（以下，新生FFXIV）における経路探索の実装に関する実践的な解説，後半はゲームAIの第一人者とも評される三宅陽一郎氏による，Luminous Studio用AIエンジンのやや概念的な話という構成だった。本稿では，まず前半の，より実践的なセッションから紹介してみたい。 テーマは，「MMORPGでマップ上を移動する敵NPCの経路をどう決めるのか」である。複雑で広いマップを有するMMORPGでは，移動する経路を賢く選択
へ、変態っ！！読めないからやめてっ！bit使ったデータ構造・アルゴリズム実装集 - Negative/Positive Thinking
この記事はCompetitive Programming Advent Calendar Div2012の2日目の記事です。 12月20日追記： Darseinさんが20日目の記事で、ビット演算についての詳しい説明を紹介してくださっています！必読ですね！！！！：） はじめに Y＾´ ∨／／ ／,∠ ,. ' ／l／／／ ／, ' , '／ ! ｜ ｌ }´ 〈 〉 変 〈/ , ' ／／￣｀>< ／／／ ／／／ _,.=‐|'"´l ｌ〈 変 / 〈 態. ∨, '／l| ,.'-‐､｀/／｀7/ ／''"´__ ｜ ﾊ l丿 態 { 人） ! ! （／! |ヽ〈_ ・.ﾉ〃 〃 ／ '／⌒ヾ.! ,' !く ! ! （_ ト､__／ ヽ､_,.イ ／ｌ ｌ ｜:::::::｀｀`/:::::／...´..
HALOBET: Situs Judi Online Terdepan, Slot Gacor & Slot88 Terbaik, Login Mudah!
Pemeliharaan Terjadwal: AllBet pada 23-Jun-2025 dari 06:00:00 sampai 10:30:00. Selama waktu ini, AllBet permainan tidak akan tersedia. Kami memohon maaf atas ketidaknyamanan yang mungkin ditimbulkan. Pemeliharaan Terjadwal: PPVIRTUALGAMES pada 13-Oct-2023 dari 18:00:00 sampai 01-Jan-2026 00:00:00. Selama waktu ini, PPVIRTUALGAMES permainan tidak akan tersedia. Kami memohon maaf atas ketidaknyamana
Re永続データ構造が分からない人のためのスライド
Competitive Programming Advent Calendar 2012の12/01担当分の記事です。
Topcoder
Topcoder is a crowdsourcing marketplace that connects businesses with hard-to-find expertise. The Topcoder Community includes more than one million of the world’s top designers, developers, data scientists, and algorithmists. Global enterprises and startups alike use Topcoder to accelerate innovation, solve challenging problems, and tap into specialized skills on demand.
指数時間アルゴリズム入門
2. 自己紹介 TopCoder: ◎wata TCO2010Marathon優勝など Twitter: @wata_orz 東京大学情報理工学系研究科コンピュータ科学専攻 理論計算機科学 (アルゴリズムの理論的な解析とか) プログラミングコンテスト チャレンジブック 2 3. 本日の内容 NP困難問題を解くためのアルゴリズムを扱います 𝑂𝑃𝑇 𝐼 ≤ 𝐴 𝐼 ≤ 𝑐𝑂𝑃𝑇(𝐼) 近似アルゴリズム ヒューリスティック 𝑓 𝑘 𝑝 𝑛 FPT アルゴリズム max 𝑐𝑥|𝐴𝑥 ≤ 𝑏, 𝑥: 整数} { 𝑂∗ 𝑐 𝑛 整数計画 厳密指数時間アルゴリズム 3 4. 効率的な指数時間アルゴリズム 何の指数？ 頂点数? 辺の数? それとも… • 2 𝐸 のアルゴリズムはまず役に立たないが，2 𝑉 のアル ゴリズムならコンテストでもよ
二分探索と三分探索 - komiyamの日記
ちょっと考えたことをまとめてみました。どちらのアルゴリズムも区間を扱うものですが、例によって私の好みで半開区間を主に扱います。 二分探索とは何か 自分なりにまとめると、「ある点を境界に真偽が入れ替わるとき、その境界を効率的に求めるアルゴリズム」だといえます。二分探索という単語は「単調性」や「最大/最小」というキーワードとともに語られることが多いように思いますし、実際問題それらが要求されることが非常に多いのですが実はそれらがなくても二分探索は成立します。 「ある点」というのが区間内に複数(あるいは0個)あっても適当に番兵を置けばどれか一つを検出できます(どれが検出されるかは分からないし、番兵が検出されるかもしれない！)。以下の図でいうと、黒い丸で囲んだ点のどれかを検出できます。もちろん、少し手を加えれば赤-青の境界のどれかを検出するようにすることもできます。 単調性というのは「ある点」が一つ
しゃくとり法 - komiyamの日記
私はしゃくとり法を書くのが苦手です。なので、しゃくとり法について自分なりに考えてみました。 しゃくとり法って結局何？ 二分探索は「ある点を基準に真偽が入れ替わるとき、その基準となる点を見つけるアルゴリズム」と説明できるし、座標圧縮は「何かの境界となり得ない座標を潰す技法」等と説明できます。 じゃあ、しゃくとり法は何かという答も持っているべきです。今の私なら「ある条件を満たす極小な区間を全て列挙するアルゴリズム」と答えます。 もう少し詳しく言葉にしてみます。 ある関数fは区間X=[l,r](開とか閉とか半開とかは適当)を受け取って真偽値を返します。例えば数列のある区間和がS以上になるかどうか、みたいな。この関数はある種の単調性というべき性質を持っている必要があります。つまりf([l,r])が真ならf([l-1,r])もf([l,r+1])も真だということです。また、f(空)=偽も要求します。
にぶたん
kinaba @kinaba にっきかいた。みんな二分探索どう書くの。http://t.co/qg7wvIbu ライブラリ化する際に引数と返値と関数名と引数名をどうするのという話としてもよいです。 2012-07-03 23:16:51
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
DPとかメモ化再帰とか - komiyamの日記
以下の内容は間違いを含んでる可能性が高い。 状態数が少ない問題ではDPやメモ化再帰による解法が結構あるけど、少し整理してみよう。 まず、大前提としてDPやメモ化再帰が使える必要条件はDAGになっていることだろう。ここで考えているグラフは、各状態を頂点、状態遷移を有向辺としたグラフである。確率とかの問題だと辺に遷移確率の重みがつくと考えれば良い。 特に、最小値を求める系の問題では必要十分と言ってもいいかもしれない(何か三角不等式っぽいのが成り立っていればいいような気がする。でも組み合わせの数を求める系だと上手く行かないのでやっぱり嘘か？)。 DPというのは、DAGに対してトポロジカル順序の小さい順に値を決定していくことに他ならない。 メモ化再帰というのは、もらうDPの特殊形式で余計な所を評価しないlazyなアルゴリズムと言えるかもしれない。 こうして書いてみると、DPの欠点が明らかになる。そ
DPの話 (追記) - aizuzia
前回の記事に対してみやむーさんから素晴らしい反響を頂いたので、こちらにレスポンスする形で追記してみます。 そもそも前回の「DPの話」は、こちらのエントリと内容が全く同じなのでした。全然気付いてなくてごめんなさい・・・。 ループのメリットとメモ再帰のメリット 「メモ再帰のメリットは計算が遅延的に行われること」とのことでした。メモ再帰では、「最終的に求めたい状態には絶対に遷移し得ないノード」への計算は行われません。そのようなノードが数多くある問題では、メモ再帰が速くなりうる。なるほど。 似たようなことがループでは絶対できないというわけではありません。配るDPにおいて、配る元のノードの値が初期値 (最短経路だったら inf とか、経路数だったら 0 とか) のままだったら、配っても意味が無いのでやめる。このような枝刈りを加えると、「初期状態から絶対遷移しないノードから」の計算は行われません。 が
DPの話 - aizuzia
この記事は Competitive Programming Advent Calendar のために作成されました。 「DP (Dynamic Programminng: 動的計画法) がよく分からない」というつぶやきをよく目にします。何から何まで分からないというわけではないけど、 「こういうDPをすれば解けるよ」と説明されれば理解できるけど、一からそれを思い付けない メモ再帰だと書けるけどループだと書けない、またはその逆 とかいう。 この記事は、DPという技法をより深く理解する手助けをすることを目的として書かれています。これを読めばどんなDPの問題もさくさく解ける・・・ことはないと思いますが、あんまり悩まずに実装できるようになるぐらいの効果はあるんじゃないかなと思います。想定する読者層は、簡単なDPの問題をいくつか解いたことがある、TopCoderレーティング 1500 未満ぐらいの人と
DPとかメモ化再帰とか(2) - komiyamの日記
Competitive Programming Advent Calendarでtayama0324さんが素晴らしい記事を書いておられました。なので自分もそれに触発されて、以前書いた記事の続きを書いてみました。以下はtayama0324さんの記事を読んでいることを前提に話をします。 DPのメリットとメモ化再帰のメリット 基本的にはtayama0324さんが触れているメリットでつきていると思うんですが、自分は次のようなメリットもあると考えています(本筋から離れるだけなので、tayama0324さんも知っていた上で敢えて書かなかっのだと思います)。 DPのメリット 配列の再利用でメモリが節約できることがある。 データ構造を工夫しての高速化が書きやすい。 メモ化再帰のメリット 評価が遅延的に行われる。 ひとつずつ説明します。 配列の再利用 これは非常によく知られていることだと思います。配列ではあ
DPの練習として良さそうなやつ - kyuridenamidaのチラ裏
いろいろなDPがありますが、これもまとめとくと良いと思ったので。僕はDPは得意ではないですが、それでもスキルアップに繋がったなあと感じた問題をピックアップしておきます。 DPかメモ化再帰か――ループの中で色々場合分けとかしなきゃいけなかったり、順序付けしにくかったりするＤＰは出来るならメモ化したほうがバグ減ったり実装楽だったりします。メモ化再帰は初期化ミスとかが無くて済むので。再帰が深くなりそうだったり、特殊なテクニック(ある区間をまとめて足したりする)とかする場合はやはりDPじゃないとだめですが、大体はメモ化再帰で代用が効きます。ではDP問の紹介。 (ネタバレ注意) 簡単な数え上げタイプ・Kannondou[☆]・A First Grader[★] 最長増加部分列タイプ( O(n log n)解法が存在するのでググったり蟻本とかを読むと良い。 )・ビルの飾りつけ(2007年度JOI春合宿
プログラミングコンテストでの乱択アルゴリズム
2013/1/9に統数研チャンネルにて、ウェーブレット木の解説をしました。岩波書店より出版されました「高速文字列解析の世界」の解説になっています。
MinHashによる高速な類似検索 - Preferred Networks Research & Development
年が明けてもう一ヶ月経ちましたね．岡野原です． 今日はMinHashと呼ばれる手法を紹介します．これは特徴ベクトルの高速な類似検索に利用することができます(クローラーの文脈だとShingleとして知られている）． 今や世の中のあらゆる種類のデータが，高次元のバイナリベクトルからなる特徴ベクトルで表されて処理されるようになってきました．例えば文書データであれば文書中に出現する単語やキーワードの出現情報を並べた単語空間ベクトル（Bag of Words）で表し，画像データも，SIFTをはじめとした局所特徴量を並べた特徴ベクトル（とそれをSkecth化したもの）として表せます．行動情報や時系列データも特徴量をうまく抽出する．グラフデータもFast subtree kernels[1]と呼ばれる方法で非常に効率的に特徴ベクトルに変換することができ，グラフの特徴をよく捉えることができるのが最近わかっ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Google Code Archive - Long-term storage for Google Code Project Hosting.