問題文 https://atcoder.jp/contests/abc378/tasks/abc378_f 問題概要 $n$ 頂点の木 $T = ( V, E )$ が与えられる． $T$ に辺を $1$ 本追加して得られるグラフはちょうど $1$ つの閉路をもつが，そのようなグラフの内，以下の条件をともに満たすものの個数を…

問題文 https://atcoder.jp/contests/abc368/tasks/abc368_d 問題概要 $n$ 頂点の木 $G = ( V, E )$ と $V$ の部分集合 $W$ が与えられる．$G$ の $W$ をターミナルとする最小 Steiner 木の頂点数を求めよ． 制約 $1 \leq |W| \leq n \leq 2 \times 10^5$

問題文 https://atcoder.jp/contests/abc357/tasks/abc357_e 問題概要 $n$ 頂点の Functional Graph $G = ( V, E )$ が与えられる．具体的には， $V = \{ 1, 2, \dots, n \}$ $|V| = |E| = n$ $A_i \in \{ 1, 2, \dots, n \}$ な $n$ 項の列 $A$ が与えられ…

問題文 https://atcoder.jp/contests/abc350/tasks/abc350_d 問題概要 $1$ から $n$ で番号付けられた $n$ 人の人がいて，$m $ 組の友好関係がある．友好関係は $m $ 項からなる列 $A, B$ によって表され，$i$ 番目の友好関係は人 $A_i$ と人 $B_i$ が友人同…

問題文 https://atcoder.jp/contests/abc335/tasks/abc335_e 問題概要 $n$ 頂点 $m $ 辺からなる連結な単純無向グラフ $G = ( V, E )$ があり，$i$ 番目の辺は頂点 $V_i$ と $U_i$ を双方向に結んでいる．また，整数列 $A = \langle A_1, A_2, \dots, A_n \r…

問題文 https://atcoder.jp/contests/abc292/tasks/abc292_e 問題概要 単純有向グラフ $G = ( V, E )$ が与えられる． 以下の操作を考える． グラフ $\hat G = ( V, \hat E \leftarrow E )$ を用意する 以下の操作を可能な限り適用する 相異なる頂点 $u, v, …

問題文 https://atcoder.jp/contests/abc267/tasks/abc267_e 問題概要 $N$ 頂点 $M $ 辺の単純無向グラフ $G$ が与えられ，頂点 $i$ には整数 $A_i$ が書かれている． ここで，一つの頂点を削除する以下の操作を $N$ 回繰り返すことでグラフを空にすることを…

問題文 https://atcoder.jp/contests/abc245/tasks/abc245_f 問題概要 単純有向グラフ $G = ( V, E )$ が与えられる． 頂点 $v \in V$ であって，$v$ を始点として $G$ 上で無限に（辺に沿った）移動を繰り返すことができるものの個数を求めよ． 制約 $1 \le…

問題文 https://atcoder.jp/contests/arc106/tasks/arc106_b 問題概要 $N$ 頂点 $M $ 辺からなる単純無向グラフ（連結とは限らない）が与えられる．はじめ，各頂点 $i$ には整数 $a_i$ が書かれている．ここで，次の操作を任意回行うことができる． 辺 $\{ u…

問題文 https://atcoder.jp/contests/abc173/tasks/abc173_f 問題概要 $N$ 頂点の木があって，頂点は $1$ から $N$ の整数で番号付けされている．また，$i$ 番目の辺は 2 点 $u_i, v_i$ を結んでいる． 整数 $L, R$ ($1 \leq L \leq R \leq N$) について，関…

