平方分割の練習をしようにも難しい問題ばかり、そんなお悩みに狙いを決めて手取り足取りのレクチャーです！ - CADDi Tech Blog
平方分割の練習をしようにも難しい問題ばかり、そんなお悩みに狙いを決めて手取り足取りのレクチャーです！ ちなみになのですが、「気になる💓あの子を平方分割！列の区間和を求める恋の特効薬アルゴリズムを、幸運なあなただけにご紹介です。」というタイトルは没になりました。（← これはタイトルでふざけすぎて怒られたのに懲りずにこっそり本文でサルベージする人です。） 対象の読者さん紹介です。 当記事は、平方分割にあまりなれていない方が、簡単なものであれば息を吸うようにスラスラかけるようになるのが目的です。したがってですね…… カモンです。 平方分割の実装は大変そうです。 練習のやり方がわかりません。 ノー・カモンです。 遅延評価のない平方分割なんて…… 親に重めなデータ構造を持たせるのが醍醐味ですよね〜〜 クエリ平方分割で常勝！ｗ どのように練習するのが良いでしょう。 おすすめな練習方法です まず、だめ
Googleが開発した進化的AI「AlphaEvolve」は未知のアルゴリズムや未解決数学問題の新解法を発見可能、すでにGoogle内部ではAI開発やチップ設計の効率化に活用されている
GoogleのAI研究チームであるGoogle DeepMindがコーディングエージェント「AlphaEvolve」を2025年5月14日(水)に発表しました。AlphaEvolveはGeminiと進化的アルゴリズムを組み合わせたAIエージェントで、未知のアルゴリズムを発見したり未解決数学問題の新解法を発見したりできるほどの能力を備えています。 AlphaEvolve: A Gemini-powered coding agent for designing advanced algorithms - Google DeepMind https://deepmind.google/discover/blog/alphaevolve-a-gemini-powered-coding-agent-for-designing-advanced-algorithms/ DeepMind unveils
高速ゼータ変換について - Qiita
これは データ構造とアルゴリズム Advent Calendar 2018 の 25 日目の記事です。 突然ですが 次の問題を解いてみましょう。 整数 $N$ と $A_0, A_1, A_2, ... A_{2^N-1}$ が与えられます。 $s, t$ に対して $s\ AND\ t=t$ の時、$t \subset s$ と表記することにします。 $0≦i<2^N$ を満たす整数 $i$ について、$j \subset i$ を満たす整数 $j$ についての $A_j$ の総和をそれぞれ求めなさい。 ただし、$a\ AND\ b$ は $a$ と $b$ のbitごとの論理積を求める演算とします。 $1≦N≦10$ $1≦A_i≦10^9\ (0≦i<2^N)$ 実行時間制限 2秒 問題文にある $s\ AND\ t=t$ が何を言っているのかちょっと分かりにくいかもしれませんが、こ
ゲルファント変換入門 - p進大好きサークル
趣旨 競技プログラミングでは非常に多くの畳み込みとゲルファント変換が登場するのですが、ゲルファント変換という名称が競技プログラミング界隈ではあまり有名ではないようなので簡素な解説を書いてみます。どうせ$n$番煎じかもしれませんが、現状としてあまり有名でない以上はまだまだこういう記事が増えることで調べ物の助けになる人もいるかと思いますので、あまり気にせず書いてみることにします。毎回ネタを思いついてはどうせ$n$番煎じと思ってやめちゃうのですが、たまには許してもらえますよね。 まず競技プログラマーなら以下の用語に聞き覚えがある人も多いのではないでしょうか？ 累積和 部分集合上のゼータ変換 約数ゼータ変換 倍数ゼータ変換 離散フーリエ変換（DFT） アダマール変換 これらは全部ゲルファント変換です。それぞれの原理を一々別個に勉強した覚えのある人も多いのではないでしょうか？ ゲルファント変換を知っ
物理学者ニュートンが300年前に考案して現代でも実用されるアルゴリズム「ニュートン法」がアップデートされる
by Alexander Borek 約300年前に物理学者のアイザック・ニュートンが考案した「ニュートン法」は、現代でも物流や金融工学、コンピュータビジョン、純粋数学など多岐にわたる分野で重要な役割を果たしているアルゴリズムです。これまでさまざまな数学者がこのニュートン法の改良に苦心しており、近年の研究でついにアップデートされたと科学系ニュースサイトのQuanta Magazineが紹介しています。 Implementable tensor methods in unconstrained convex optimization | Mathematical Programming https://link.springer.com/article/10.1007/s10107-019-01449-1 Three Hundred Years Later, a Tool from Isaa
Succinct data structures
Succinct data structures By Martijn Faassen • 2025-02-28 • Tags: computer science, xml, rust Introduction A few months ago, searching for ideas on how to make some code faster, I found myself reading a bunch of computer science papers. I don't pretend to be good at this - but I don't mind some confusion or being overwhelmed, and I'm okay to admit my ignorance. 1. I ran into this 15 year old paper
「二分決定グラフ」の演算にかかる最悪時間計算量を証明～計算機科学分野の数十年来の未解決問題を解決～ | ニュースリリース | NTT
◆二分決定グラフは集合の集合を圧縮して表現することができるデータ構造です。これまで最悪時間計算量が未知であった二分決定グラフの多数の演算について、入力のサイズに対して演算の実行に指数的に時間がかかる事例が存在することを示しました。 ◆本発見は今後二分決定グラフを用いた応用において、正しく計算量を見積もるのに役立ちます。 ◆計算機科学に関する著名な教科書であるThe Art of Computer Programming（TAOCP）の記述の誤りを指摘するものであり、研究チームからの修正案が承諾され改訂予定です。 日本電信電話株式会社（本社：東京都千代田区、代表取締役社長：島田 明、以下「NTT」）は、論理関数を表現する著名なデータ構造である二分決定グラフにおける長年の未解決問題を解決しました。 二分決定グラフは集合族（※1）、つまり集合の集合を表現するデータ構造として、回路設計や通信ネット
NTT、計算機科学の未解決問題を解決 著名教科書の「二分決定グラフ」に関する誤りを指摘
NTTは2月19日、計算機科学の未解決問題を解決したと発表した。同社が解決したのは、著名なデータ構造として知られる「二分決定グラフ」に関する未解決問題。今回示した理論は、計算機科学の著名な教科書にあった記述の誤りを指摘しており、研究チームの修正案が承諾され、内容が改訂されるという。 二分決定グラフとは、集合のあつまりである「集合族」を表現するデータ構造だ。例えば、集合｛1, 2｝と集合｛2, 3｝からなる集合族は、｛｛1, 2｝,｛2, 3｝｝と表現できる。集合族は汎用性が高く、さまざまなデータ構造を表現する際に使われる。その例には、ある地点から別の地点までの移動経路の組合せや、同時に利用可能なクーポンの組合せなどがある。 ネットワークの通信パターンを表現する集合族、二分決定グラフの例 図では16個の通信パターンを16個の集合からなる集合族で表現し、それを11個のノード（節点）を結ぶ線から
Go 1.24 で map が30%以上高速化！Swiss Tableとは？ - カンム テックブログ
Go1.24 がついに公開されましたね。その中でとても興味深い改善内容がありました。 1/14 Go's new map implementation in 1.24 is powered by Swiss Tables, a cutting-edge hash table design that significantly boosts performance. Let's break down why this matters and how @CockroachDB's implementation played a key role. 🧐🚀— Peter Mattis (@petermattis) 2025年2月10日 9/14 Performance gains? Benchmarks show Go's new maps are 30%+ faster in many wo
差分検出アルゴリズム三種盛り - Object.create(null)
こんばんは. 気がつけばもうずいぶんと涼しくなってきました. 勢い余って凍ってしまったりせぬよう, くれぐれも普段の言動にはお気をつけください. はじめに さて, 我々人類にはどうしても二つの文字列 (あるいは行ごとに区切られたテキスト) 間の差分を求めなければいけない瞬間が発生します. 先人たちはそういった時のために diff のようなツールを開発し, それを利用することで文明はめざましい発展を遂げてきました. しかしながら, 使用するアルゴリズムを比較検討したい場合, 「差分」の定義を変えるなどして既存のアルゴリズムに変更を加えたい場合, diff のない異世界に飛ばされて自分で実装しなければいけない時などにおいては, 差分検出アルゴリズムについての理解が必要不可欠です. というわけで, この記事では文字列間の差分検出とは何かということと, 差分を求める三種類のアルゴリズムの紹介・解説
DSA Tutorial - GeeksforGeeks
Data structures manage how data is stored and accessed, while Algorithms focus on processing this data. Examples of data structures are Array, Linked List, Tree and Heap, and examples of algorithms are Binary Search, Quick Sort and Merge Sort. Why to Learn DSA?Foundation for almost every software like GPS, Search Engines, AI ChatBots, Gaming Apps, Databases, Web Applications, etcTop Companies like
ゼロ知識証明ものがたり
これはあくまでも個人の調査の上で、ゼロ知識証明の研究の流れを物語形式に自分なりに表現したものです。ざっくりと外観を捉えたい時にご参照ください。ご指摘も歓迎しております。 第一章：ゼロ知識証明の始まり - （1985-1992） 1985年暗号理論の世界に、Goldwasser、Micali、Rackoffという3人の研究者による、ある論文が発表されました。それは「特定の情報を知っていること」を、他の一切の情報を明らかにせず他者に数学的に証明することができる技術でした。 この論文は、完全性、健全性、ゼロ知識性という3つの重要な概念を導入し、二次剰余と二次非剰余の構成を提供し、二次剰余性を判定する問題を使って、ゼロ知識証明プロトコルを具体的に構築しました。これは、後の暗号学の発展に大きな影響を与えることになります。 1992年、この分野に新たな革新が加わります。Lund、Fortnow、Kar
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.
Sub-pixel Distance Transform — Acko.net
High quality font rendering for WebGPU This page includes diagrams in WebGPU, which has limited browser support. For the full experience, use Chrome on Windows or Mac, or a developer build on other platforms. In this post I will describe Use.GPU's text rendering, which uses a bespoke approach to Signed Distance Fields (SDFs). This was borne out of necessity: while SDF text is pretty common on GPUs
Smoothed-particle hydrodynamics - Wikipedia
Schematic view of an SPH convolution Flow around cylinder with free surface modelled with SPH. See[1] for similar simulations. Smoothed-particle hydrodynamics (SPH) is a computational method used for simulating the mechanics of continuum media, such as solid mechanics and fluid flows. It was developed by Gingold and Monaghan[2] and Lucy[3] in 1977, initially for astrophysical problems. It has been
Designing a Tree Diff Algorithm Using Dynamic Programming and A* - Tristan Hume
During my internship at Jane Street1, one of my projects was a config editing tool that at first sounded straightforward but culminated in me designing a custom tree diffing algorithm using dynamic programming, relentlessly optimizing it and then transforming it into an A* accelerated path finding algorithm. This post is the story of the design and optimization of the algorithm, of interest to any
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Memory access is O(N^[1/3])
Top 50 Array Coding Problems for Interviews - GeeksforGeeks
定数倍高速化の技術
Interval parsing grammars for file format parsing (2023) | Hacker News