グラフとは，点の集合と枝の集合からなる「つながり方」を表すモデルです。 二部グラフとは，点が 222 グループにわかれていて，同じグループ間はつながっていないようなグラフです。→グラフ理論の基礎
二部グラフの最大マッチングと増加道 | 高校数学の美しい物語
グラフとは，点の集合と枝の集合からなる「つながり方」を表すモデルです。 二部グラフとは，点が 222 グループにわかれていて，同じグループ間はつながっていないようなグラフです。→グラフ理論の基礎
一般的なダイクストラ法 - kirika_compのブログ
概要 ダイクストラ法を使うと、単一始点 s から全ての頂点への最短距離が計算できるのは有名だね。これを少し拡張することで、「s からの最短距離と、それを実現する最短経路の個数」の組を、全ての頂点について計算することができるわ。 詳しく 少し天下り的だけど、以下の半環を考える。 (a, x) + (b, y) := a < b ? (a, x) : a > b ? (b, y) : (a, x + y), (a, x) * (b, y) := (a + b, x * y) この半環を使って、[Mohri2002]の方法でダイクストラ法を行うことにより、s-vの最短距離とs-vの最短経路の個数が全ての頂点vについて分かる。 ソースコードは以下の通り。 gist.github.com ARC090 E - Avoiding Collision で確かめた。 https://beta.atcode
競プロにおけるNim、Grundy数とNimK - かっさのなにか
この記事は、 「競プロ!!」 競技プログラミング Advent Calendar 2017 21日目 の記事です。 昨日は DEGwer さんの「数え上げテクニック集」でした。まだ全部読んでないけど凄かったです。 こっちでも同時に競プロのアドベントカレンダーが進められています。 Nim,grundy数がわかっていると、盤面を共有して二人で対戦し、勝敗が必ず決するタイプのゲーム問題がわりとサクッと解けます。 最近では 5日前、2017/12/16 の Atcoder Regular Contest 087 E で Grundy数の問題が出ました。 この記事の本題はNimの拡張されたゲーム、NimKの話です。 導入として、Nimとかgrundy数を知らないひとにもわかるようにスライドを作成しました。 絵を描くだけのつもりだったのにスライドになってしまいました。 適当すぎてわからん！と思うひとも
Grundy数 その2 - へなちょここーだー
前回はGrundy数とは何かを説明しました。Grundy数に関する基本的な求め方は前の記事をご覧ください。augusuto04.hatenablog.com ただ、これだけではあまり多くの問題に使えないのでもう少し発展的な使い方を紹介します。 Nim 私は知りませんでしたが、有名なゲームらしいですね。ルールは次の通り。 n個のコインの山があります。プレーヤーは１つの山を選んで、その山から1枚以上のコインを取り除きます。これを2人で交互に行い、取り除くコインがなかったらその時点で負けになります。 ここで、上のような場合を(4, 2, 1)と今回は表します。 とりあえず各山についてGrundy数を求める まずは、各山についてGrundy数を求めます。 もし、0枚の山があるとするとここからは遷移できないのでGrundy数は0。 1枚の山からは0枚の山に遷移できるのでこれ以外で最小は1。 2枚の山
Grundy数 その１ - へなちょここーだー
Grundy numberについての勉強をしたので、そのまとめ（自分用のメモでもある）。ちなみにNimberとも言うみたいですね。実際にいくつかのゲームを考えながら説明をしていきます。最後の結論まで少し長いです。 そもそもGrundy数ってなんだろう 具体例は後で出すとして、とりあえずGrundy数の求め方から紹介します。 ある状態におけるGrundy数はそこから遷移できる状態におけるGrundy数以外の最小の0以上の整数。 えーと・・・。これだけでは良く分かりませんね（笑）。じゃあ実際にあるゲームを考えてみます。 30を言ったら負けゲーム 以前、伊東家の食卓というテレビ番組で紹介されたゲームです。ルールは次の通り。 先手と後手が交互に1つ以上3つ以下の整数を1から順に30まで言っていく。 先手は1から初め、30を言った人が負け。例えば、先手:1, 2, 3 後手:4 先手:5, 6 後手
アルゴリズム - PukiWiki
2025-05-12 韓国語 プレゼント 2025-05-11 GitHub 2025-05-10 洋服 2025-05-08 Google Sheets 2025-05-07 生活 ふるさと納税 2025-04-27 量子コンピュータ 2025-04-19 MySQL 2025-04-11 トラブルシューティング 2025-04-10 ネットワーク 2025-03-16 FrontPage 2025-03-04 ラストウォー 2025-03-01 Steam 2025-02-28 料理 2025-02-26 セキュリティ 2025-02-21 パソコン 2025-01-18 Azure 2025-01-13 レシピ 2025-01-02 哲学 2024-12-25 歯医者 2024-12-16 名刺 2024-10-25 自転車 2024-10-03 Chrome 2024-09-30
競プロにおけるオイラー路とその応用について - Learning Algorithms
この記事はCompetitive Programming Advent Calendar 2017の12月8日の記事です。 競プロにおけるオイラー路とその応用について 目次 ・はじめに ・オイラー路とは？ ・無向グラフのオイラー路 ・有向グラフのオイラー路 ・無向オイラー路の構築 ・有向オイラー路の構築 ・実装 ・例題 ・追加問題 ・最後に はじめに この記事では、オイラー路の基礎、そして主に競技プログラミングで使えるその応用についてできるだけ詳しく書きます。 最初の方は基礎的な定義や解説を書いているので、オイラー路とは何かをすでにご存知の方は、無向オイラー路の構築あたりからどうぞ。 説明で出てくるグラフは特に断らない限り連結で、多重辺や自己辺は基本的にあってもよいものとします。 また、もし必要があればこの記事に載せたコードはすべて自由に使って頂いて構いません。 例題で扱った問題は、はまや
フィボナッチヒープ - 宇宙ツイッタラーXの憂鬱
adventar.org フィボナッチヒープとは この記事ではヒープは最小値を求めるものとします。 フィボナッチヒープとは、フィボナッチ数の性質をうまく使ってならし計算量で高い性能を持ったヒープです。 ヒープ フィボナッチヒープ 二分ヒープ 最小値の削除 ならし O(log n) O(log n) 値の追加 O(1) O(log n) 値の追加が非常に多く、最小値の削除が非常に少ない場合は、二分ヒープより速くなることもあるかもしれません。他にもヒープ同士をマージできたり、ヒープ内の値の減少ができたりしますが、この記事では扱いません。すみません。 構造 図は wikipedia からの引用です。 フィボナッチヒープは、下図のようにいくつかのツリーを並べたような構造を持っています。ツリーの各ノードに、ヒープ内の値が入っています。各ツリーでは、上の根に近いほうが小さい値になるようになっています。
遅延伝播セグメント木について（旧：遅延評価セグメント木について） - beet's soil
もう12月まじ？こわれる はじめに 先にこっちを見て beet-aizu.hatenablog.com 2019/05/06 編集 遅延評価を遅延伝播に変更 問題例へのリンク↓を追加 beet-aizu.hatenablog.com 【はじめに】 これの続きです。 beet-aizu.hatenablog.com 前提としてうし木（普通のセグメント木）までは理解しているものとします。 この記事では後述する の場合だけ取り上げましたがそうでない例が↓の後半にあります。 beet-aizu.hatenablog.com 【遅延伝播セグメント木とは】 ある列に対して連続する区間に対して更新と取得ができるデータ構造である。以降遅延セグ木と略す。 前回のブログでは、要素の集合 と写像 からなるモノイド を考えた。 遅延セグ木では、新たに作用素の集合 と写像 からなるモノイド を追加し、 さらに作用と
セグメント木をソラで書きたいあなたに - hogecoder
セグ木がソラで書けなかったらセグ木に何か生やす問題とか解けない— つたじろう@帰省 (@_TTJR_) March 29, 2017 セグ木にいろいろ生やす問題がてんで解けない私なので、セグ木に慣れようと思い立ちました。そのためにはまずセグ木をもっと知らねばならないと思ったので、ソラで書けないか色々やっていました。 やってくうちにコツを掴んでソラで書けるようになってきたので、忘れないためにも記事を書くことにしました。ということで、何も見ずにセグ木を書くために押さえておきたいポイントを紹介していきます。 注意 この記事は、「セグ木がどんな形をしているかはわかるけど、実装はできない・・・」という方向けで、遅延評価が不要な、区間最小の基本的なセグメント木のみ扱っています。 そもそもセグ木って何という人は他記事を参考にしてください。 おすすめは iwiwi さんのスライド → プログラミングコンテ
初期化配列の実装 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? こんにちは、最近ハマっている初期化配列について紹介したいと思います。 はじめに 皆さんプログラミングをする時に配列を使ってますか？使ってない人はほとんどいないのではないでしょうか？ 長さNの固定長配列AはN個の要素を格納でき、かつ任意の位置に保存された要素A[i]を最悪定数時間（以下、定数時間）で読み書き可能な最も基本的なデータ構造の一つです。配列の様々な操作の中で読み書きについで頻出する重要な操作が、配列の全ての要素を指定した値に書き換える初期化操作です。配列の初期化は配列長に対して線形な時間がかかるため、配列長が長い場合や、初期化が
Bloom Filters by Example
A Bloom filter is a data structure designed to tell you, rapidly and memory-efficiently, whether an element is present in a set. The price paid for this efficiency is that a Bloom filter is a probabilistic data structure: it tells us that the element either definitely is not in the set or may be in the set. The base data structure of a Bloom filter is a Bit Vector. Here's a small one we'll use to
Bloomフィルターについて調べた
Eric Redmond & Jim R. Wilson 著の”Seven Databases in Seven Weeks” を読んでいたところ、Ch.8 Redis の Day2 で書籍名の重複チェックに Bloom Filter という確率的データ構造(アルゴリズム?)が利用されていた。本ではさらっとしか触れられていなかったので調査。 処理の流れ 材料 ビット配列(m ビット) ハッシュ関数(k個。整数1からm のどれかをかえす) 作り方 下ごしらえ ビット配列の各ビットは予め0で初期化しておく。 各初期データをk個のハッシュ関数に食わせ、ハッシュ関数のかえすビットを立てる。 重複チェック 重複チェックしたい入力値をk個のハッシュ関数に食わせる ハッシュ関数のかえすビットがビット配列で立っているかチェック すべてのビットが立っていれば、重複と判定。 一つでも立っていないビットがあれば
2部グラフにおける最大マッチングの個数と最小点被覆の個数の一致 - komiyamの日記
蟻本に載っていた事実だけど、理解するのに時間がかかった。 まず、前段階として|マッチング| <= |点被覆|であることを確認しよう(これは一般のグラフで成り立つ)。これは、マッチングに含まれる辺を被覆するのに最低限マッチングと同じだけの点が必要だから。なので|最大マッチング|<=|最小点被覆|となる。 具体的に最小点被覆を構成してみよう。2部グラフにsinkとsourceつなげて最大流を流し、最大マッチングを作る。このとき、残余グラフでsourceから到達不可能な左側の点集合と到達可能な右側の点集合の和集合Xが最小点被覆になっている。以下ではこれを示す。 もっと具体的に考えてみよう。図のように色を付ける。最大マッチングに含まれる辺は赤。そうでなければ黒。 左から右にいくときは黒だけ通れる。右から左にいくときは赤だけ通れる。赤い辺がついていない左の点を出発点にできる。 ここで次の2つを調べて
Re永続データ構造が分からない人のためのスライド
Competitive Programming Advent Calendar 2012の12/01担当分の記事です。
競技プログラミングにおける永続データ構造問題まとめ - はまやんはまやんはまやん
永続データ構造 persistent data structures 解説 色々ある「永続配列」「永続セグメントツリー」「永続Union-Find」「永続木」「永続平衡二分木」「永続WaveletMatrix」参考 部分永続。最新版のみ変更可能、Undoができる機構がある。履歴は一直線。 完全永続。昔のどのバージョンからでも変更でき、履歴が全て残っている。履歴は木。 永続配列があれば永続Union-Findが作れるらしい 永続配列は永続木があれば作れるらしい 部分永続Union-Findの資料 部分永続はスタックで履歴を残しておいて逆操作をしていって戻すやり方がある（要出典）多分そのやり方でやってる 平衡二分木を永続化するときは赤黒木が最良らしい 問題 完全永続セグメントツリー SPOJ D-query CF429 Destiny (要素add,特殊クエリ) 部分永続セグメントツリー CS
最小費用流の負辺除去 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
つい最近まで最小費用流の負辺除去、「なんか上手いことやれば出来ることもあるらしい」程度の認識だったんですが、ちゃんと考えてみたら自明やんってなったので書いておきます。 この記事を読めば多分、自明かどうかはともかくとして、かなり見通しがよくなるのでは思います。 （2019-06-27に若干書き換えました） 追記 (2021-08-15)： ポテンシャルを求めるのが簡単な場合にはそれを使って負辺除去する方が楽です。 この記事の方法はグラフが複雑だったり、思考停止したいとき用かなぁ。 例題 最小費用流への認識 最小費用流は「始点 S から終点 T に水を流す」という問題に見えがちですが、それは少し本質とずれています。 水の例えを用いつつ言うならば「頂点間で水をやりとりして過不足を補い合う」という感じでしょうか。 実装の際に始点と終点があった方が分かりやすいことがあるだけで、定義上は必要なものでは
絵で理解するWord2vecの仕組み - Qiita
皆さん、Word2vec の仕組みはご存知ですか？ Word2vec は gensim や TensorFlow で簡単に試せるので使ったことのある方は多いと思います。しかし、仕組みまで理解している方はそう多くないのではないでしょうか。そもそも本家の論文でも内部の詳細については詳しく解説しておらず、解説論文が書かれているくらいです。 本記事では Word2vec のモデルの一つである Skip-Gram について絵を用いて説明し、概要を理解することを目指します。まずは Skip-Gram がどのようなモデルなのかについて説明します。 ※ 対象読者はニューラルネットワークの基礎を理解しているものとします。 どのようなモデルなのか？ Skip-Gram はニューラルネットワークのモデルの一つです。Skip-Gram は２層のニューラルネットワークであり隠れ層は一つだけです。隣接する層のユニット
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
アルゴリズムが世界を変える Season 4.0
組合せ最適化でクリークを解く - Qiita