問題文 https://community.topcoder.com/stat?c=problem_statement&pm=14000&rd=16624 問題概要 数のリスト $\mathit{ num }$ が与えられる．$| \mathit{ num } | = N$ とする． $N$ 頂点の木であって，$i$ 番目の頂点の次数が $\mathit{ num }_i$ であるよ…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13990&rd=16550 問題概要 $N$ 頂点の木と 2 種類のトークンを使った 2 人ゲームをする．プレイヤーを A, B として，A は赤いトークンを，B は青いトークンを使う． 木の頂点は $0$ から $…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13955&rd=16515 問題概要 $N$ 頂点の木があって，各頂点は $0$ から $N - 1$ で番号付けられている．木の情報は配列 $\mathit{ parent }$ で与えられ，有効な $i$ について，頂点 $i + 1$…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13667&rd=16314 問題概要 正整数 と，頂点数・辺数が共に の無向グラフが与えられる．辺の情報は 2 つの配列 で与えられ，各 に対し，2 頂点 を結ぶ辺が存在する． このグラフから辺を 1 …

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13648&rd=16312 問題概要 頂点の（連結とは限らない）単純無向グラフが与えられる．グラフは の文字の行列 として与えられる． が 'Y' のとき，2 頂点 を結ぶ辺が存在することを表し，'N'…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13628&rd=16278 問題概要 今，無限に広い 2 次元空間の原点にいる．1 回の移動では 4 近傍（上下左右）のいずれかの方向に距離 1 移動することができる． 平面上のいくつかの座標はブロッ…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13627&rd=16278 問題概要 今，無限に広い 2 次元空間の原点にいる．1 回の移動では 4 近傍（いずれかの座標軸に平行な方向）のいずれかの方向に距離 1 移動することができる． 平面上のい…

問題文 http://codeforces.com/contest/500/problem/B 問題概要 サイズ の順列 及び， 行列 が与えられる．また， 及び が成り立つ． 二つの整数 について， であるときに限り， と を交換することができる．任意回の操作で作ることができる列の内，辞書式順…

問題文 http://codeforces.com/contest/500/problem/D 問題概要 頂点からなる重み付きの木が与えられる．辺の情報は 3 つの配列 によって与えられ， 番の辺は 2 頂点 間を結び，その重みは である．また， を，2 頂点 間の単純道のコストとする． 今，以下の…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13523&rd=16085 問題概要 不思議の国の王様は，底の高い靴を履くのが好きである． 不思議の国には 個の町と，それらを結ぶいくつかの道路がある．道路の情報は 3 つの配列 によって表され…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13519&rd=16081 問題概要 いくつかのロウソクが、木（ネットワークトポロジー的な意味で）状に配置されている。この木を使って時間を測ることを考える。計測の手順は、まず葉にあたるいく…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13416&rd=16078 問題概要 頂点からなる重み付きの木が与えられる。辺に関する情報は要素数が の三つの配列 によって与えられ、 番目の辺は を距離 で結んでいる。 この木に対し、一つの辺…

問題文 http://codeforces.com/contest/472/problem/D 問題概要 の行列 が与えられる。 頂点からなる木であって、頂点 間の距離が となるものは存在するか？ なお構成される木は、無向・重み付きであって、辺重みは全て正である。

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13242&rd=16009 問題概要 内の整数からなる集合 と、 上の写像 がある。 は配列 によって表され、 である。 また、 の部分集合 が invariant set であるとは、次の条件を満たすときである…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13237&rd=16009 問題概要 特殊な電気回路について考える。回路の構成は文字列で表される。 まず、単一の素子は一つの回路である。これは、文字列 "X" として表される。 また、二つの回路…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13197&rd=15857 問題概要 N 頂点からなる連結な重み付き無向グラフが与えられる。重みは非負整数である。 頂点を 1 から N で番号付けたとして、頂点 1 から頂点 N への最短経路（単純道…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13193&rd=15855 問題概要 有向重み付き完全グラフ G = ( V, E ) と、正整数 T が与えられる。全ての頂点対 ( s, t ) について、s -> t の最短路を考える（ある ( s, t ) に対し最短路が複…

問題文 http://arc022.contest.atcoder.jp/tasks/arc022_3 問題概要 N 頂点からなる木が与えられる。この木の最遠頂点対を一つ出力せよ。

問題文 http://code.google.com/codejam/contest/2994486/dashboard#s=p2 問題概要 N 個の街があって、それぞれの街は固有の郵便番号をもっている。また、いくつかの街の間は空路で結ばれていてる。 全ての街を訪れることができるように飛行機を予約したいが…

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=10541&rd=15851 問題概要 有向グラフ G が family graph であるとは、次の条件を充足することであるとする。 各頂点は男性か女性である 頂点 v から頂点 u に有向辺があるとき、v は u の…