グラフ理論
問題 無向グラフが与えられる。ここから辺を一本取り除き、できた連結成分をA, Bとする。（A, Bの片方またはどちらも空かもしれない） グラフGに対してsum(G) = Σ{w(e)|e∈Gの辺}とする。ただしw(e)は辺eの重みである。 abs(sum(A) - sum(B))を最小化するよう…
問題 しりとりになっている英単語の列wiが与えられる。この列には次のような操作を好きなだけ行うことができる。 i＜jなるi, jについてwiとwjの先頭の文字が等しいとき、列からwi, wi+1, ..., wj-1を取り除く。 最小でいくつまで要素を減らせるか。 制約 単…
問題 無向木に一本だけ無向辺を足したグラフが与えられる。 次のQ個のクエリに答えよ。 aからbへのパスをなくすために最小で何本の辺を消せばいいか。 制約 グラフのサイズとクエリの数が両方10万以下。
問題 n頂点m辺からなる連結な無向グラフが与えられる。そのグラフに含まれる単純閉路（同じ頂点を二度通らないような閉路）の個数を求めよ。 制約条件 n≦10万 m≦n+15
問題 重み付きの有向グラフが与えられる。i番目の辺の向きを反転させたとき、1番から2番の頂点への最短路が 短くなる 変化しない 長くなる のいずれであるかをそれぞれ出力せよ。 制約条件 グラフの辺と頂点≦10万 辺の重みは正整数で10万以下
問題 日本語なので略 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1622&lang=jp
問題 n頂点からなる木がある。木には最初s[i]の値がかかれている。 次の操作をm回行う。 数字tiを手に入れる。捨てるか、好きな木の頂点cを選んで数字を置く。 頂点cにもともとあった数字はcの親に行く。cの親vにあった数字はvの親に行く。 ……と同様に根まで…
問題 n頂点m辺のグラフの全ての頂点を「直接良い状態にするか、良い道路を辿って良い頂点へ辿りつける」ようにしたい。 i番目の頂点が良い状態であるようにするにはci円 j番目の道路はaj, bjを結んでいて双方向に通行可能であり、良い道路にするにはcj円かか…
問題 1番のノードが根であるような木が与えられる。各ノードは値a[i]をもっている。 木に対して次のクエリを行うことができる。 1 x val : x番の頂点にvalを足す。x番の直接の子に-valを足す。x番の頂点の２代目の子孫にvalを足す３代目の頂点に-valを足す………
問題 n頂点からなる木が与えられる。 この木を、辺を一本ずつ書いていく。書いている途中の辺は全て連結であるようにしたい。 辺を書く順番は何通りあるかmod 10^9 + 7で求めよ。 制約条件 n≦1000
問題 n頂点m本の辺からなる重み付き無向グラフが与えられる。 m本の辺それぞれについて、 このグラフの最小全域木に含まれる場合とそうでない場合がある このグラフの最小全域木に必ず含まれる このグラフの最小全域木に含まれない のいずれかを判別せよ。 …
問題 N頂点からなる有向グラフが与えられる。 最初全ての頂点は白で、グラフにパス（同じ頂点を何度通ってもよい）を描くと、 パス上の頂点の色が全て黒になる。 この操作を２回できるとき、黒にできる頂点の個数の最大値を求めよ。 制約条件 N≦300
問題 N頂点からなる木に、交わらないK本のパスを書く書きかたは何通りあるか。mod 10^9 + 7で求めよ。 パスを書く順序は区別しない。 制約条件 N≦1000 K≦50
問題 日本語なので本文参照（http://tenka1-2014-quala.contest.atcoder.jp/tasks/tenka1_2014_qualA_e） 制約条件 h≦20000 w≦16
問題 無向木で表されるような島と橋が与えられる。 辺の重みが、橋を渡る時間であり、その橋を壊す時間である。（両者は等しい） 好きな島から出発し、橋を渡るか、今いる島につながっている橋を壊すかすることができる。 終了時には好きな島にいてよい。 全…
問題 n頂点からなる無向木が与えられる。最初1番の頂点だけが色つき。 この木に対して以下のクエリを処理せよ。 1 v : 頂点vに色をつける。 2 v : 頂点vに最も近い色つきの頂点の距離を出力する。 制約条件 n, クエリ≦100000
問題 日本語なので本文参照（http://kupc2014.contest.atcoder.jp/tasks/kupc2014_h）
問題 二次元平面上にn匹きつねがいて、 位置が(x[i], y[i]), パワーがd[i]. （何度でも）i番目のきつねにコスト1を支払うとそのきつねのパワーを1上げることができる。 きつねi, jは(iのパワー)+(jのパワー)がi, jのユークリッド距離以上ならば通信できる。 …
問題 n頂点からなる無向木が与えられる。 各頂点には重みwiがついている。重みの初期値が与えられる。 この木に対して次のようなクエリがq個来るので、答えよ。 t a b c t = 1のとき、木の頂点aから頂点bへのパス上にある頂点全ての重みをcに変更する。 t = …
問題 n頂点からなる無向木が与えられる。 この木の辺を何本か切断して、直径がそれぞれmaxDist以下であるような木いくつかにしたい。 最小でいくつの木に分ければよいか求めよ。 制約条件 n≦51 辺の長さ≦500 maxDist≦500
問題 N頂点からなる木A, Bがそれぞれ与えられる。 A, Bを次のようにしてつなぐ。 長さNの順列を等確率にランダムで一つ取り、これをP[i]とする。 Aのi番目の頂点とBのP[i]番目の頂点を辺で結ぶ。 こうしてできたグラフに、長さがちょうどkの単純閉路がいくつ…
問題 n頂点からなる木で、各頂点以下の部分木のサイズがc[i]であるような木であり、 葉以外の頂点では直接の子が二つ以上のものが存在するか、 存在するならYESを、そうでないならNOを出力せよ。 制約条件 n≦24
問題 n頂点からなる根付き木が与えられる。各頂点は最初0または1である。 このグラフに対して次の操作が好きなだけできる。 操作：好きな頂点vをえらび、vおよび、vの子孫uでdepth(u)-depth(v)が偶数の頂点uの0, 1を反転させる。 最終状態が与えられるとき、…
問題 無向木Gが与えられる。 Gの部分誘導グラフの木H, Iであって、HとIは同型かつdisjointであるものについて、 H + I の最大値を求めよ。 制約条件 G ≦50 部分誘導グラフは、部分グラフのうち辺を勝手に削除してはダメなやつ （元のグラフにあった辺の両端…
問題 次の性質をもつ自然数の集合Sをcoolであるとする。 全ての要素は0以上2^60未満 任意の異なるa, b∈Sについて(a & b) > 0 （bitwiseのand） 任意の異なるa, b, c∈Sについて(a & b & c) > 0 Sの部分集合subsetが与えられる。 サイズがNであって、subsetの…
問題 根付き木が与えられる。 この木に対して次の操作をK回行う。 K番目の操作を行ったとき、K番目の鳥がどこかの頂点に入れる確率を求めよ。操作： 根に鳥が来る。 鳥が今いる頂点に、他の鳥がまだいなければその頂点に入って終了。 そうでない場合、子を等…
問題 n人の人がいて、この中の二人が犯人。 n人のそれぞれに犯人は誰だと思うと聞いた結果、i番目の人はa[i]とb[i]と答えた。 犯人の候補(x, y)は、x = a[i]またはy = a[i]またはx = b[i]またはy = b[i]を満たすとき、 i番目の人の同意を得られる。 最低p人…
問題 50人の人がいて、n日間二人ずつプレゼントが渡される。 i日目にプレゼントを渡される人はchoice1[i]およびchoice2[i]である。 プレゼントはPieまたはDolphinで、どちらが渡されるかは決まってない。 全てのプレゼントを渡し終えた後、 各人が持っている…
問題 n頂点からなる有向グラフが与えられる。 整数Lに対して、このグラフ上の長さLのウォークの個数がO(L^k)で抑えられるような最小のkを求めよ。 そのようなLが存在しないとき、は-1を返せ。 制約条件 n≦50 長さlのウォークとは、グラフの頂点の列v1, v2, .…
問題 n頂点からなる木が与えられる。根は0番のノード。 各頂点には水槽がついている。お金をp円もっている。 最初にk個以下の好きなノードを選び、そのノードの水槽に1リットルずつ水を入れる。 次から全ての水槽が空になるまで以下の操作を繰り返す。 水槽…
