問題 n個の歌があり、それぞれの歌の長さはduration[i], トーンがtone[i]である。 Tの時間のうちに異なる歌をできるだけ多く歌いたい。 トーンがaである歌の直後にトーンがbの歌を歌おうとすると、|a - b|の時間の休憩が必要である。 最大でいくつの歌を歌え…

問題 n個の数列a[i]を互いに素な二つのグループにわける。片方が空であってもよい。 f(i, j)を、i, jが違うグループのときa[i] + a[j] + h, 同じグループのときa[i] + a[j]とする。max{f(i, j) | 1≦i＜j≦n} - min{f(i, j) | 1≦i＜j≦n}が最小となるようなわけ…

問題 hxwの行列がある。 この行列のうち、(a, b)を左上(c, d)を右下とするような長方形を選ぶ。 角の4つの数字の最小値の最大値を求めよ。 制約条件 h, w≦1000 数字≦10^9

問題 n人の人がいて、それぞれの人の大きさはa[i]である。 n人はn!通りの並び方を等しい確率で選んで並ぶ。 大きさの和がp以下であるような部分だけ、列の先頭から人がレストランに入れる。 入る人が、入れない人を飛ばすことはできない。 レストランに入れ…

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

問題 01からなる文字列で、0がn個1がm個ちょうど含まれているものを考える。 この文字列に対して、以下の操作を繰り返した後で、最後にgになるものの個数を求めよ。 操作： 文字列が1文字になっていたら終了 末尾が00のとき、1に置き換える 末尾が01のとき、…

問題 n個の正の整数a[i]が与えられる。 a[i]から異なるk個を選びb[0], ..., b[k-1]とする。 b[0] & b[1] & ... & b[k-1]を割り切る2^vのうち、vの最大値を bの美しさと呼ぶ。（&はビット演算のand） ただし最大値が存在しないときは美しさは-1である。 美し…

問題 平面上に半径Rの円が2m個ある。 A1〜Amは中心が座標((2i - 1)R, 0)にあり、 B1〜Bmは中心が座標((2i - 1)R, 2R)にある。 円Aiの中心から円Bjの中心へ、2m個の円の内部または周だけを通って行くときの最短距離をd(i, j)とする。 全ての1≦i, j≦mに対するd…

問題 長さnの数列a[i]が与えられる。 a[i]の空でない、（必ずしも連続しない）非減少部分列のうち、異なるものを全て取り出す。 それぞれに対して、それより"小さな"列の個数を求め、足し合わせる。 個数の総和はいくつか。 ただし、列xiよりyiが小さいであ…

問題 文字列aをb回繰り返すことを(a, b)と書く。 文字列a, cおよびそれらの繰り返し回数b, dが与えられる。 w = [a, b], q = [c, d]としたとき、 [q, p]がwの（必ずしも連続しない）部分文字列となるような最大の整数pを求めよ。 そのような正の整数pが存在…

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

問題 n桁の正整数であって、 0, 1, 2... ,9の数字がそれぞれa[0], a[1], ..., a[9]回以上現れるようなものはいくつあるか、求めよ。 leading zeroは許されない。 制約条件 n≦100

問題 nxnのそれぞれのマスに数字a[i][j]が書かれたグリッドがある。 Aさんがグリッドの左上から右下まで、右か下だけに移動しながら移動する Bさんがグリッドの右下から左上まで、左か上だけに移動しながら移動する このとき、「二人の少なくともどちらかが…

問題 数列a[i]が与えられる。 数列の連続する部分列(a[i], a[i+1], ... a[j])のうち、 同一の値をk個以上含むものの個数を求めよ。 制約条件 n≦4*10^5

問題 n種類のコインを投げて、出た面を順番に記録する。 i番目のコインが表の確率はp[i]である。このとき、連続する○の大きさの二乗の総和 （たとえば○○×○××だったら、2^2 + 1^2 = 5）の期待値を求めよ。 制約条件 n≦10^5 0≦p≦1

問題 辺に文字列のついた根付き木が与えられる。 この木から文字列を以下のようにして作ることができる。 始点の(枝，枝の文字の何番目か）、終点の（枝，枝の文字の何番目か）を選ぶ。 必ず始点のほうが根に近いほうを選ぶものとする。 始点枝から終点の枝…

問題 n行m列のグリッドが与えられる。各マスは'.'または'#'である。 #のマスが連結であるとは、「どの二つの#のマスも、辺を共有するような'#'を経由してたどり着ける」ことを言う。 #が一つだけのグリッド、#が一つもないグリッドは連結であることに注意す…

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

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

問題 うさぎがn匹いて、それぞれs[i]からt[i]の間部屋にいた。 部屋にいた時間の区間が長さ0以上の共通部分をもつうさぎは友達になった。 うさぎが全員twitter的なサービスで自己紹介を、他の全てのうさぎに見せたい。 友達の自己紹介は直接見られるが、友達…

問題 n個の単語を、幅wのフィールドに、好きな行数にわけて書く。 一つの単語は、間をあけずに、行をまたがずに書く。 単語と単語の間は一つ以上のスペースを空けて書く 行の先頭および末尾にはスペースを空けずに書く。 ただし、最後の1行の末尾はスペース…

問題 日本語（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2446） 制約条件 n≦20 m≦10^18

問題 二分木が与えられる。 根に移動するコストが０ 子に移動するコストが０ 一つだけ、今いるノードを覚えることができて、覚えるコストが０ 覚えたノードに移動するコストが０ （何度でも新たに上書きで覚えることができる） とき、全ての子を訪れるのにか…

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

問題 日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2434） 制約条件 n≦2000 m≦2000

問題 n本の直線が与えられる。 全ての直線から等距離にある点を求めよ。 複数あるときはManyと、存在しないときはNoneと出力せよ。 誤差は10^-4の絶対誤差が許容される。 制約条件 n≦100

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

問題 n個の単語をそれぞれ一行に1つずつ書く。 幅wになるように、自由にスペースを入れることができる。 スペースを入れた後で、上下左右に同じ文字が隣り合っているとき（スペースを挟んではいけない）、１点を得るものとする。 得られる得点の最大値を求め…

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

問題 4x4のグリッド上に風船がおかれている。 風船には1〜4の数字がついている。 風船をクリックすると、風船の数字が1増える。 数字が5以上になった風船は、破裂して、上下左右の４方向に水滴が飛び散る。 割れた次の秒から、水滴は1秒に１マス進む。 水滴…