競プロのアルゴリズム関連略称まとめ - noshi91のメモ
随時募集しています 略称 正称 APSP All Pairs Shortest Path BB Branch and bound BBST Balanced Binary Search Tree BFS Breadth First Search BIT Binary Indexed Tree BM Berlekamp-Massey BM Boyer-Moore BSGS Baby-Step Giant-Step CHT Convex Hull Trick CRT Chinese Remainder Theorem D&C Divide and Conquer DAG Directed Acyclic Graph DEPQ Double-ended priority queue DFS Depth First Search DP Dynamic Programming DST Disjoin
高校生がアルゴリズムとスパコンの力で、京都の碁盤目状道路を13.9%効率化した話 - Qiita
2. 本研究で解く問題 「いざ研究しよう！」と思っても、条件や設定を決めないと何も始まりません。 まずは研究を分かりやすくするために、「一つの問題」に落とし込むことにしました。 問題設定 縦 $N$ 行・横 $N$ 列の大きさの碁盤の目があります。隣り合う交差点間の距離は 1 です。つまり、交差点が合計で $N^2$ 個あり、それぞれ座標 $(1, 1), (1, 2), ..., (1, N),$ $(2, 1), (2, 2), ..., (N, N-1), (N, N)$ に位置すると考えることもできます。 下の図は、$N = 4$ の場合の交差点の位置です。 あなたは、碁盤の目の交差点の位置は変えずに、道路の並びのみを変えることができます。上手く道路の並びを変えることで、できるだけ「便利」な道路網を建設してください。 「便利な道路網」って何？ 私は、以下の 2 つの条件を満たす道路
ロックフリーアルゴリズムによるFIFOバッファ - Qiita
はじめに 私が組み込みプログラミングを始めたころ(まだインターネットもなく組み込みマイコンもAKI-80とかZ80系主流で遊んでいた時代)に大学の先輩に教えてもらったテクニックです。今どきのCPU向けではないですが、私自身が古典的かつ重要な要素が含まれており、組み込みプログラミングに引き込まれたきっかけの一つでもありますので、当時を思い出しつつ記事にしてみます。 「ロックフリーなアルゴリズム」についてはこちらのWikipediaの記事がわかりやすいです。 これらのアルゴリズムは、割り込み禁止やミューテックスなどのロックを用いずに、割り込みハンドラやマルチタスク／マルチスレッドなどの異なる非同期な実行コンテキスト間で情報を渡すことを目的としており、今回はその応用内でのFIFOバッファの構成例となります。 近年ではArduinoなどの組み込みプログラミングも手軽に行える環境が増えています。また
メモリモデル？なにそれ？おいしいの？ - yohhoyの日記（別館）
この記事はC++ Advent Calendar 2014の21日目にエントリしています。 内容はC++メモリモデルと逐次一貫性についての概説記事となっています。 flickr / nomadic_lass もくじ 忙しい人のための「C++メモリモデル」 C++メモリモデル一問一答 ソフトウェアからみた「C++メモリモデル」 “メモリ”という共有リソース C++ソースコードが実行されるまで メモリの一貫性と整合性 逐次一貫性モデル is Easy ハードウェアからみた「C++メモリモデル」 ハードウェア・メモリ一貫性モデル C++コンパイラの責任と自由 強いメモリモデル vs. 弱いメモリモデル 逐次一貫性モデル is Hard （本文のみ約9600字） まえがき When your hammer is C++, everything begins to look like a thumb
ロックフリーアルゴリズムについて理解する - 逐次一貫性 - 高速日記
逐次一貫性(sequential consitency)とは何か 最初に逐次一貫性の概念についてまず理解しよう 逐次一貫性はコンピュータシステムに関するメモリ一貫性モデルの一つであり、定義をWikipediaから引用すると「どのような実行結果も、すべてのプロセッサがある順序で逐次的に実行した結果と等しく、かつ、個々のプロセッサの処理順序がプログラムで指定された通りであること」とのことだ。 何のことだかよくわからんが、並列処理中の実行結果が常に逐次的に実行した場合と同等となる、ということのようだ。 例えば下記のようなコードがあるとして std::atomic<int> X(0), Y(0); int r1, r2; void thread1() { X.store(1); r1 = Y.load(); } void thread2() { Y.store(1); r2 = X.load();
プログラミングスキル判定サービス「TOPSIC」を通じてアルゴリズムを学ぶ～立教池袋中学校・高等学校 数理研究部の挑戦
プログラミングコンテストで数々の実績をもつ同校がなぜTOPSICを始めるに至ったのか。その背景からアルゴリズムの重要性まで、数理研究部顧問の内田芳宏教諭、TOPSICを運営するシステムインテグレータ代表取締役社長の梅田弘之氏、TOPSICの問題作成を手掛けるAtCoder代表取締役社長の高橋直大氏に話を伺った。 左からシステムインテグレータ梅田弘之氏、立教池袋中学校・高等学校 内田芳宏教諭、AtCoder高橋直大氏 設立47年の実績ある数理研究部 東京・池袋の立教大学の並びに建つ立教池袋中学校・高等学校は、立教大学をはじめとした有名大学への進学率も高く、中高一貫の名門校として人気を誇っている。クラブ活動の豊富さも特徴で、中でも1971年に設立された数理研究部は、歴史と伝統のある部活動の一つだ。 「数理研究部が始まった1970年代はまだ高等学校は設立されていなかったため、中学校しかありません
スライド最大（最小）値・ヒストグラム内最大長方形問題を俯瞰する - Qiita
はじめに 長さ$N$の配列が与えられて，愚直に計算すると$\mathcal{O}(N^2)$かかってしまうところを，デック(deque)やスタックを用いてうまく計算することで$\mathcal{O}(N)$に改善することができる有名問題に次の2つがあります． 配列内の長さ$K ( \leq N)$の区間すべてに対して，その区間内の最大(最小)値を求める （スライド最大(最小)値） $N$個の幅$1$，高さ$H_i$（$0 \leq i < N$)の長方形をこの順に並べてできるヒストグラムに含まれる長方形の面積の最大値を求める (ヒストグラム内最大長方形問題) この記事ではこの2つのアルゴリズムのポイントと類似点を自分なりの視点で解説します． 1. スライド最大（最小）値 解きたい問題は次のような問題です． 配列内の長さ$K$の区間すべてに対して，その区間内の最大(最小)値を求める 愚直な解
Umepon on Twitter: "今日のスライド資料です． 「組合せ最適化による問題解決の実践的なアプローチ」 https://t.co/d84vOyD9Xg #opt_night"
今日のスライド資料です． 「組合せ最適化による問題解決の実践的なアプローチ」 https://t.co/d84vOyD9Xg #opt_night
厳選！C++ アルゴリズム実装に使える 25 の STL 機能【前編】 - Qiita
それほど C++ が、競プロやアルゴリズムの学習に人気であるのには、以下のような理由があるのです。 計算速度が 1 秒あたり $10^{8} ～ 10^{9}$ 回程度と、他のプログラミング言語に比べ高速だから。 基礎的文法の習得がそれほど難しくないから。 しかし、C++ の利点はこれだけではありません。元々用意されている標準ライブラリがあるのです。一方、標準ライブラリは C++ を学ぶ大きな障壁となるものの一つです。C++ を学ぶ上で標準ライブラリが上手く使えず挫折したという人も多いと思います。そこで本記事では、 競技プログラミングやアルゴリズムの実装に使える 25 個の C++ 標準ライブラリと、それらの各種アルゴリズム実装への応用例 を解説したいと思います！！！！！ 本記事を読んだら何ができるのか？ 前編(本記事) と後編を読み、この記事でリストアップされた 25 個の C++ 標準
のいみ on Twitter: "300回言ってるけど x^-1 = (MOD % x) ^ -1 * (- MOD / x) 、マジで天才"
300回言ってるけど x^-1 = (MOD % x) ^ -1 * (- MOD / x) 、マジで天才
数学オリンピックの問題にプログラミングで挑戦！ ～数え上げから幾何問題まで～ - Qiita
1. はじめに はじめまして！高校 2 年生の square1001 です。 私は主に「競技プログラミング」に取り組んでいます。情報オリンピックの世界大会の日本代表になったり、TopCoder や AtCoder などのプログラミングコンテストにも出場したりしています。コンテストに出場するだけでなく、問題の作成も積極的にやっています。 ところで、みなさんは、「日本数学オリンピック」という大会を知っていますか？これは、日本全国の高校生以下を対象にした、数学の問題解決能力を競う、全国的にとても有名な大会です。本記事では、日本数学オリンピックの予選で出題される問題を、難しい数学的知識や数学的考察を使わずに、「コンピューターの高い計算能力」と「アルゴリズムの力」でチャレンジしてみます！ 導入 - コンピューターが世界を変えた！ プログラミングを実務などでやっている方の中には、「システムやアプリケー
最短経路問題総特集！！！～BFSから拡張ダイクストラまで～ - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 基本的アルゴリズム（幅優先探索など）から応用（経路復元、拡張ダイクストラなど）まで、最短経路問題に関するアルゴリズムを総特集しました。 基本的なグラフ理論の用語については、次を参考にしてください。 グラフ理論 用語集 queueなどのデータ構造の用語については、次のスライドの後半を参考にしてください。 C++ STL講習会 by @e869120 最短経路問題とは 一般的に、次のような問題とされます。 $V$ 頂点と $E$ 辺からなるグラフが与えられる。頂点 $u$ と 頂点 $v$ を結ぶパスのうち、重みの総和が最も小さいものはどれ
Z-algorithm詳解と具体例 - Senの競技プログラミング備忘録
新ABCになって、6問制になってから、2020/1/6現在まで、Z-algorithmは二回(500, 600)出題されてます。これからも継続して出そうな「文字列照合」で強力なツールとなるZ-algorithmですが、既存資料たちは非常によく説明されていますが、どこか筆足らずのような印象を受けました。 そこで、この記事でZ-algorithmに絞った説明、実際の挙動の説明、実装例を紹介します。 以下のページ、PDFを参考にしてます。 snuke.hatenablog.com 文字列アルゴリズム from HCPC: 北海道大学競技プログラミングサークル www.slideshare.net Z-algorithmで何ができるか？ 文字列Sに対して、S[i : j]という記号を、Sのi番目からj番目(いずれも0-idx)までの連続部分文字列とします。 例えば、S="abcde"で S[1 :
ループ構造の正しさを証明してやる！ - それはBooks
Code Readingを読んで、ループ性能(妥当性)に関しての議論を考えるときに、有効な手段があると書いてあった。「バリアント(variant)」と「インバリアント(invariant)」という概念を使う方法だ。「バリアント(variant)」とは、変わりやすいとか変更されるといった意味を持っている。 逆に「インバリアント(invariant)」は、変わらないとか不変なとかという意味を持っているらしい。 この「バリアント(variant)」と「インバリアント(invariant)」を使って、ループ構造が正しいかを証明する方法が、Code Readingの2章に載っていたので、忘れないうちに復習しておきたいと思います。 それにしても、Code Readingは面白いですね。技術者のツボをついた本だと思います。 概要と解説 ループ処理の開始と終了の時点で共に成り立つ条件をループインバリアント
ループ不変条件 - Wikipedia
ループ不変条件（英: Loop invariant）とは、計算機科学において、ループの不変条件のこと。ループとは、繰り返し実行されるコードのこと。ループの不変条件とは、ループ実行前にも、反復を実行するたびにも成立する条件のこと。これは、論理アサーションであり、アサーションを使ってコードが書かれることもある。不変条件を知ることは、ループの意味を知るのに重要である。 形式的検証において、特にホーア論理を使った方法では、ループ不変条件は形式的な述語論理で表現され、ループの特徴やループのアルゴリズムを証明するのに使われる。ループ不変条件はループに入る前の段階でも真であり、ループを繰り返すたびにも真である必要がある。これは、ループが終了する際には、ループ不変条件とループ終了条件の両方が真であることが保証される。 ループと再帰の基礎的な類似性により、ループ不変条件を使いループの部分的な正しさを証明する
IDA* -- Iterative Deepening A* - Qiita
自分は孫弟子にあたるらしいRichard E. Korf 先生の論文紹介です。 会ったことないですがKorf先生→ https://www.youtube.com/watch?v=EnX8cQPiB1M https://www.youtube.com/watch?v=TAjyI06Q1x8 IDAはAと同じく最適解を返すアルゴリズムですが、A*と異なり メモリ使用量が線形 であるという違いがあります。 Iterative Deepening Depth First Search だれだ反復深化深さ優先探索なんて長ったらしい名前を付けたのは。 反復Xは長いのでIDDFSと呼びましょう。 IDDFSは、ダイクストラの深さ優先版です。 ダイクストラやA*などの最良優先探索系、もとい幅優先探索系に共通する問題は、OPENリストを全部メモリに確保しておかないといけないという点です。 しかし、実際のコ
アルゴリズムと数学的思考力 - 怠惰を求めて勤勉に行き着く
厳しい。年始早々厳しさを感じている。自分のプログラミング力にだ。伸び悩んでいる。 端的に言って、数学力のなさが自分のプログラミング能力に制限をかけている。例えばこの問題。 560. Subarray Sum Equals K 入力として与えられる配列 nums のうち、合計が k となる部分配列の個数を数え上げよ。どうも有名な問題らしいが… まず大前提として、部分配列なので i, j の2重ループで始点・終点を定めて sum(nums[i, j]) = k になるものを数え上げれば必ず答えが得られる。最悪計算量は O(N^3) ただし i < nums.length < 20000 という制約があるので N^3 では遅すぎるから何か考えてくださいというのがスタート地点。 ここで、結果の変わらない累積和を何度も求めているので nums[i, j] = k を求めたい場合、 nums[0, j
調和級数などのはなし - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 今日は、競プロの計算量解析でよく出てくる、調和級数と割り算で出てくる項数の話をします。 計算量解析に失敗すると、実は解ける解法なのに解析に失敗したせいで解けないと思い込んでしまい、解かなかった、みたいなことが起こりかねないので、特に非直感的なこの2つについて押さえておきましょう。 調和級数 調和級数とは、$\sum_{n=1}^k \frac{1}{n}$ で表される級数です。 $k \rightarrow \infty$ とした時に正の無限大に発散することが知られていますが、発散は非常に遅いです。 さて、この調和級数は計算量解析にしば
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
福永 津嵩 on Twitter: "「生物情報は文字列マッチングだけで2単位分の授業がある」と理情出身の学生に言ったら驚かれたが、 ・Suffix Array、SA-IS、BWT ・NW法、SW法、アフィンギャップ、スコア行列 ・seed-and-extension… https://t.co/8hxtDAPT1B"
解答略 on Twitter: "チョコボの不思議なダンジョンのマップを自動生成するコードを書いた。工程4の閉路削除は少々テクが必要で、まず廊下の交差点間の接続を表すグラフを作って * 行き止まりのエッジを削除 * ある部屋から出発して同じ部屋に戻る経路を検出し、… https://t.co/QI0PUKb335"