木の半径、直径、中心、重心
最近よく見聞きする木の用語を整理しておく。 離心数（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)個の交わらない区
フィボナッチヒープ - 宇宙ツイッタラー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 さんのスライド → プログラミングコンテ
子から異なる2つを選ぶ感じの木DPを解くアレ - よすぽの日記
子から異なる2つを選ぶ感じの木DPを解くアレを解くテクニックを紹介します。 D: Longest Path - Indeedなう（オープンコンテスト） | AtCoder とかが簡単に解けたりします 頂点0を根とする根付き木について 頂点iはa[i]を持つ(a[i] >= 0) 頂点iそれぞれについて、b[i] = a[i] + max(0, max(b[x] ただしxはiの子), max(b[x] + b[y] ただしx, yはどちらもiの子でかつx != y)) b[0]を求めよ という問題を考えます つまり、b[i]は子供から0, 1, 2個選んだ時のb[選んだ頂点]のsumのmaxにa[i]を足したものですね vector<int> g[MAX_V]; //g[p]は頂点pの子供を入れたvectorとする int a[MAX_V], b[MAX_V]; void dfs(int p
競技プログラミングにおける全方位木DP問題まとめ - はまやんはまやんはまやん
全方位木DP よく分かる解説 問題 CSA Connected Tree Subgraphs [解説 CF397 Tree Folding CF405 Bear and Tree Jumps AtCoder Driving on a Tree CSA Root Change EDPC Subtree 解説 CF Centroids 解説1 解説2 解説3 CF395 Timofey and a flat tree CF302 Road Improvement 解説 yukicoder No.768 Tapris and Noel play the game on Treeone 解説 違うけど方針が似ている問題 CF Nearest Leaf
CS Academy: Connected Tree Subgraphs - pekempey's blog
問題ページ modified 2018年12月21日 map を使ったこれはあやまりですので、キをつけてください。 modified 2018年12月17日 map を使うと書きやすいらしい。たとえば height を求めるには次のように書けばよい。 map<int, int> dp[100000]; vector<int> g[100000]; void dfs(int u, int p) { if (dp[u].count(p)) return; dp[u][p] = 0; for (int v : g[u]) if (v != p) { dfs(v, u); dp[u][p] = max(dp[u][p], dp[v][u] + 1); } } 解法 $O(n^2)$ 解法は TDPC の木という問題と同じ。 dp[v]:=vの部分木の番号の振り方を計算する。子が a,b,c,d だ
木の直径を求めるアルゴリズム - ペケンペイのブログ
注意：議論が洗練されておらず、真面目に読むべき記事ではありません。信頼できそうなグラフ理論の書籍を読んだほうが良いと思います。ウェブ上で閲覧できる資料としては以下があり、そこの References を辿ると良いでしょう。 http://mathworld.wolfram.com/GraphCenter.html 中心が高々 2 個であることと、2 個あるならばそれらは隣接していることは F. Harary の ''Graph Theory'' に証明があります。p. 35 の Theorem 4.2 Every tree has a center consisting of either one point or two adjacent points. がそれです。頻繁に参照される記事ではありませんので、この記事を改訂する予定は今の所ありませんが、幾らか思うところがあるので希望があれば
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
Aho Corasick 法 - naoyaのはてなダイアリー
適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。 この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析、Wikipedia やはてなキーワードのキーワードリンク処理などが代表的な応用例です。 Aho Corasick 法 任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひと
Segment Trees
Motivational Problems: http://www.spoj.pl/problems/BRCKTS/ http://www.spoj.com/problems/GSS3/ http://www.spoj.com/problems/HORRIBLE http://www.spoj.pl/problems/IOPC1207/ https://www.spoj.com/problems/GSS2/ http://www.spoj.com/problems/SEGSQRSS/ http://www.spoj.com/problems/ORDERSET/ http://www.spoj.com/problems/HELPR2D2/ http://www.spoj.com/problems/TEMPLEQ Segment trees (shortened as segtrees), a
Heavy Light Decomposition
Long post with lot of explanation, targeting novice. If you are aware of how HLD is useful, skip to “Basic Idea”. Why a Balanced Binary Tree is good? Balanced Binary Tree A balanced binary tree with N nodes has a height of log N. This gives us the following properties: You need to visit at most log N nodes to reach root node from any other node You need to visit at most 2 * log N nodes to reach fr
キャッシュフレンドリーな二分探索 ー データ構造を再考する | POSTD
現代のコンピュータのアーキテクチャに搭載されている高速のキャッシュメモリは、 参照の局所性 に優れた(＝一連のものとしてアクセスした要素が、互いに近いメモリのアドレスに配置されている)データ構造を好みます。これは、 Boost.Containerの平坦な（ツリー状ではない）連想コンテナ のようなクラスを陰で支えている理論的根拠です。要素を連続的に（かつ順序だてて）保存すると同時に、標準的なC++ノードベースの連想コンテナの機能性をエミュレートします。以下にあるのは、要素が0から30の範囲の時、 boost::container::flat_set の中で 二分探索 がどのように行われるのかを示した例です。 探索で目的の値を絞り込むにつれて、アクセスされる要素は次第に近くなっていきます。そのため、最初のうちは大きな距離を飛び越えていくような感じであっても、参照の局所性は このプロセスの最後の
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://www.npca.jp/works/magazine/2015_5/
The Unhealthy Obsession with Tree Questions