Dancing Links の secondary column を使って、"ゆるい Exact cover" 問題を解く
この記事では、Knuth's Algorithm X (DLX) の secondary column を使って、「全マスを埋めなくてもOK」なブロック配置問題を解く方法を紹介します。 Advent of Code 2025 Day12 の問題を題材に解説を行います。 Advent of Code の話 今年も 12月になり、 Advent of Code の季節がやってきました。例年は25日分開催されるところ、今年は12日と規模は縮小されましたが、こうやって続けられるのは素直に嬉しいですね。 今回はその中でも Day12: Christmas Tree Farm の問題を解くときに新しいアルゴリズムに出会ったときの話です。 問題設定について この問題の設定についてまず説明します。以下のようなブロックの定義が与えられます。 # がブロックで、 . が空きマスです。 これは「4x4 のグリッ
Static search trees: 40x faster than binary search
1 Introduction1.1 Problem statement1.2 Motivation1.3 Recommended reading1.4 Binary search and Eytzinger layout1.5 Hugepages1.6 A note on benchmarking1.7 Cache lines1.8 S-trees and B-trees2 Optimizing find2.1 Linear2.2 Auto-vectorization2.3 Trailing zeros2.4 Popcount2.5 Manual SIMD3 Optimizing the search3.1 Batching3.2 Prefetching3.3 Pointer arithmetic3.3.1 Up-front splat3.3.2 Byte-based pointers3.
Generalized Dijkstra in Haskell
This years’ Advent of Code has loads of 2D grids, and makes you traverse them all to find paths of various kinds. At some point I had to implement Dijkstra’s algorithm, in Haskell. In trying to make my implementation reusable for the following days, I realized that Dijkstra’s algorithm is actually way more general than I remembered (or was taught)! In short, weights don’t have to be real-valued! I
GoogleがJPEGエンコーダー「Guetzli」をオープンソースで公開
by greyloch Google製のJPEGエンコーダー「Guetzli」がGitHubで公開されています。生成されるJPEGファイルはlibjpegと比較したとき、同等の品質でファイルサイズが20～30％ほど小さくなるとのことです。 GitHub - google/guetzli https://github.com/google/guetzli 特にニュースリリースなどは発表されていないようなのですが、2016年10月にEncode.ruというフォーラムにJyrki Alakuijala氏が投稿した内容(Googleキャッシュ)によると、このGuetzliはGoogleが新たな圧縮アルゴリズムとして2013年に発表した「Zopfli」ライクな、非常に遅いJPEGエンコーダーだとのこと。 画像の品質とファイルサイズについて、butteraugliを用いてlibjpegと結果を比較した
diffの動作原理を知る～どのようにして差分を導き出すのか | gihyo.jp
UNIXの基本的なコマンドの1つであるdiff。 これに実装されているアルゴリズムは実に興味深い世界が広がっています。 本稿では、筆者が開発した独自ライブラリ「dtl」をもとに「diffのしくみ」を解説します。 はじめに diffは2つのファイルやディレクトリの差分を取るのに使用するプログラムです。 ソフトウェア開発を行っている方であれば、SubversionやGitなどのバージョン管理システムを通して利用していることが多いかと思います。本稿ではそのdiffの動作原理について解説します。 差分の計算の際に重要な3つの要素 差分を計算するというのは次の3つを計算することに帰結します。 編集距離 2つの要素列の違いを数値化したもの LCS（Longest Common Subsequence） 2つの要素列の最長共通部分列 SES（Shortest Edit Script） ある要素列を別の要
定番アルゴリズム本リスト - カレーなる辛口Javaな加齢日記
どうせ何度も使い回ししそうなので，独立した項目に切り離した． アルゴリズムイントロダクション 第3版 第1巻: 基礎・ソート・データ構造・数学 (世界標準MIT教科書) 作者: T.コルメン,R.リベスト,C.シュタイン,C.ライザーソン,浅野哲夫,岩野和生,梅尾博司,山下雅史,和田幸一出版社/メーカー: 近代科学社発売日: 2012/08/02メディア: 単行本購入: 1人 クリック: 16回この商品を含むブログ (21件) を見るアルゴリズムイントロダクション 第3版 第2巻: 高度な設計と解析手法・高度なデータ構造・グラフアルゴリズム (世界標準MIT教科書) 作者: T.コルメン,R.リベスト,C.シュタイン,C.ライザーソン,浅野哲夫,岩野和生,梅尾博司,山下雅史,和田幸一出版社/メーカー: 近代科学社発売日: 2012/12/26メディア: 単行本購入: 1人 クリック: 4回
世界でもっとも強力な9のアルゴリズム - しっきーのブログ
米国の大学教授によるコンピュータ・サイエンスのガイド。大方の人はアルゴリズムと聞くとソートプログラムを思い浮かべるだろうが、本書は普段私達がよく使うようなシステムに関わるアルゴリズムを取り上げる。これはアルゴリズムなのか？というトピックもあるが、重要な考え方を扱っていることに変わりはない。 世界でもっとも強力な9のアルゴリズム 作者: ジョン・マコーミック,長尾高弘出版社/メーカー: 日経BP社発売日: 2012/07/19メディア: 単行本購入: 15人 クリック: 437回この商品を含むブログ (21件) を見る 平易な言葉で説明できていて、数学的な手法を抜きにすれば、コンピューターの基本的な考え方がわりとシンプルにできていることがわかる。「この本の著者として私がとても驚いたのは、これら大きなアイデアは、どれもコンピュータープログラミングやコンピューター科学の予備知識を一切必要とせずに
深さ優先探索による塗りつぶし
深さ優先探索とは 探索とは • 探索とは，可能性を調べながら，解を探す方法です 深さ優先探索とは • 最も基礎的な探索の方法です 本スライドで学ぶこと •深さ優先探索による「塗りつぶし」 • 深さ優先探索の再帰関数による実装 • 深さ優先探索のスタックによる実装 2015/6/6 2
Optimizing A* for grid maps
► 2024 ( 1 ) ► March 2024 ( 1 ) ► 2023 ( 14 ) ► December 2023 ( 1 ) ► November 2023 ( 1 ) ► October 2023 ( 1 ) ► September 2023 ( 1 ) ► August 2023 ( 1 ) ► July 2023 ( 1 ) ► April 2023 ( 4 ) ► March 2023 ( 1 ) ► February 2023 ( 1 ) ► January 2023 ( 2 ) ► 2022 ( 13 ) ► December 2022 ( 2 ) ► November 2022 ( 2 ) ► October 2022 ( 2 ) ► September 2022 ( 1 ) ► June 2022 ( 1 ) ► May 2022 ( 1 ) ► April 20
Open Data Structures
Open Data Structures covers the implementation and analysis of data structures for sequences (lists), queues, priority queues, unordered dictionaries, ordered dictionaries, and graphs. Data structures presented in the book include stacks, queues, deques, and lists implemented as arrays and linked-lists; space-efficient implementations of lists; skip lists; hash tables and hash codes; binary search
Parsing expression grammar - Wikipedia
Parsing Expression Grammar（PEG）は、分析的形式文法の一種であり、形式言語をその言語に含まれる文字列を認識するための一連の規則を使って表したものである。PEGは再帰下降構文解析を文法を示すためだけに純粋に図式的に表現したものと見ることもでき、具体的な構文解析器の実装やその用途とは独立している。 PEGにおける構文（文法）の定義は文脈自由文法のバッカス・ナウア記法によるそれに似ているが、文脈自由文法では一般に「｜」（縦棒、バーティカルバー）で表される「これらのうちどれか」ではなく、「最初の解析がうまくいったらそれを、失敗なら次を順に試してゆき、成功したものを採用」（「/」であらわす）という意味を使う。 このため、文脈自由文法とは異なり、PEGには曖昧さは存在しない。文字列を構文解析する場合、正しい構文木は常に1つしかない。このためPEGはコンピュータ言語の構文解析
プログラミングコンテストで、C++を使って全ての問題を解くのに必要なアルゴリズムは何ですか？ | POSTD
これが私の提案するリストです。必要とされるアルゴリズムや概念のほとんどが挙げられています。いくつかの要素はアルゴリズムではなかったり（フェイクや状態、関心事など）、重複していたりもします。 最後に1つ、アドバイスを。 知識を蓄える前に、まずは思考能力を鍛えることを重要視しましょう。これはコンテストのみならず、あなた自身の将来にも役立ちます。思考能力を鍛えるには、アルゴリズムではなく純粋な思考を必要とする、アドホックを使いこなせるようになりましょう。 topcoderのDiv2とCodeforcesのDiv2の2つに集中することも効果的だと思います。どちらも、低いレベルから問題に取り組んでいきましょう。例えば、Div2-250をマスターしてからDiv2-500に取り組む、などです。
std::string::findより速くなるかもしれない。boost::algorithmのboyer_moore_searchとかknuth_morris_pratt_searchとか - Qiita
この記事は、C++ Advent Calendar 2014の2014年12月7日ぶんです。（1時間弱遅刻してしまいました） これは何ですか C++標準の文字列クラスstd::stringには、その中に指定されたキーワード（文字列）が含まれているか&含まれている場合には何文字目から出現するかを返すメソッドとして、std::string::findが用意されている。 多くの場合これがあれば事足りるのだが、あまり長い文字列を検索キーワードに指定するような場合には、（少なくとも理論的には）大幅に遅くなることが知られている。 これを改善した（少なくとも理論的には）アルゴリズムとして、Boyer-Moore SearchやKnuth-Morris-Pratt Searchというアルゴリズムがある。本記事では上記の遅くなる理由とこれら二つのアルゴリズムについて概略を説明する（実装の詳細は一部のみ説明）
アルゴリズムとプログラミングをビジュアルで一挙に理解できる「VisuAlgo」
アルゴリズムを理解するのにビジュアル化することは非常に有効で、プログラムをビジュアル化することで理解が進むのもまた同じ。そこで、アルゴリズム・プログラミングの理解が進むようにと、アルゴリズムを記述したプログラムコードを一挙にビジュアル化することで、アルゴリズム＆プログラミングを同時に学習できる一挙両得なサービス「VisuAlgo」が公開されています。 VisuAlgo - visualising data structures and algorithms through animation https://visualgo.net/en 上記のVisuAlgoサイトで試しにソートアルゴリズムの基本プログラム「バブルソート」をビジュアル化してみます。「Sorting」の「bubble」をクリック。 検索窓の下に「bubble」と表示されたのを確認したら「Sorting」の画像をクリック。
平方数かどうかを高速に判定する方法 - hnwの日記
平方数とは、ある整数の平方（＝二乗）であるような整数のことを言います。つまり、0,1,4,9,16,...が平方数ということになります。 ところで、与えられた整数が平方数かどうかを判定するにはどうすれば良いでしょうか。与えられた整数の平方根の小数点以下を切り捨て、それを二乗して元の数になるかどうか、というのがすぐ思いつく実装です。 <?php function is_square($n) { $sqrt = floor(sqrt($n)); return ($sqrt*$sqrt == $n); } しかし、平方根の計算は比較的重い処理です。もっと高速化する方法は無いのでしょうか。 多倍長整数演算ライブラリGNU MPには平方数かどうかを判定するmpz_perfect_square_p関数が存在します（PHPでもgmp_perfect_square関数として利用できます）。本稿ではこの実装
日本の競技プログラミングを世界水準に引き上げる レッドコーダー 秋葉拓哉 | 三年予測 | dodaエンジニア IT
レッドコーダー 秋葉拓哉 1988年生まれ。25歳。高校2年生のときにプログラミングコンテスト「SuperCon」で準優勝、 「日本情報オリンピック」にて優勝を達成。それ以降プログラミングコンテストに精力的に参加し、 2012年に「ACM-ICPC」世界大会にて銅メダルを獲得。 プログラミングコンテスト向けアルゴリズム書『プログラミングコンテストチャレンジブック(第二版)』(マイナビ)が発売中。 秋葉拓哉は、最初は自分がレッドコーダーになれるとは思っていなかったそうだ。 レッドコーダーとは、約60万人がオンラインで参加するプログラミングコンテスト「TopCoder」での成績を示す数字「レーティング」が2200以上の挑戦者のことだ。プログラマの中でも一目置かれる存在である。 2007年に秋葉が大学に入りTopCoderの存在を知った頃、レッドコーダーは日本で4人しかいなかった。レッドコーダー
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://metodosestadisticos.unizar.es/asignaturas/62801/DiferentialEvolution.pdf
warterlogueのアルゴリズム分析
色々なダイクストラ高速化
VisuAlgo moves to https://visualgo.net/en