畳み込みの仕組み | Convolution
確率から画像処理まで、離散畳み込みと高速フーリエ変換(FFT) 激ムズ数え上げパズルと驚きの解法 https://youtu.be/FR6_JK5thCY フーリエ変換の解説動画 https://youtu.be/fGos3wrKeHY 【注釈】 整数のかけ算のアルゴリズムについて、FFTの"straightforward"な適用はO(N * log(n) log(log(n)) )の実行時間になる。log(log(n))の項は小さいが、2019年になってHarvey and van der Hoevenがこの項を取り除くアルゴリズムを発見した。また、O(N^2)を、必要な計算量がN^2と共に大きくなると表現したが、厳密にはこれはTheta(N^2)が意味するところである。 O(N^2)は計算量が高々N^2の定数倍になるという意味で、特に、実行時間がN^2項を持たないが有界であるアル
いろんなバンディットアルゴリズムを理解しよう - Qiita
今回は、何も知らないところからバンディットアルゴリズムを学びました。 シンプルなバンディットアルゴリズムから、各ユーザーごとに最適化するContextual Bandit、順序を最適化するCascading Banditまで解説します。 学んでいて疑問に思ったことを解消しつつ記載しています。 ソースコード https://github.com/birdwatcherYT/bandit 対象読者 バンディットアルゴリズムを理解して実装したい人 ユーザーごとにカスタマイズしたバンディットを理解して実装したい人（Contextual Bandit） 順序を最適化するバンディットを使いたい人（Cascading Bandit） バンディットアルゴリズム バンディットの問題設定を説明します。 スロットマシンN台がある スロットマシンの腕を引くと報酬がもらえる 累積報酬を最大化したい バンディットアル
ソルト付きハッシュのソルトはどこに保存するのが一般的か - Qiita
pictBLandとpictSQUAREに対する不正アクセスがあり、パスワードがソルトなしのMD5ハッシュで保存されていたことが話題になっています。 2023年8月16日に外部のフォーラムにpictSQUAREより窃取した情報と主張するデータ販売の取引を持ち掛ける投稿が行われた（中略）パスワードはMD5によるハッシュ化は行われているもののソルト付与は行われていなかったため、単純なパスワードが使用されていた29万4512件は元の文字列が判明していると投稿。（それ以外の26万8172件はまだMD5ハッシュ化されたままと説明。） 不正アクセスによるpictBLand、pictSQUAREの情報流出の可能性についてまとめてみた - piyolog より引用 これに関連してMD5ハッシュやソルトに関するツイート(post)を観察したところ、どうもソルトの理解が間違っている方が多いような気がしました。
Haskellでグラフアルゴリズムを攻略する(WIP)
はじめに Haskellでは、ListやTreeがよく取り上げられる一方で、グラフの話題はあまり出てこないことがあります。これは、ListやTreeには適切な始代数があり、それに応じたコンストラクタ（パターンマッチング）がうまく機能するためです。しかし、グラフ構造でも実はmatch関数を使ったパターンマッチングで、驚くほど簡潔に各種のアルゴリズムを実装できます。 グラフの基本構造 まず、グラフの基本構造を以下に示します。 import Data.List import Data.IntMap.Strict (IntMap) import qualified Data.IntMap.Strict as IM type Gr a b = IntMap (a, IntMap b) type Node = Int type LNode a = (Node, a) type Edge = (Node
解説: Life Universe
公開からだいぶ時間が経ってしまいましたが、Life Universe の技術解説を書きます。 English version is here. Life Universe について その前に、いくつか知っておくとよい事柄があるので先に説明します。 OTCA Metapixel について ライフゲームの説明については割愛します。ライフゲームはチューリング完全なので様々なパターンが存在し、その中に OTCA Metapixel というものが存在します。OTCA Metapixel は（メタ）セルのオンとオフの状態が視覚的に分かる特殊なパターンで、ライフゲームのみならず outer totalistic なルール[1]で動く全ての[2]２次元セルオートマトンを再現できます。 つまり、ライフゲームの中で動くライフゲームを見ることができます。 こちらは有名な動画ですが、実際にこういう計算が可能になり
コンピュータ将棋のアルゴリズム
コンピュータ将棋のアルゴリズム HTML版 序章 将棋のルール 簡単なインタフェースと思考ルーチンを付ける 評価関数 MinMaxとαβ法 ハッシュと千日手の処理 反復深化とハッシュを用いたαβの効率化 序盤での定跡と駒組の問題 指し手の評価と前向き枝刈 詰将棋 終章 残された課題とヒント TCP/IPでのＣＳＡプロトコルへの対応 参考文献など 2015年10月10日から書き始めました。 一週間～二週間に一章ずつ位のペースで追加していく予定ですでした。 要望があれば、付録の章まで載せますが、特になければ終章（１０章にあたります）までで止める予定ですでしたが、CSAプロトコル over TCP/IPについては書く予定です。floodgateや電王戦で使われているCSA拡張プロトコルも一部書くつもりです。（CHATコマンド等については書かないつもりです。） 特に要望されたわけではないですが、U
「競プロ典型 90問」Smallest Subsequence (最小部分列問題)
最小部分列問題 「 競プロ典型 90 問」の 006 - Smallest Subsequence（★5） (最少部分列問題) という問題を解いてみたのですが、最初は解説をみてもさっぱり分からず打ちひしがれていました･･･。 が、けんちょんの競プロ精進記録 を見るに、どうもこの問題を解く途中で出てくる nex という配列が「極めて汎用性が高いので、実にさまざまな問題で活用できます！！！」ということらしく、ちゃんと理解しといた方が良さそうだ･･･ということで気を取り直して取り組んでみたところなんとか理解できました。 せっかくなので忘れないうちに解説記事を作って記憶を定着させたいと思います。なお後半の実装パートは、Haskell で実装します。 けんちょんさんの解説記事にあるとおり、この問題 (を全探索で解く場合) の解法のキーになるのは事前に「任意の文字が i 番目以降に出現する位置」を二次
2023パズル をRustで解いてみる - すぎゃーんメモ
tkihiraさんの問題が面白そうだったので挑戦してみた。 2023年クイズ！ 上の例のように、数字の合間に四則演算（＋−×÷）や括弧を入れることで、2023 を作ってください。 - 数字の間に必ず演算子を 1 つ入れてください - ただし 9 と 8 の間には既に ÷ が入っています - 括弧は複数重ねて使用できます - 10×(-9 ÷ 8) のようなマイナス記号の使用は禁止です pic.twitter.com/K0w2miMXJA— Takuo Kihira (@tkihira) December 31, 2022 既に解説記事が出ているので解答はこちらをどうぞ。 nmi.jp 結局自分は自力では解けなくて 他の人の解法や上記の解説記事を読んでようやくできた、のだけど… 自分なりに理解して改めてRustで実装してみた。 RPN(逆ポーランド記法)の backtracking 探索の高
テキストエディタで使われがちなデータ構造 Piece Table の概要と実装 - A Memorandum
テキストエディタのデータ構造 Gap method Piece Table method Piece Table の構造 Piece Table の実装 Piece Table のメソッド まとめ テキストエディタのデータ構造 テキストエディタで採用されているデータ構造にはいろいろあります。 こちらの論文 Data Structures for Text Sequences では各種データ構造について比較検討されています。 多くは、Gap method や Piece table method をベースにしたものが多いのではないでしょうか(図で言う最下部の中心の丸印に当たります)。最近では Rope なども有名ですね。 Gap method Gap method では、現在のカーソル位置で、テキストバッファを2つに分割し Gap を間に挟み、カーソル位置に対する編集(テキスト追加/削除)を
Let’s 競技プログラミング! E8さんが教える アルゴリズム発想のキホン(12) アルゴリズムの基本用語 - 「グラフ」とは?
皆さんは「グラフ」という言葉を聞いて何を思い浮かべますか。Excel の折れ線グラフや棒グラフを想像する方が多いことでしょう。しかしアルゴリズムの文脈では、グラフは「モノとモノを繋ぐ関係」のことを指します。今回は、グラフの基本について整理した上で、どんな問題をグラフで表すことができるのかを紹介します。 グラフとは グラフは、モノとモノを繋ぐ関係を表すネットワーク構造のようなものです。グラフは頂点と辺からなり、頂点はモノを、辺は繋がりを表します。イメージしづらい場合は、鉄道路線図の駅を頂点、線路を辺と考えると良いでしょう。なお、頂点同士を識別するため、各頂点には 1、2、3…… と番号が付けられることが多いです。 無向グラフと有向グラフ 下図左側のように、辺に向きが付いていないグラフを「無向グラフ」と言い、下図右側のように、辺に向きが付いているグラフを「有向グラフ」と言います。例えば、一方通
リアルタイム共同編集のアルゴリズム (Operational Transformation; OT) を理解する試み – RORO
Google Docsのように文書を複数人でリアルタイムに共同編集できるアプリケーションがあります。あのような機能は、多かれ少なかれ、Operational Transformation (OT; 操作変換) という考え方を使って実現されているようです。興味があったので、このOTについて調べてみました。 (追記: これからは OT でなく CRDT だという話 → I was wrong. CRDTs are the future) なおGoogle Docsではいわゆる「リッチテキスト」を共同編集できますが、ここでは話を簡単にするために「プレーンテキスト」を共同編集することを想定します。 リアルタイム共同編集の流れ 共同編集システムの登場人物は次の通りです： サーバ x 1（各クライアントから届く編集操作をもとに、最新の文書を保持します） クライアント x N（文書を編集する側です） そ
みんな、とにかくオセロAIを作るんだ - Qiita
オセロAIってなんか難しそう？そんなことはありません。むしろゲームAIを学ぶ様々なレベルの人にこれ以上ないくらい最適です。この記事ではオセロAIを作ると何が良いのかをひたすら語っていきます。そしてオセロAIをこれから作る人のために参考になりそうな記事をいっぱい貼り付けていきます。 私自身はもうかれこれ1年以上オセロAIにどっぷりハマっています。詳細は以前書いた記事で。 オセロAIをおすすめする3つの理由 1. 原始的なゲーム木探索を学べる オセロは「二人零和有限確定完全情報ゲーム」と呼ばれる種類のゲームです。この名称を説明すると、 二人: 二人で行われる、 零和: どちらかが得をすればもう片方が同じだけ損をする、 有限: 探索すべき範囲(ゲーム木)が有限で、 確定: 手番が一意に定まり、 完全情報: ランダム要素などの予期せぬ情報がない、 ゲーム: ゲームである という意味です。チェスとか
はじめに - アルゴリズムとデータ構造大全
はじめに このドキュメントは，主に競技プログラミングで出題される問題を解く際に利用できるアルゴリズムやデータ構造をまとめたものです．特定の問題にはあまりフォーカスしないため，問題を解く際の考察の仕方等の内容はありません．詳しく，正確に，分かりやすく書いていこうと思っています． このドキュメントは執筆途中です． 想定する読者 C++を用いたプログラミングに慣れている方を読者として想定しており，C++言語の仕様や，文法にはあまり触れません．また，計算量という用語についても説明しません．ただし，償却計算量など，計算量の見積もりが複雑なものについては必要に応じて説明します． コードについて このドキュメントで登場するコードは，可読性向上のため，以下のようなコードがファイルの先頭に記述してあることを前提としています．また，適切な問題を用いてコードの検証がなされている場合は，コード周辺にのように，検証
アルゴリズムと数学の本を書きました - E869120's Blog
1. はじめに こんにちは、はじめまして。東京大学 1 年生の米田優峻（E869120）と申します。私は競技プログラミングが趣味で、AtCoder や国際情報オリンピックなどの大会に出場しています1。2021 年 11 月時点で、AtCoder では赤色（レッドコーダー）です。また、2020 年以降、アルゴリズムを学べる以下のようなコンテンツや資料を作成してきました。 レッドコーダーが教える、競プロ上達ガイドライン 競プロ典型 90 問 50 分で学ぶアルゴリズム さて、このたびは技術評論社から、書籍を出版させていただくことになりました2。アルゴリズムと数学が同時に学べる新しい入門書です。 「アルゴリズム×数学」が基礎からしっかり身につく本 - amazon 発売日は今年のクリスマス、2021/12/25 です。電子書籍版も同時期に出る予定です。本記事では、この本の内容と想定読者について、
Rustでつくる詰将棋Solver - すぎゃーんメモ
ついカッとなって先週からRustで詰将棋ソルバを書き始めてしまい、ようやくdf-pnで何らかの解答を出せるようになったところ。ここからもうちょっと調整していくぞ、、 pic.twitter.com/XM9iPJqocv— すぎゃーん💯 (@sugyan) November 2, 2021 というわけで突然Rustで詰将棋ソルバを作りたくなり、作った。 github.com 現時点ではまだ完成度は低くて6割ほどかな…。 とはいえそこらの素直な詰将棋問題なら普通に解けると思う。 冒頭の画像は看寿賞作品の3手詰「新たなる殺意」を2秒弱で解いたもの。 先行事例 将棋プログラムの多くはC++で書かれていて 最近はRustも増えてきているのかな？ しかし「詰将棋を解く」ことに特化しているものはあまり多くはなさそうだった。 なかでもRustで書かれているものはna2hiroさんによるものくらいしか無さ
できるだけ嘘を書かずに計算量やオーダーの説明をしようとした記事 - えびちゃんの日記
計算量についてのお話です。対象は、プログラミング経験はあるが計算量のことを知らない初心者から、計算量のことを知っているつもりになっている中級者くらいです。 数式を見たくない人にとっては読むのが大変かもですが、深呼吸しつつ落ちついて読んでくれるとうれしいです。 それから、この記事が自分には合わないな〜と思ったときは、（別の記事を Qiita とかで検索するよりも）この記事の一番下の 参考文献 にある本を読むことをおすすめします。Amazon の試し読みで無料で読めます*1。 TL; DR 関数の増加度合いのことをオーダーと呼ぶよ 計算量は、入力サイズ（など）を受け取ってアルゴリズムの計算回数（など）を返す関数だよ その関数のオーダーについての議論がよく行われるよ オーダーを上から抑えるときは \(O\)、下から抑えるときは \(\Omega\) を使うよ オーダーを上下両方から抑えたいときは
【Unity C#】PBD法でヒモを実装してみる
Position Based Dynamics (PBD法)を利用して、ヒモを実装してみたので紹介します。 Position Based Dynamicsについて ヒモの表現方法について 複数の質点をつなぎ合わせて、ヒモを表現します。 以下の動画は、ヒモの質点を可視化したものになります。(灰色の丸が質点です) PBD法を利用したヒモのシミュレーション 質点の位置から速度を計算する方法を軽く紹介します。 こちらと同様の内容はPosition Based Dynamicsの論文にも載っています。 推定位置p_iの計算 位置x_iと定常状態の伸びdから推定位置p_iを計算します。 (i = 0, 1, 2, ..., n - 1) 速度v_iの計算 推定位置p_iからv_iを計算します。 v_iは位置x_iから p_iへ向かう速度になっています。 アルゴリズム 論文に載っているアルゴリズムは以下
Index 1,600,000,000 Keys with Automata and Rust - Andrew Gallant's Blog
It turns out that finite state machines are useful for things other than expressing computation. Finite state machines can also be used to compactly represent ordered sets or maps of strings that can be searched very quickly. In this article, I will teach you about finite state machines as a data structure for representing ordered sets and maps. This includes introducing an implementation written
リバーシプログラムの作り方 サンプル
序章 はじめに リバーシのルール ソースコードの記述について 第１章 盤面の処理 1.1 定数と関数の定義 1.2 盤面の生成、初期化 1.3 石を返す処理 1.4 返せる石数を調べる処理 1.5 盤面をコピー、反転させる処理 1.6 その他の盤面処理 1.7 盤面の操作と表示 第２章 ゲーム木と探索 2.1 コンピュータ思考の関数定義 2.2 各関数の実装 2.3 ゲーム木 2.4 MinMax法とNegaMax法 2.5 αβ法 第３章 盤面の評価 3.1 評価関数の定義 3.2 パターンによる局面評価 3.3 評価クラスの構造 3.4 評価クラスの生成とファイルの読み書き 3.5 評価関数の実装 3.6 評価パラメータの更新 3.7 中盤の探索 3.8 自己対局による学習 第４章 性能改善 4.1 石数取得の高速化 4.2 着手の高速化 4.3 候補手リストの導入 4.4 終盤探索の
最適輸送の解き方
最適輸送問題（Wasserstein 距離）を解く方法についてのさまざまなアプローチ・アルゴリズムを紹介します。 線形計画を使った定式化の基礎からはじめて、以下の五つのアルゴリズムを紹介します。 1. ネットワークシンプレックス法 2. ハンガリアン法 3. Sinkhorn アルゴリズム 4. ニューラルネットワークによる推定 5. スライス法 このスライドは第三回 0x-seminar https://sites.google.com/view/uda-0x-seminar/home/0x03 で使用したものです。自己完結するよう心がけたのでセミナーに参加していない人にも役立つスライドになっています。 『最適輸送の理論とアルゴリズム』好評発売中！ https://www.amazon.co.jp/dp/4065305144 Speakerdeck にもアップロードしました: https
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
