問題 N個の都市があり、n本の双方向に通行可能な道路で結ばれている。 i番目の道路はA[i]とB[i]を結んでいて、長さがD[i]である。 0番の都市からN-1番の都市へ、長さがちょうどTになるように道を通っていくことが出来るかを判別せよ。 制約条件 n, N≦50 D[i]…

問題 n頂点からなる無向木が与えられる。 各辺には重要か重要でないかと、初期状態でオンかオフかが与えられる。 木の二頂点を選び、その頂点を結ぶ最短パス上にある辺全てのオンオフを入れ替えるという操作を繰り返し、 重要な辺全てをオンであるようにした…

問題 n個の言語をマスターしたい。 最初はすべてレベル0で、9になったらマスター。 m個の講習を受けることができて、i番目の講習は、 言語a[i]のレベルがb[i]以上のときに、言語c[i]のレベルをd[i]まで上げることができて、e[i]の時間がかかる。 全ての言語…

問題 n人の人がいて、isFriend[i][j]が'Y'であるときi, jは友達同士である。 （i, jが友達のときj, iも友達である） 友達同士の所持金の差はd以下である。 このとき、n人の中で、所持金の最大値と最小値の差は、最大でいくらになるか。 最大値が存在しないと…

問題 n個の都市が双方向に通行可能な道路n-1本の道路で結ばれている。 任意の二都市をつなぐパスが存在する。 道路はいくつかが壊れている。 i番の都市を選ぶと、1番の都市からi番の都市へ行くのに必要な道路がすべて修理される。 最低いくつの都市を選べば…

問題 有向グラフがinterestingであるとは、 多重辺が存在しない。 一つの頂点cがあり、cはほかのどの頂点へも辺があり、どの頂点からもcへの辺がある。 頂点cには一本だけ自己辺がある。 c以外の頂点は入次数、出次数ともに2である ことを言う。 多重辺の存…

問題 Innaは整数の配列a[i]を使って次のようなことをする。 a[i]を一列に全部書く。これをa1[i]とする。 次に、n - 1個の(a1[i] and a1[i + 1])を書く。（ただしandはビット演算のand） これをa2[i]とする。 次にn - 2個の(a2[i] and a2[i + 1])を書く…… を…

問題 n匹のバクテリアがいて、（匹？）、1〜nと番号がついている。 最初のc[1]匹が種類1,次のc[2]匹が種類2……で、全部でk種類である。 バクテリアu[i]からv[i]へまたはv[i]からu[i]へ、エネルギーを移すことがx[i]ドルで可能である。 このような関係がm個与…

問題 日本語なので本文参照（http://utpc2013.contest.atcoder.jp/tasks/utpc2013_12） 重みつき有向グラフが与えられる。 各辺には+, -, =の3種類があって、 +の辺を通ると所持金が1円増える -の辺を通ると所持金が1円減る（所持金0のときは通れない） =の…

問題 日本語なので本文参照（http://utpc2013.contest.atcoder.jp/tasks/utpc2013_06） 自己辺多重辺がありうる重みつき有向グラフが与えられる。 このグラフの0番の頂点から0番の頂点へ戻る閉路（同じ辺や頂点を２度使ってもよい）の長さを、 長さが短い順…

問題 日本語なので本文参照（http://utpc2013.contest.atcoder.jp/tasks/utpc2013_09） 根つき木が与えられる。 各頂点には数字がついている。 それぞれの頂点に対して、 自分の親でも子でもない頂点のうち、自分に最も数字が近い頂点の数字を答えよ。 複数…

問題 日本語なので本文参照（http://utpc2013.contest.atcoder.jp/tasks/utpc2013_08） NxNの二次元グリッドに石がM個ある。 i番目の石は(x[i], y[i])にあって、強さの和がa[i]以上b[i]以下になるようレーザーを当てる。 レーザーはx軸に平行またはy軸に平行…

問題 日本語なので本文参照（http://utpc2013.contest.atcoder.jp/tasks/utpc2013_06） n頂点からなる無向グラフが与えられる。 最初全ての頂点は自分自身だけかならるグループで、クエリによりグループ同士をマージしていく。 グループA, Bをマージした後、…

問題 日本語なので本文参照（http://utpc2013.contest.atcoder.jp/tasks/utpc2013_03）二つの重みなし無向グラフが与えられるので、 それを一本の辺でつなぐとき、 できたグラフの直径を最小にするようにつないだときの直径 できたグラフの直径を最大にする…

