Qiita に移植しました 重みつき Union-Find 木とそれが使える問題のまとめ、および、牛ゲーについて
hoge木 - けんちょんの競プロ精進記録
Qiita に移植しました 重みつき Union-Find 木とそれが使える問題のまとめ、および、牛ゲーについて
遅延評価セグメント木をソラで書きたいあなたに - hogecoder
最下段が N-1 から始まるのと、親と子の取得方法がわかってればセグ木は書けます (ホンマか？)— 009_tsutaj@CODE FESTIVAL (@_TTJR_) 2017年3月29日 この記事は前記事: 「セグメント木をソラで書きたいあなたに」の続編です。セグ木をソラで実装するのはまだ厳しい・・・という方はまずはこちらの記事を読んでみてください。 tsutaj.hatenablog.com この記事は「セグメント木はソラで書けるけど、遅延評価セグ木は書けない・・・」という人を対象にしています。 遅延評価って何？ まず遅延評価について軽く説明しておきます。 遅延評価というのは、値の伝播*1を遅らせるテクニックです。これは区間に対して更新を行うときに必要になる時が多いです。例えば、値の更新を普通のセグメント木でやろうとしたとき、範囲の長さを とするとこの範囲の長さだけクエリを呼ばなけれ
グランディ数 - zukky162のブログ
Competitive Programming Advent Calendar 2016 - Adventarの12日の記事になります。 この記事では、競技プログラミングの問題にたまに出てくる、グランディ数についての解説記事です。解説と言いつつ、ひたすら自己流の証明を書きなぐった記事みたいになってしまったので、読みづらいかもしれません・・・。内容としてはグランディ数の基礎的な部分しか扱っていないので、知っている人は読む必要がないかもしれません。 グランディ数を知ると何ができる？ 競技プログラミングでたまに見かける、2人で交互に行う系のゲームの勝敗判定を行う問題の解法によくグランディ数が使われます。実装自体はとても簡単なので、知らないと全くわからないが、知っていると超簡単になる傾向があります。なので知っていて損ではないと思います。グランディ数自体はとても面白いので、少し興味があれば知っておく
日本の中心はどの県だ？グラフ理論（ネットワーク）の基本的な諸概念 - アジマティクス
Ｑ：これは何の構造を表しているでしょう？ グラフ理論 上の構造のように、頂点（ノードともいいます）の集まりと、２つの頂点をつなぐ辺（エッジともいいます）の集まりでできたもののことを「グラフ」あるいは「ネットワーク」と呼び*1、このような構造を研究する分野こそが「グラフ理論（Graph theory）」です。今回はそんなグラフを使うと、身近なものの新たな側面が見えてくる話。 （余談ですが「グラフ」という用語は、数学だと関数のグラフとか円グラフみたいなやつもあって検索精度が悪いです。グラフ理論に関してわからないことがあった場合に「グラフ ○○」や「グラフ理論 ○○」とググるよりも、「ネットワーク ○○」とググったほうが得たい情報にリーチしやすいというライフハックが知られています） さて、冒頭のグラフです。グラフ理論の知識なんかひとつもなくても、このグラフから読み取れることはいくつもあります。例
二部グラフの最大マッチングと増加道 | 高校数学の美しい物語
グラフとは，点の集合と枝の集合からなる「つながり方」を表すモデルです。 二部グラフとは，点が 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 後手
Grundy number - ペケンペイのブログ
Grundy number (Nimber) について説明する。 Nimber - Wikipedia Sprague–Grundy theorem - Wikipedia Grundy number はゲームにおいて先手・後手必勝の判定に使われる。Grundy number は「現在の状態から遷移できる状態達の Grundy number の中に存在しない最小の自然数」として再帰的に定義される。形式的に定義するならば、ゲームの状態全体 $S$ に対して Grundy number は関数 $g\colon S \to \mathbb{N}$ であり以下で定義されるものである。 \begin{align} g(x) = \mathrm{mex}\{g(x') \mid x' \in N(x) \} \end{align} ここで $N(x)$ は $x$ から遷移できる状態全体の集合であり
木の重心列挙アルゴリズム - Learning Algorithms
木の重心列挙アルゴリズム English version is available here. 木の重心を列挙するアルゴリズムです。重心の性質をよく知っている方にとっては自明な木$dp$を実装するだけだと思います。 これで $verify$ しています。計算量は $O(n)$ です。 中のアルゴリズムとしては、基本的には各頂点についてその頂点からのびる部分木のサイズがすべて $\cfrac {n}{2}$ 以下であるような頂点を求めているだけです。 では、そのような頂点が $3$ 個以上存在しないことを示しておきます。 まず、重心が $2$ 個あるとき、それらは必ず隣接していることを示します。 仮に以下の画像のように、重心 $u$ と重心 $v$ が存在して、これらが隣接していないと仮定します。すると $u$ と $v$ のパス上には必ず一つ以上の頂点が存在することになります。そのうちの一
木の半径、直径、中心、重心
最近よく見聞きする木の用語を整理しておく。 離心数（eccentricity） 節点vから最も離れた節点をwとする。 このときパス(v, w)の長さをvの離心数と呼ぶ。 記号で表すときは、ε(v)と書く。 木の半径（radius） 離心数の最小値。つまりmin_(v ∈ V) ε(v)。 木の中心から最も遠い節点までの距離とも言える。 木の直径（diameter） 離心数の最大値。つまりmax_(v ∈ V) ε(v)。 最も遠い2点間の距離と言える。 木の中心（center） 離心数が最小の節点。 最も離れたところにある節点までの距離が最小の節点なので、なんとなくグラフの中心にありそうなイメージと合致する。 木の重心（centroid） 節点vを根とした木を考える。 vの直接の子以下の最大部分木の節点数が最小となる場合、vを木の重心と呼ぶ。 木を再帰的に分割して何か処理をしたい場合、木の
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
Segment Treeをちょっと高速化したい - komiyamの日記
Competitive Programming Advent Calendar Div2013の12月2日の分です。 ときどき脱線しながらも主にsegment treeの再帰展開について書こうと思います。 はじめに segment treeの資料といえば蟻本やiwiさんのスライドが非常に分かりやすくお勧めです（定番中の定番ですね）。この資料で使われている図をイメージしながら読んでください。同じくiwiさんの平衡二分探索木のスライドもぜひ目を通しておきましょう。 これら以外にもsegment treeについてまとめたブログ記事などは検索すれば色々引っかかります。去年や今年のAdvent Calendarでも初学者向けの記事があるようです。初学者向けの詳しい解説はそちらをご覧ください。 私なりにsegment treeの動作原理を短くまとめると、「区間をたかだかO(log n)個の交わらない区
アルゴリズム - 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 【遅延伝播セグメント木とは】 ある列に対して連続する区間に対して更新と取得ができるデータ構造である。以降遅延セグ木と略す。 前回のブログでは、要素の集合 と写像 からなるモノイド を考えた。 遅延セグ木では、新たに作用素の集合 と写像 からなるモノイド を追加し、 さらに作用と
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
アルゴリズムが世界を変える Season 4.0
組合せ最適化でクリークを解く - Qiita
