Le Algorithm: 高速な全点対最短経路アルゴリズム
理論計算機科学 (Thoerotical Computer Science) の色んな定理やアルゴリズムを紹介していきます. 基本的には日本語の資料がほとんどないような知見を解説していきます. 執筆者: 清水 伸高 https://sites.google.com/view/nobutaka-shimizu/home 1. 全点対最短経路問題の計算量の外観 グラフ $G$ が与えられたときに全点対最短経路(APSP : all pair shortest paths)を求めたいときがあります. そんなときはほとんどの人がワーシャル・フロイド法または各点ダイクストラなどを使うかと思います. しかしこれらのアルゴリズムは頂点数 $n$ に対して最悪 $O(n^3)$ 時間かかってしまうので, $n=1000$くらいでもちょっと厳しい感じがあります. 実は辺重み付きグラフのAPSPの計算量には多
How to leverage optimal transport
大幅な加筆改訂を加えた最新版はこちらです： https://speakerdeck.com/eumesy/optimal-transport-for-natural-language-processing --- 最適輸送の使い方 〜最適輸送の直感的理解のための単語埋込入門 兼 最適輸送入門〜 【これは何？】 自然言語処理を中心に多くの利用例を挙げながら、最適輸送の直感的な理解を目指すスライドです。 「こんな風に使うことができるんだ… 面白い道具じゃん」「こういう使い方をしたかったらこういうキーワードで調べれば良いのね」と知識にアンカーを張ることが目的です。より深く知りたい人のための参考文献もできるだけ潤沢に加えました。 また、例として頻繁に活用する自然言語処理に馴染みがないかたのために、最初に単語埋め込みのチュートリアルをつけてあります。 【コンテンツ】 1. 単語埋込入門 … 「分布仮
AGC018: C – Coins を離散凸解析（L 凸関数最小化）で解く
頂点集合が $U = \set{1,\dots,N},$ $V = \set{1,2,3}$ である完全二部グラフ $G = (U, V; E)$ を考える．以下が与えられる: 正整数 $b_1, b_2, b_3$（ただし $b_1 + b_2 + b_3 = N$），各辺 $(i, j) \in E$ の正整数重み $c_{ij}$．以下の $2$ 条件を満たすように辺部分集合 $S \subseteq E$ を選ぶとき，重みの和 $\sum_{(i, j) \in S} c_{ij}$ の最大値を求めよ: 二部グラフ $(U, V; S)$ において各頂点 $i \in U$ の次数は $1$，二部グラフ $(U, V; S)$ において各頂点 $j \in V$ の次数は $b_j$． 入力に対する制約$3 \leq N \leq 10^5$$1 \leq c_{ij} \leq
清一色のシャンテン数を01BFSで計算する - yukinote
概要 清一色のシャンテン数は01BFSで計算できる。 機械的な計算なので、正当性が簡単に証明できる。 シャンテン数とは テンパイするまでに必要な牌の最小枚数のこと。 例えば 🀉🀊🀍🀎🀑🀒🀙🀚🀛🀜🀜🀀🀁 のとき、🀈🀌 を引いて🀀🀁を捨てればテンパイとなる。これより少ない枚数の入れ替えでテンパイすることはできないので、この手牌のシャンテン数は2となる。 この例のようにシャンテン数がわかりやすいケースがほとんどだが、清一色のような場合はシャンテン数を求めにくい。 特にプログラムでシャンテン数を計算する場合、正しいコードを書くことは難しい。また、正当性を保証するのも難しい。 考える問題 清一色だけを考える。以下では萬子🀇🀈🀉🀊🀋🀌🀍🀎🀏だけを扱う。 複数色ある場合や字牌を含む場合でも、清一色のシャンテン数さえ計算できていれば、軽いdpで解くことが
二分探索よりお得なオンライン価格戦略 - 麻辣坊主
オンライン価格設定で面白いと思った結果を紹介します． 「適正価格を二分探索するとそこそこ良い方法になるが， 二分探索に少し手を加えるとさらに良い方法になる」という話です． 出典は R. Kleinberg and T. Leighton (FOCS 2003) の Theorem 2.1 です． この記事自体は Haifeng Xu 先生の講義スライド の第 1 回をかなり参考にしてます． ゲーム理論と機械学習の様々な興味深いトピックが網羅されていておすすめです． 問題設定 戦略の評価尺度：リグレット 自明な $\mathrm{O}(N)$ リグレット戦略 二分探索による $\mathrm{O}(\log N)$ リグレット戦略 二分探索を改良した $\mathrm{O}(\log\log N)$ リグレット戦略 まとめ 問題設定 あなたは A さんに $N$ 個のリンゴ を，$1$ 日
2のべき乗サイズの配列は危ないという話 via 行列積 - elkurin’s blog
こんにちは。労働者です。とあるプログラムで学生さんの課題を添削していたら面白い話に出会いました。 僕は今、主に学部生向けのインターン研修的なプログラムでメンターなるものをやっています。メンターとしての仕事は、学生さんの課題へフィードバックを返し、Office Hourというセッションを毎週設けて質問受けやCSに関するトークを行うといった内容になっています。今回話題に取り上げるのはその中の課題の1つ、「行列積のプログラムを書いて時間を計測せよ」という何気ない話で、続く課題たちのいわば前座のようなものです。こういったところに沼は隠されているものですね。 担当している学生さんたちが細かい実験を行ってくれて以下のような疑問が提示されました。 「行列積の計算が N = 1024のときだけ N = 1023, 1025のときに比べて3倍遅いのはなぜ？」 配列のサイズが2のべき乗になるのは避けるべきとい
Red Blob Games: Hexagonal Grids
Mar 2013, updated in Mar 2015, Apr 2018, Feb 2019, May 2020, Oct 2021, Dec 2022, Feb 2023, Oct 2024, Mar 2025 This guide will cover various ways to make hexagonal grids, the relationships between different approaches, and common formulas and algorithms. I've been collecting hex grid resources[1] for over 25 years. I wrote this guide to the most elegant approaches that lead to the simplest code, st
ファミコンゲームについて
Karu_gamo★★☆☆☆ @Karu_gamo 『アトランチスの謎』のマップデータ、(16x16pixを１マスとして)縦８マス分の短冊状のデータをテーブル化してるっぽい。縦は240pix÷16pix=15マスなので、上下で別の短冊データということになる(1つ余る)。上下で別々に設定できるから、こういう上下分割されたステージが作りやすいようだ。 pic.x.com/PotOYMfPJm 2024-11-02 16:24:04 Karu_gamo★★☆☆☆ @Karu_gamo 屋外ステージでは、上半分は空白が続くので短冊データは１つで済む(たまに雲があるが)。凝る必要があるのは下半分だけなので効率良さそう。ちなみにこの背の高い木がちょうど半分になっている(下１マスあまる)。 pic.x.com/clsajkoc30 2024-11-02 16:24:05
過半数判定アルゴリズム（LeetCode / Majority Elementより） - Qiita
（ブログ記事からの転載） 過半数を獲得した候補者を効率的に特定するにはどんな方法が良いと思いますか？ 今日の問題は、そう読み替えてみるとなかなか奥が深いです。 [https://leetcode.com/problems/majority-element/] Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. You may assume that the array is non-empty and the majority element always exist in the array. Example 1: Input: [3,2,3] Output: 3 Example 2: I
inversion counting
2018/10/31 勉強会 (文字が見えない方は、ダウンロードするかフルスクリーンにしてご覧ください)
ネットワークフロー問題たちの関係を俯瞰する - 私と理論
ネットワークフロー好き好きマンとして，フローを布教したくなったので記事を書きました． ただし，フローの解説資料は既に素晴らしいものがたくさんあるので，今回は今まであまり焦点が当てられてこなかった部分を推して話をしたいと思います． テーマは，数あるフローの問題の関係を整理することです． フローの問題たちには共通の歴史があり，共通の定式化があり，共通のアルゴリズムの思想があります． その「共通」の部分を理解することで，フローに対する理解が深まり，より面白いと感じられると僕は思っていて，そこについて書きます． かなり基本的な内容しか書いてないので，強い人が得るものはあまりないかもしれません． あとこの記事はおきもちを書いてる部分が多いです． また，この記事では問題の話だけをしてアルゴリズムの詳細の話をほとんどしません．この辺りは 保坂さんのスライド などが非常に分かりやすいので，そちらを参照して
安全で爆速なRollingHashの話 - Qiita
要約 ロリハ(RollingHash)のModを$2^{61}-1$にすると安全で爆速になってむちゃくちゃ幸せになれます。 前提知識 bit演算に関する基礎的な知識を要求します。 また、RollingHashについては以下で解説しますが、分からない場合は別の記事を読んだほうがいいかもしれません。 RollingHashとは? 開く 「文字列を一つの大きな整数として見る」というのがRollingHashのアイデアです。 まず、0-9のみの数字を含んだ文字列s = "1234567890"を考えてみます。 ここで、この文字列のHash値を文字列を10進数と解釈したときの数値と定義します。 また、$s$の$a$文字目から$b$文字目の前までの部分文字列を$s[a..b]$と書くことにします。 例えば、s = "1234567890"について、$s[1..3]$は1文字目から3文字目の前までの部分
Monge 行列と monotone minima について - Lorent’s diary
Monge 行列や monotone minima について何も知らない方でも理解できるよう, 一から丁寧に解説する記事を書きました. 計算量解析については多少の前提知識を要求しますが, その他の部分については式を追っていけば理解できると思います. 本記事の評判次第ではありますが, 続編として SMAWK algorithm についての記事もいずれ書きたいと考えております. Monge 行列の定義と性質 定義 補題 1 証明 補題 2 証明 補足 monotone minima アルゴリズムの解説 補足 実装例 例題 参考リンク 参考文献 謝辞 Monge 行列の定義と性質 定義 $ m \times n $ 型実数値行列 $ A $ が, $ 1 \leq i \lt k \leq m $ および $ 1 \leq j \lt l \leq n $ を満たすすべての $ i, j, k,
平衡二分探索木を使った2-optの効率化について - aspirator’s blog
こんにちは。 平衡二分探索木で2-optを高速化する方法について研究したので、本記事ではそれについて書こうと思います。 2-optとは 2-optは巡回セールスマン問題(TSP)の近似解を求めるヒューリスティックアルゴリズムです。 下図のように、サイクルに対してランダムに二つのパスを選び、パスを組み替えた方がサイクルの長さが短くなる場合、パスを組み替えます。具体的には、A→B + C→D > A→C + B→D の時、辺ABと辺CDを辺ACと辺BDに組み替えます。 しかし、辺を張り直すだけではサイクルにならないので、B~CまたはD~Aの間の順序を逆にする必要があります。 2-opt法では順路を配列などで管理することでこれを実現しています。 そしてこれが`測定で用いた2-optの実装です。 #include<iostream> #include<algorithm> #include<vec
グレイコード
グレイコード（Gray code）とは、２進数の表現で、隣り合う値でビットの変化が１ビットしかないようにしたものです。 たとえば、４桁の２進数（バイナリコード）で考えると、 １０進数の「７」から「８」に変化する場合、２進数では「０１１１」から「１０００」となり、 ４桁すべてのビットが０から１または、１から０へと変化します。 電気（電子）回路では、２進数の「０」、「１」を電圧の高い状態「Ｈ」と低い状態「Ｌ」で扱います。 入力回路は、「Ｈ」と「Ｌ」を検出する速度が異なります。 （Turn on time および Turn off time が異なる） 上記の「７」から「８」に変化する場合、入力回路の遅延により、 最悪「１１１１」または「００００」の値として読み込む可能性があります。 １０進数の「１５」または「０」となってしまいます。 ロータリエンコーダ（回転位置検出センサ）で、回転する軸の角度
Tsukasa #01 (4x vaccinated) on Twitter: "真偽はともかく、ちょっととんでもない論文が出てきたんだが。国際暗号学会の未査読論文だが、素因数分解を (RSA を破壊するレベルで) 劇的に高速化するアルゴリズムを開発したと主張している。 https://t.co/ApzLqRmjqR"
真偽はともかく、ちょっととんでもない論文が出てきたんだが。国際暗号学会の未査読論文だが、素因数分解を (RSA を破壊するレベルで) 劇的に高速化するアルゴリズムを開発したと主張している。 https://t.co/ApzLqRmjqR
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Hal Tasaki on Twitter: "遅ればせながら早水さん @hayamizu_lab のグラフ理論入門講義を仕事の合間に順に聴講してようやく連載（？）に追いつきました！ それにしても、みなさんおっしゃるように、これは本当に素晴らしい。YouTube 上の最高級の文… https://t.co/738Eahx1wk"
Karu_gamo on Twitter: "【麻雀：任天堂】任天堂初期の麻雀の中身を見てみたいと思います。とてもシンプルな二人打ち麻雀がどのようにできているのか？ メモリを除くと、自分の手牌と同じ数字の羅列が見つかります。そして、その上に相手の手牌が２列。これは配牌時ですが… https://t.co/1Tvgbu2NqV"
E869120@本発売 on Twitter: "今日は 3.11 ということで，地震対策に使われているアルゴリズムについて 4 枚の資料にまとめてみました．（自分でも気になったので，資料や論文を 2 時間くらい調べてみて，勉強になりました） https://t.co/d03B17THzG"
Miller-Rabin素数判定法 - Mister雑記
