問題 日本語なので本文参照（http://utpc2013.contest.atcoder.jp/tasks/utpc2013_07） 夏休みがM日あって、N人の掃除当番を使って、 「連続して掃除がされない日数の最大値」をなるべく小さくしたい。 i番目の人はa[i]日目〜b[i]日目のうち一日だけ掃除がで…

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

問題 日本語なので本文参照（http://utpc2013.contest.atcoder.jp/tasks/utpc2013_04） 二分ヒープを表す長さnの配列a[i]がある。 二分ヒープを表す長さm（m≧n)の配列b[i]で、b[i]の後ろn個がa[i]になっているものが存在すれば、その最小のmを、なければ-1を…

問題 長さnの順列p[i]が与えられる。 p[i]よりも辞書順で前にある全ての順列について、転置の総数の和をmod 10^9 + 7で求めよ。 制約条件 n≦10^6とか

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

問題 n項からなる数列A, B, Cが与えられる。 Aの先頭u項、Bの先頭v項、Cの先頭w項の和集合と、 A, B, Cの和集合が一致するような(u, v, w)について、u + v + wの最小値を求めよ。 制約条件 n≦10^5 各項≦10^9

問題 長方形の紙が2*n枚あり、それぞれの一辺の長さはx[i], y[i]である。 （縦横を入れ替えてもよい） この紙をn枚ずつに自由にわける。 n枚について次のような得点を考える。 xy平面上に辺が軸に平行になるよう自由に置く。 全ての紙が重なっている領域の面…

問題 長さが2^nの配列が与えられる。 配列に対する値vを以下のように計算する。 (a[0] or a[1]), (a[2] or a[3]), (a[4] or a[5]) ...を新たな数列aとする (a[0] xor a[1]), (a[2] xor a[3]), (a[4] xor a[5]) ...を新たな数列aとする というように、隣接す…

問題 nxmのアルファベット小文字の書かれたグリッドがある。 このグリッドの部分長方形うち、四隅のアルファベットが同じで、含まれている'a'の個数がk個であるようなものの個数を求めよ。 制約条件 n, m≦400 k≦nm

問題 n個の数列がある。 この中からk個以下の数字を削除して、連続する同一の数字の長さを最大にしたい。 その最大値を求めよ。 制約条件 n≦2 * 10^5

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

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

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

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

問題 1以上n以下のn個の整数a[i]が与えられる。 a[i]は全て互いに異なる。 このa[i]に対して、m個の以下のクエリに答えよ。 整数l, rが与えられる。 l≦i, j≦rなるi, jで、a[i]がa[j]の倍数であるものの個数を求める。 制約条件 n≦200000 クエリの個数≦200000

問題 n頂点m辺からなる重みつき無向グラフが与えられる。 これらのうち、i番目の辺(s[i], t[i])を使わないで作った最小全域木の重みを 全てのiについて求めよ。 制約条件 n≦100000 m≦200000 重みは0以上10^6以下の整数

問題 座標平面上にx座標, y座標がそれぞれ全て互いに異なるN個の点がある。この点のうち、三つを取りそれらをr, g, bとする。 x[r] 制約条件 N≦300000 0≦座標の値＜10^9

問題 日本語なので本文参照（http://imoz.jp/data/joi/2013-sp-d3-koala.pdf）

問題 nxmの方眼紙がある。 方眼紙には1x1刻みで縦線と横線が引かれている。 （ふちに線はひかれていないものとする） この用紙を使って二人が次のようなゲームをする。 二人が交互に手番をもつ。 手番のプレイヤーは、格子点と格子点を結ぶ、水平または垂直…

問題 nxm行列aijが与えられる。 関数x, yを f(x, y) = Σ[i=1 to n]Σ[j=1 to m]a[i][j] * max(0, k - abs(i - x) - abs(j - y)) と定義する。 k≦x≦n - k + 1 k≦y≦m - k + 1 を満たし、f(x, y)を最小にするようなx, yの組を求めよ。 答えが複数ある場合どれを…

問題 日本語なので本文参照（http://arc010.contest.atcoder.jp/tasks/arc010_4） 座標平面上に味方n人と敵m人がいる。 それぞれの座標が与えられる。 味方は、自分から最も近い敵よりも、厳密に近くにいる味方全員に情報を伝えられる。 味方全員に情報を伝…

問題 日本語なので本文参照（http://wupc2nd.contest.atcoder.jp/tasks/wupc_07） 次のようなクエリm個に答える。 高さhのだるまを、一番上に重ねる。 高さyの場所をハンマーで叩く。 このとき、ハンマーがあたらないならmiss, 複数のだるまに当たるならstop…

問題 日本語なので本文参照（http://www.utpc.jp/2011/） N頂点からなる木が与えられる。 i番目の頂点には数字x[i]が書かれている。 この木に対して次のようなQ個のクエリに答えよ。 クエリ：頂点v[i]からw[i]へのパス上に書かれている数字のうち、l[i]番目…

問題 日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1508） RMQに、値の変更および、[l, r]の部分を巡回シフトさせるクエリが飛んでくる。 制約条件 n≦2 * 10^5 q≦2 * 10^5

問題 家計図が与えられる。 家計図は、(名前、その人の親）の情報がn個与えられることにより与えられる。 この家計図に対して、次のようなq個のクエリに答えよ。 クエリ： 人v[i]の、ちょうどk代目の子孫のうち、異なる名前の数を答える。 制約条件 n≦10^5 q…

問題 日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0575） 制約条件 N, Q≦100000 M≦200000 K≦N

問題 英小文字からなる文字列sが与えられる。 この文字列に対して、以下のようなクエリをm個実行する。 入力l, rを受け取る。 sのl文字目からr文字目を、その部分が回文になるように並び替える。 回文が複数個できる場合は、辞書順で最小になるように並び替…

問題 最後からk個のアクセスのメモリをキャッシュするコンピュータがある。 このコンピュータに次のようなクエリが来る。 ADDR x : xの番地にアクセスする。 RANGE b y n : bの番地から、0≦i＜nとしてb + i * yの番地に順にアクセスする。 STAT : 前回のSTAT…

問題 日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1070&lang=jp） 制約条件 クエリの数≦200000

問題 xy平面上に、n本の川とn+1個の陸地がある。 i番目の川の幅はwidth[i]で、n番目の陸地とn+1番目の陸地の間を流れている。 その川を渡るときのスピードは、speed[i]（方向によらず一定）である。 陸地は細長く、y軸に平行な線分とみなすものとする。 線分…