問題 n頂点からなる木が与えられる。頂点には数字が記憶されていて、最初は全て0. これにq個のクエリが来るので処理せよ。 1 v x k 頂点vにxを足す。 vの子孫全てにvからの距離がdならばx - k*dを足す。 0 v 頂点vの数字をmod 10^9 + 7で答える。 制約条件 n…

問題 無向グラフで頂点1から2への最短パスの総数がちょうどk通りであるような頂点数1000以下のグラフを出力せよ。 答えが複数ある場合はどれを出力してもよい。 制約条件 解の存在は保証されている。

evima先生作問。 問題 n人の人がいて、それぞれの名前が与えられる。 i番目の人の名前はj番目の人のprefixであるというグラフを作る。 このグラフの頂点に以下の制約を満たすように0〜n-1の番号を振りたい。 m個のinfoが与えられて、info1[i]番の頂点はinfo2…

問題 木が与えられる。 それぞれの頂点には最大１匹のきつねがいる。 きつねは、最終的に以下の条件を満たすように移動したい。 きつねがいる町が連結になっている 一つの町には最大一匹のきつねしかいない このとき、きつねの移動距離の総和の最小値を求め…

問題 R, G, Bのどれかの色をした歯車がn個ある。 同じ色をした歯車は、すべて同じ向きに回転している。 歯車のうち、いくつかは噛み合っていて、噛み合っている歯車は必ず反対向きの回転をしている。 同じ色をした歯車同士が噛み合っていることはない。 この…

問題 n頂点からなる無向完全グラフで表される都市と道がある。 ここに雨がふって、それぞれの道がroads[i][j] / 8の確率で残り、 それ以外の確率で破壊される。 残った道が、木になっている確率を求めよ。 制約条件 n≦16

問題 n頂点からなる木のうち、m個の頂点から被害が出ている。 頂点のうち1箇所に悪霊がいて、被害の出ている頂点は全て、悪霊のいる頂点からの距離がd以内である。 このとき、悪霊のいる頂点としてありうる頂点の個数を求めよ。 制約条件 n, m, d≦10^5

問題 n頂点からなる木が与えられる。 木のそれぞれの頂点に、以下のような条件を満たすように'A'から'Z'の一文字のラベルを割り当てる。 同じラベルを持つ任意の頂点u, vについて、uからvへのパス上に、uのラベルよりも 小さいアルファベットのラベルを持つ…

問題 無向木が与えられる。 この木上を、m個の出発点とゴールの組(ui, vi)について、 uiから一人が出発し、viへゴールする。 それぞれの辺について、合計何人が通るか求めよ。 制約条件 n≦10^5 m≦10^5

問題 n個の町がn^2本の道でつながっている。 車がm個あり、それぞれの車で町iからjまで行くのにかかるコストが与えられる。 ここでr回のレースをする。 i回目のレースではsiからtiまで移動する。 この際、車をki回まで乗り換えてよい。 車は任意の町で、時間…

問題 n個の部屋が一直線上に並んでいる。 i個目の部屋にコンテナが置いてあるかどうかが与えられる。 部屋をいくつかの監視カメラが監視している。 全ての監視カメラは、長さLの連続する部屋を監視している。 それぞれの監視カメラが監視する部屋に重複があ…

問題 それぞれn頂点からなる木A, Bが与えられる。 この二つの木を次のようにしてつなぐ。 0, 1, ..., n - 1の順列をP[i]とする。 A[i]とB[P[i]]の間に辺を張る。 出来たグラフに大きさKの単純閉路（同じ点を二度通らない閉路）はいくつできるか。 全ての順列…

問題 平面上に猫とねずみがいて、それぞれの座標が与えられる。 猫とねずみの間に、円周の形をした壁をいくつか置くことができる。 それぞれの候補は中心(x, y)および半径rにより与えられる。 壁は、候補の中からいくつでも選んで置くことができるが、 交わ…

問題 日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1178&lang=jp） 制約条件 h, w≦30

問題 wxhのグリッド上にn匹のスライムがいる。 1ターンにスライムのうち1匹が、以下のような動きをすることができる。 上下左右の1方向を選び、 壁にぶつかるか、他のスライムがいるマスに入るまで動く。 他のスライムのいるマスに入ると、二つのスライムは…

問題 n個の路線がある。 i番目の路線はai個の駅をつなぎ、 それぞれの駅名および、j番目とj+1番目の駅の所要時間が与えられる。 今sの駅からtの駅へ、路線を使っていきたい。 電車はどちらの向きにも使うことができるが、乗り換えには1回あたりTの時間がかか…