読者です 読者をやめる 読者になる 読者になる

torus711 のアレ

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

DFS

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 …

Good Bye 2014, D : New Year Santa Network

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

TopCoder, SRM 638, Division 1, Level 1 : ShadowSculpture

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13355&rd=16081 問題概要 複数の単位立方体からなる立体をつくる。立体を構成する単位立方体は、 の立方体を構成する単位立方体の部分集合である。 作られる立体は、2 つの条件を満たさな…

TopCoder SRM 628, Division 2, Level 2 : BracketExpressions

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13243&rd=16009 問題概要 "(){}[]" に含まれる 6 種類の括弧及び 'X' からなる文字列 が与えられる。'X' を括弧の内任意の一文字に(独立に)置換できるとき、括弧の対応を取ることができ…

TopCoder SRM 628, Division 2, Level 3 : InvariantSets

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

TopCoder, SRM 627, Division 1, Level 2 : GraphInversions

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13275&rd=16008 問題概要 頂点からなる無向・重み無しで連結なグラフが与えられる。辺の数は に等しく。 番目の辺は と を結んでいる。更に、各頂点には(頂点番号とは別に)整数値が割り…

TopCoder, SRM 622, Division 2, Level 3 : Subsets

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=10554&rd=15855 問題概要 正整数の(多重)集合 S が与えられる。この集合の部分集合 T であって、 であるものの数を求めよ。 であり、任意の a ∈ S について である。 また、答えは 32 b…

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 2, Level 3 : MovingRooksDiv2

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13065&rd=15851 問題概要 のグリッド状の盤面に、n 個の石が置かれている。また、盤面の各行・各列について、そこに置かれている石は丁度一つである。 この盤面上 ( r1, c1 ), ( r2, c2 )…

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 593, Division 1, Level 1 : HexagonalBoard

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12784&rd=15705 概要 ハニカム構造の盤面があり、いくつかのセルには印がつけてある。 次のようなグラフを考える。 印の付いたセルを頂点とする 印の付いた二つのセルが辺を共有するとき…

TopCoder SRM 571, Division 1, Level 2 : MagicMolecule

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=11705 概要 頂点に重み付けされた N 頂点からなる無向グラフが与えられる。 このグラフの部分グラフで、頂点数が 以上でクリークとなるものの重みの最大値を求めよ。

TopCoder SRM 571, Division 1, Level 1 : FoxAndMp3

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=12436 概要 Division 2, Level 2 : FoxAndMp3Easy と制約以外同一。