問題 整数x1, x2, ..., xnに対してn個の制約 l[i] ≦ xi ≦ r[i] (1≦i≦n) および、m個の制約 x[u[i]] ≦ x[v[i]] + d[i] (1≦i≦m)が与えられるとき、 Σa[i] * x[i]^2 + b[i] * x[i] + c[i]を最大化せよ。 制約条件 n≦50, m≦100 ai ≦10, bi ≦1000, ci ≦1000 -100≦…

問題 辺に重みのついた無向木が与えられる。 二つの頂点u, vについてg(u, v) = uからvへの最短パス上に含まれる辺の重みの最大値 と定義する。数列p1, p2, p3, .. pn(1≦p1≦n)に対してf(p1, p2, ..., pn)を次のように定める。 f(p1, p2, ..., pn) = min{ g(i,…

問題 n個の地域に雨を同じ量ずつ振らせたい。 雨の降らせ方はm個あって、 i番目の降らせ方ではa[i]番目の地域に2, b[i]番目の地域に0, それ以外の全ての地域に1の雨が降る。 最初、上の降らせかたで、c0, ... , ck-1の雨を降らせた。 この後、どうにかして全…

問題 長さnの部屋が一直線上に並んでいる。 containers[i]はi番目の部屋にコンテナが置いてあるとき'X'で、そうでないときは'-'である。 監視カメラがいくつかあり、一つの監視カメラは連続するL個の部屋を監視している。 それぞれの監視カメラに写っている…

問題 無向木Gが与えられる。 Gの部分誘導グラフの木H, Iであって、HとIは同型かつdisjointであるものについて、 H + I の最大値を求めよ。 制約条件 G ≦50 部分誘導グラフは、部分グラフのうち辺を勝手に削除してはダメなやつ （元のグラフにあった辺の両端…

問題 hxwのグリッドがある。 最初全てのセルは白で、指定されたセルを全て黒に塗りたい。 一度の操作で、縦または横に一列に連続して並んだ白いセルを選び、 全てを黒に変えることができる。（間に黒が入っていてはだめ） 必要な操作の回数の最小値を求めよ…

問題 nxnのグリッドに白石'o'と黒石'x'が置かれている。 何も置かれていない場所は'.' 辺を共有する白石はひとかたまりとみなす。 ひとかたまりの白石が、何も置かれていない場所に隣接していない状態になると、 その白石は全て'.'に変わる。黒石を好きなだ…

問題 容量が多項式で表される無向グラフが与えられる。 このグラフの1番の頂点からn番の頂点への最大流を求めよ。 制約条件 n≦50 m≦500 多項式の次数は50以下

問題 全ての辺の容量が1であるような無向グラフがあたえられる。 このグラフに辺の追加と削除のクエリがくる。 それぞれのクエリの後での、1番の頂点からn番の頂点への最大流の大きさを求めよ。 制約条件 N≦500 M≦20000 任意の２頂点間に張られる辺の本数は…

問題 hxwの土地があって、それぞれのマスはfield[i][j]で表される。 filed[i][j]が'w'のところは荒野で、 'C'のところはCurviesがいるところ、 '.'のところは何もないところである。 'w'以外の全てのマスに、線路を引く。 線路はマスの４辺のうち、２つを接…

問題 h x wのチェス盤がある。 座標(i, j)が、(i + j) % 2 = 0 を満たすマスは黒で、そうでないマスは白である。 いくつかのマスには障害物が置かれている。 チェス盤に、ちょうど３マス分のサイズのL字のブロックを置く。 ブロックは、角の部分が黒いマスに…

問題 日本語なので本文参照（http://imoz.jp/data/joi/2013-sp-d1-collecting.pdf） 制約条件 N≦20 Q≦2000000

問題 座標平面上にn個の点がある。 このn個の点を以下の条件を満たす辺でつなぎたい。 辺はy[i] > y[j]であるときに限りiからjに張ることができる 全ての点は連結である 全ての点の入次数は1以下、出次数は2以下 辺の長さの和が最小になる このとき、辺の長…

問題 hxwマスのグリッドがある。 一番上の列と下の列はループしてつながっていて、 右端と左端もループしてつながっている。 それぞれのマスには上下左右いずれかの向きの矢印が書かれている。 一点からスタートした人は、その矢印に従って移動することを繰…

問題 n x nマスの盤の上にいくつかコマが乗っている。 コマの乗っているマスは'C'であり、乗っていないマスは'.'で与えられる。 初期状態において、i行目に置かれているコマの数をrow[i]とする。 コマを、一つ選び、上下左右の空いているマスへ移動させると…

問題 空間上にn個の点があり、それぞれの座標は(x[i], y[i], z[i])である。 点をk本以下のパイプでつなぐ。 パイプは、 自由にまげて良い。 分岐したり、合流したりしてはいけない。 どこを始点、終点としてもよい。 始点または終点または、途中の任意の点で…

問題 日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1088） 制約条件 n≦100 m[i]≦20 0≦xi,yi≦200000 cij≦1000 g≦10

問題 座席がn個ある電車がある。 m人の乗客がいて、それぞれはa[i]から乗りb[i]の駅で降りる。 電車には同時にn人以上が乗ることはできない。 （乗る駅および降りる駅では数に数えない） 乗客は、乗りたい区間全部に乗れないときは、電車に乗らない。 乗客を…

問題 hxwのグリッドで表される迷路がある。 迷路の中に二人がいる。 maze[i][j]が'#'であるマスは壁で、進入することができない。 maze[i][j]が'.'であるマスは何もないマスで、進入することができる。 maze[i][j]が'P'のマス（迷路上に二つ）は、二人のスタ…

問題 n人のチェスのチームが二つある。 自軍のそれぞれの人の強さはus[i]で表され、敵軍のそれぞれの人の強さはthem[i]で表される。 それぞれのチームからn人を順番に出し、勝負（強さの大きい人が必ず勝つ。強さが同じなら引き分け）をして、 勝ったら2点、…

問題 友達関係のグラフが与えられる。 友達関係は反射的（A→Bが友達ならB→Aも友達）であるが、推移的ではない（A→Bが友達かつB→Cが友達でもA→Cが友達とは限らない）。 このグラフにおいて、n-friendを以下のように定義する。 AとBが友達ならばAとBはn-friend…

問題 レジスタがm個あるコンピュータを考える。 n個の出力をさせたい。 出力するためには、あらかじめレジスタにその値を代入しなければならないが、 レジスタに値xを代入するにはxの2進数で立っているビットの数に等しいコストがかかる。 （出力にはコスト…

問題 nxnマスの研究所がある。 それぞれのマスは炉（壁）もしくは通路である。それぞれの通路に最初、何人の人がいるかおよび、 いくつの避難カプセルがあるかが与えられる。 時間0に'Z'で表されるマスの炉が暴走した。 'Z'のマスから汚染が、次のような広が…

問題 n個の頂点からなる有向グラフが与えられる。 それぞれの辺には最小流量、最大流量、およびコストが定められている。辺(u,v)に流量cのフローを流した場合、 c＞0ならコスト(u,v)+c^2のコストがかかり、 c=0ならコストはかからない。 1番の頂点からn番の…

問題 アリスはn本の映画に出演したい。 それぞれの映画は、一週間のうちに撮影できる日が決まっている。 それぞれの映画には、定められた期限（w[i]週間）がある。 それぞれの映画が完成するためには、アリスがd[i]日、撮影に加わらなければならない。 アリ…