問題文 Design Tutorial: Inverse the Problem 概要 $n$ 頂点の有向グラフの隣接行列 $A$ が与えられる. この行列が各辺に重みがついた無向グラフであり, 木を表していれば YES を, そうでなければ NO を出力せよ. 制約 $n \leqq 2000$

問題 : Coloring Tree概要 : $n$ 頂点からなる根付き木のそれぞれのノードに色がついている. 頂点$v$ を根とする部分木にある, 異なる色の個数を数えるクエリに$m $ 個答えよ.$1 \leqq n \leqq 10^5$ $0 \leqq m \leqq 10^5$ $1 \leqq v \leqq n$ $1 \leqq$ …

問題 : Marked Ancestor問題概要 : 大きさ$N$ の木が与えられる. 最初頂点$0$ は赤色で, その他の頂点は青色である. 次の$Q$ 個のクエリに答えよ :・頂点$v$ の色を赤色に変える. ・頂点$v$ から赤色の先祖ノードのうち, もっとも近いものの番号をこたえる.$…

問題 : Marked Ancestor問題概要 : 大きさ$N$ の木が与えられる. 最初頂点$0$ は赤色で, その他の頂点は青色である. 次の$Q$ 個のクエリに答えよ :・頂点$v$ の色を赤色に変える. ・頂点$v$ から赤色の先祖ノードのうち, もっとも近いものの番号をこたえる.$…

問題文 : Xenia and Tree概要 : 大きさ$n$ の木が与えられる. 最初頂点0 は赤色で, その他の頂点は青色である. 次の$m$ 個のクエリに答えよ :・頂点$v$ の色を赤色に変える. ・頂点$v$ から赤色のノードまでの最短距離を求める.$1 \leqq n,\ m \leqq 10^5$

問題文 : Minimum Spanning Tree概要 : 無向重み付きグラフ$G(V, E)$ が与えられる. すべての$e \in E$ について, $G - e$ の最小全域木の重さを求めよ.$1 \leqq n \leqq 10^5$ (頂点数) $1 \leqq m \leqq 2 \times 10^5$ (辺数)

問題文 : World Eater Brothers問題概要 :$N$ 頂点からなる有向全域木$G$ が与えられる. 高々2 つの頂点を選んで, この頂点から他の頂点への有向パスが存在するようにするために変えなければならない辺の向きの最小値を求めよ.$N \leqq 3000$

問題文 : Book of Evil 問題概要 : 大きさ$N$ の木で, $M $個の印をつけた頂点すべてからの距離が$d$ 以内であるものの個数を求めよ.$N , M \leqq 10^5$

問題文 : Running Away from the Barn問題概要 : 大きさ$N$ の木が与えられる. 距離が$L$ 以内の自分の子孫に当たるノードの個数を, すべてのノードについて求めよ. $N \leqq 200000$

問題文 : 倉庫番解法 : 「倉庫番の逆」を考える. すなわち, 目標地点から箱を引っ張りまわすBFS を考える. 箱の置き方がO(MN) 個, 隣接する頂点がたかだか4 個であるため, 状態数はO(MN) である.各状態に遷移したら, 答えには連結成分の大きさを足してやれば…

問題文 : 活字印刷機解法 : Trie 木上の探索を行う. 最も長い文字を最後にたどれば, その文字の文の型を回収しなくていいため最短ですべての文字を打ち終えることが出来る. (他の文字はどのみち回収しないといけないため). コード : #include <cstdio> #include <cstdlib> #in</cstdlib></cstdio>…

問題文 : SALT TREE XV解法 : (qnighy さんのものをチラッと見てしまったので, 考えながら書いた所をまとめる.)まず, ある状態から, 辺の数が0 で頂点の数が0 に出来れば自分の勝利であることを確認する. また, 辺の数が0 の状態への遷移は, 頂点が1 個の時…

問題文 : 報告解法 :まず, 問題文の例を解析する. 報告先でサイクルになっている頂点達について, サイクル内の頂点v に仕事の報告が来れば, 必ず他の頂点でも仕事の報告が来ることがわかるので, 閉路を潰す.次に, 閉路を潰して出来たグラフの逆辺からなるグ…

問題文 : 忍者の派遣解法 : 各頂点でpriority queueを持ち, dfs を行い, 給料のコストが大きい頂点から予算を超える分だけqueueから取り除く.これだけではO(N * NlogN) = O(N^2 log N) の計算量となってしまうが, 頂点を併合する際に, 短い方のqueueを併合す…

問題文 : Query on a tree II解法 :複数テストケースなので初期化する位置に気をつけないと死んでしまう問題 (ぼく死んでしまいました).距離を求めるところはeuler-tourっぽくやるのも, doubling でやるのもよしです. k 番目の頂点は, 根からの深さとlca(u, …

問題文 : Distance Queries解法 : Highwayの, 渋滞情報変更が無いだけのSimple LCAの問題.(その前に最小全域木化しなければならないが) Euler-Tour をしたが, これはDoubling でも普通に解けそう.全体でO((N+K)logN) くらいの計算量となる. 何も見ないで書け…

平衡2分探索木, いつか実装したいなあと思っていたので書いてみた. 疲れた.手元のアルゴリズムイントロダクションとか、ネットの資料を色々漁って書いた. やべえ.2-3-4木という木を2分探索木で表現すると赤黒木になるらしい. ただ、普通の赤黒木だと実装が結…

問題 : 巡回セールスマン問題解法 : 与えられたグラフは,(validなものであれば) 問題の制約通り, 有向木に辺をいくつか(最大501本)足したものとなる. また, 枝分かれや併合・子がある(となる)頂点が, 述べ 1000 個程度より多くあると, validなグラフが構成で…

問題文 : 委員会(pdf注意, 1-2ページ目)解法 : 各頂点ごとに, やる気の最大値をメモする. 答えは, やる気の最大値が最も大きい頂点となる. ある頂点のやる気の最大値は, 自分自身のやる気＋自分の子までのやる気の最大値のうち, 負で無いものの和, として求…

問題文 : 高速道路解法 : 次のように, 2つの木を考える. 辺の更新のクエリが来た時は, euler-tourを行った時に、それぞれの辺が上りだったか、下りだったかを覚えておき処理する.頂点uからvへ行くクエリが来た際は, u->lca(u, v)に行くときは逆辺の木, lca(u…

問題文 : Housewife Wind解法 : 頂点u, vの最小共通祖先をpとすると, cost(u, v) = cost(u, p) + cost(v, p) = cost(root, u) + cost(root, v) - 2 * cost(root, p)となる. rootからある頂点への距離は, 通った辺を相殺する形で, BITで管理することでO(log N…

問題文 : Cactus解法 : 答えは2^(パスs -> tまでの中にあるサイクルの数)になる(図を描いて考察すると分かる.) よって、サイクルを検出して、それを1つの頂点に圧縮する.頂点に圧縮する際に、根付き木にグラフを再構築すると, sとtのLCAをpとしておき s->pの…

問題文 : 地域解法 : C(x) : 距離x以下でM個の地域に分割できるか、とすると C(x)が成立すればC(x - 1)も成立するので、xについて二分探索を行う. 実際に距離xを超えるかは, 与えられたグラフを根付き木にし, 2つの辺によって結ばれる地域のコストの和を距離…