torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

グラフ

AtCoder Beginner Contest 335, E : Non-Decreasing Colorful Path

問題文 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…

AtCoder Beginner Contest 292, E : Transitivity

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

AtCoder Beginner Contest 267, E : Erasing Vertices 2

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

AtCoder Beginner Contest 245, F : Endless Walk

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

AtCoder Regular Contest 106, B : Values

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

AtCoder Beginner Contest 173, F : Intervals on Tree

問題文 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$) について,関…

TopCoder SRM 674, Division 1, Level 1 : VampireTree

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

TopCoder SRM 670, Division 1, Level 2 ( Division 2, Level 3 ) : Treestrat

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

TopCoder, Single Round Match 666, Division 1, Level 1 : WalkOverATree

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

TopCoder, Single Round Match 650, Division 2, Level 3 : TheKingsRoadsDiv2

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

TopCoder, Single Round Match 648, Division 2, Level 2 : Fragile2

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

TopCoder, Single Round Match 646, Division 2, Level 2 : TheGridDivTwo

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

TopCoder, Single Round Match 646, Division 1, Level 2 : TheGridDivOne

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

Good Bye 2014, B : New Year Permutation

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

Good Bye 2014, D : New Year Santa Network

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

TopCoder, Single Round Match 642, Division 2, Level 3 : TallShoes

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

TopCoder, SRM 638, Division 2, Level 3 : CandleTimerEasy

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

TopCoder, SRM 635, Division 2, Level 3 : LonglongestPathTree

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

Codeforces #270, D : Design Tutorial: Inverse the Problem

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

TopCoder SRM 628, Division 2, Level 3 : InvariantSets

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

TopCoder, SRM 628, Division 1, Level 2 : CircuitsConstruction

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

TopCoder, SRM 624, Division 1, Level 2 : DrivingPlans

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

TopCoder, SRM 622, Division 1, Level 1 : BuildingRoutes

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

AtCoder Regular Contest #022, C : ロミオとジュリエット

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

Google Code Jam 2014, Round 1B, C : The Bored Traveling Salesman

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

TopCoder, SRM 618, Division 1, Level 1 : Family

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

TopCoder SRM 611, Division 1, Level 2 : Egalitarianism2

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13008&rd=15844 問題概要 平面上に N 個の点がある。これらの点を頂点とし、二点間にそのユークリッド距離に等しい重みの辺を張ったグラフを考える。このグラフの全域木であって、辺重み…

TopCoder SRM 612, Division 1, Level 2 : SpecialCells

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12354&rd=15845 問題概要 出題者と回答者の二人で行う次のようなゲームをする。 出題者が、平面上の整数座標にいくつかの「特別な点」を設定する(特別な点は相異なる) 出題者は、特別な…

Codeforces #237, C : Restore Graph

問題文 http://codeforces.com/contest/404/problem/C 問題概要 整数 n, k と数列 d が与えられる。以下の condition を満たすグラフを一つ示せ。存在しない場合は -1 で示せ。 頂点数が n 全ての頂点について、次数は k 以下 ある頂点 v を選んだとき、v か…

TopCoder SRM 612, Division 1, Level 1 : EmoticonsDiv1

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=10543&rd=15845 問題概要 丁度一つの顔文字を含むテキストファイルを、次の三種類の操作によって編集する。 全ての文字列をクリップボードにコピーする クリップボードの文字列をバッファ…