torus711 のアレ

主に競技プログラミングの問題について書きます

グラフ

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 問題概要 丁度一つの顔文字を含むテキストファイルを、次の三種類の操作によって編集する。 全ての文字列をクリップボードにコピーする クリップボードの文字列をバッファ…

TopCoder SRM 594, Division 1, Level 2 : FoxAndGo3

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12808&rd=15706 概要 '.', 'x', 'o' からなる盤面が与えられる。 盤面上のセル同士が辺を共有するとき、それらは隣接していると見做される。 与えられる状態で 'o' 同士は隣接していない…

Codeforces #203, Division 2, B : Resort

問題文 http://codeforces.com/contest/350/problem/B 概要 N 頂点からなる有向グラフがあり、各頂点には 0 または 1 の属性が付与されている。 各頂点について、それを終点とする辺の始点が与えられる。 次の条件を満たすパスの内、長さが最大のものを一つ…

TopCoder SRM 591, Division 1, Level 1 : TheTree

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12746&rd=15703 概要 次の制約を満たす木の最大の直径を求めよ。 一つのノードを選び、これを V とする V から最も遠いノードへの距離を D とする x ( 1 ≦ x ≦ D ) について、V から距離 x…

Codeforces #200, Division 2, B : Simple Molecules

問題文 http://codeforces.com/contest/344/problem/B 概要 三頂点からなるグラフがある。 このグラフは多重辺を許可し、ループを許可しない。 グラフの各頂点について、次数が指定される。 その制約を満たすグラフを構築できるならば、そのときの辺の張り方…

TopCoder SRM 589, Divisin 1, Level 2 : GearsDiv1

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12729&rd=15701 概要 N 個の歯車があり、それぞれの色は赤、緑、青のいずれかである。 噛み合っている歯車どうしは、互いに逆向きにしか回転できない。 また、同じ色の歯車は同じ方向に回…

Codeforces #192, Division 2, B : Road Construction

問題文 http://codeforces.com/contest/330/problem/B 概要 整数 N と、M 個の数のペア が与えられる。 次の条件を満たす N 頂点の無向グラフを構築せよ。 全ての頂点対について、二点間距離は二歩以下 二点 間には辺が無い

TopCoder SRM 584, Division 1, Level 1 ( Division 2, Level 2 ) : Egalitarianism

概要 N 人の市民がいて、それぞれの友達関係が与えられる。 友達同士であるような二人の市民について、その所持金の差が d 以内になるようにしたとき、任意の二人の市民(友達同士でなくてもよい)の所持金の差の最大値はいくらになるか求めよ。 解が無限大…

TopCoder SRM 583, Division 1, Level 1 : TravelOnMars

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12608&rd=15503 概要 リング状に N 個の街がある。 i 番目の町からは距離 以内の街へ一回で移動できる。 スタート地点とゴール地点が与えられたとき、最小で何回移動する必要があるか求め…

TopCoder SRM 583, Division 1, Level 2 : TurnOnLamps

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12606&rd=15503 概要 N 頂点からなる木があり、木の各辺には 0 か 1 が割り当てられている。 この木に対して、二頂点を結ぶパス(一意に定まる)上の辺の数字を入れ替える操作ができる。 …

TopCoder SRM 581, Division 1, Level 2 : TreeUnion

概要 V 個の頂点から成る二つの木 T1, T2 が与えられ、この二つを V 本の辺で結ぶ。 より詳しくは次の手順で辺を張る。 0 ? V - 1 の順列をランダムに一つ選び P とする 各 i ( 0 このとき、相異なる K ( 3

Codeforces #182, Division 2, D : Yaroslav and Time

問題文 http://codeforces.com/contest/302/problem/D 概要 XY 平面上に N 個の点があり、最初 1 番( 1-indexed )の点にいて、n 番の点に移動したい。 点から点に移動するとき、そのマンハッタン距離 * d の費用がかかる。 1 番と n 番以外の点では、 だけ…

TopCoder SRM 573, Division 1, Level 1 : SkiResorts

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12468&rd=15493 概要 あるスキー場には、N 箇所の "場所" があり、いくつかの道によって繋がれている。 スキーでの移動は、同じ高さの場所か、より低い高さの場所にのみ可能である。 各場…

Codeforces #170, Division 2, C : Learning Languages

問題文 http://codeforces.com/contest/278/problem/C 概要 ある会社には n 人の従業員がおり、m 個の公用語がある。 一人の従業員に一つの言語を教えるコストが 1 である。 各社員が使える言語の情報が与えられるので、全ての社員が互いに(他の社員に通訳…

AtCoder Regular Contest #011, C : ダブレット

問題文 http://arc011.contest.atcoder.jp/tasks/arc011_3 概要 ある単語について、文字を一文字置換する操作が許される。 与えられた辞書を使って、start から last まで変換するときの手順を求めよ。

TopCoder SRM 566, Division 1, Level 1 : PenguinSledding

概要 グラフの頂点数と辺の情報が与えられる。 「このグラフを二次元平面上にどのように配置しても辺が交差しない」ような辺の選び方の総数を答えよ。

Codeforces #149, Division 2, C : King's Path

問題文 http://codeforces.com/contest/242/problem/C 概要 × のチェス盤にキングが置かれている。 キングを ( x0, y0 ) から ( x1, y1 ) まで移動させたい。 使用可能なセルの情報が与えられるので、最小の移動回数を出力せよ。 移動できない場合は -1 を出…