Hは解説みて通しはしたけど解法の意味がわからない。 問題 n人の乗客がいてそれぞれ駅s[i]からt[i]まで電車に乗る。 全員が座るためには各人が席を指定できないとき、最小でいくつの座席が必要であるか、 また各人が自由に席を指定できるとき最小でいくつの…

Dむずくて通せてないですごめんなさい。 問題 n個のセルが黒または白で塗られている。 セルの初期状態およびゴールの状態が与えられる。 セルは一度の操作で連続する1〜k個を好きな色に塗ることができる。 最小で何回の操作で全てのセルをゴールの状態にでき…

問題 aまたはbからなる文字列が与えられる。 このとき、文字列に2回以上、重ならないで出現する空でない部分文字列の個数を求めよ。 文字列が同じときは一つと数える。 制約条件 文字列は乱数により生成される。 n≦10^5

問題 長方形の板がN枚並んで出来ているフェンスがある。 i番目の板は幅1, 高さがh[i]の長方形で、下側の辺は地面にぴったりとくっついている。 このフェンスに看板を貼る候補がQ通りある。 各候補は、l, r, wで表され、l枚目からr枚目の板の内部に幅wの長方…

問題 n個の水銀の入ったチューブがあり、i番目にはh[i]リットルの水銀が入っている。 このとき次のクエリに答えよ。1 pi vi : pi番目のチューブの水銀の量をviにする。 2 xi : 合計viリットルの水を好きなようにチューブに入れる。使ったチューブのうち最大…

問題 n人の人からなるべく大きい人数のグループを作る。 i番目の人はスキルがsiである。この人は、グループの他人全員のスキルがli以上ri以下じゃなければグループに入らない。 最大で何人のグループができるか。 制約条件 n≦10^5 0≦li≦ri≦si≦3*10^5

問題 数列a[i]が与えられる。各a[i]の符号を好きに変えてよい。 このとき、a[i]の転置（i ＜ jかつa[i] ＞ a[j])の個数の最小値はいくつか求めよ。 制約条件 n≦3000

問題 数列a[i]に対して次の操作を行うことができる。 位置が等差数列になっている同じ値を選ぶ（a[i] = a[i + m] = a[i + 2*m] = ...) この値を数列から削除する 残った数を好きに並び替える 数列b[i]が与えられる。この数列に対して次のクエリm個に答えよ。…

問題 座標平面上の(x, y)に宇宙船が固定されている。 最初、自分から距離r以下にある質量p以下の物体を回収できるマジックハンドをもっている。 宇宙空間にはn個のマジックハンドが散らばっており、 i番目のマジックハンドは座標(xi, yi)にあって、質量がmi…

問題 横一列にn台の駐車スペースがあり、左から順に1, ..., nと名前がついている。 ここにm個の車の到着または出発のクエリが来るので処理せよ。 車は以下のアルゴリズムで駐車場所を選ぶ。 全ての空きスペースの中で、一番近くにある他の車までの距離が最大…

問題 n項からなる数列a[i]が与えられる。これに対してq個のクエリに答えよ。 クエリ： 区間l, rが指定される。 [l, r]と長さが等しく、[l, r]に交わらない区間[s, t]で、a[l + i] = a[s + i] = constとなる区間はいくつあるか求めよ。 制約条件 n, q≦10^5 a[…

問題 1番のノードが根であるような木が与えられる。各ノードは値a[i]をもっている。 木に対して次のクエリを行うことができる。 1 x val : x番の頂点にvalを足す。x番の直接の子に-valを足す。x番の頂点の２代目の子孫にvalを足す３代目の頂点に-valを足す………

問題 n項からなる数列a[i]が与えられる。a[i]の必ずしも連続しない部分列b[i]で、 長さが4m b[4k + 1] = b[4k + 3] b[4k + 2] = b[4k + 4] が成り立つもののうち、最長のものを一つ出力せよ。 制約条件 n≦5 * 10^5 -10^9≦a[i]≦10^9

問題 n個の点(si, fi, ti)が与えられるので次のQ個のクエリに答えよ。 クエリ：点(x, y, z)に対して、最初のn個の点の中から、s≦x, f≧y, t≧zを満たす点のうち、tがもっとも小さいものの番号を答える。 ただし、最初のn点のtiは全て異なる。 制約条件 n, Q≦10…

問題 二つの数列が与えられる。 この数列に次の2種類の操作を行える。 両方の数列から、空でない任意のprefixを選んで削除する。ただし両方のprefixの、最後の要素は一致していなければならない。 残った数列を全て削除する。 1番目の操作にかかるコストはe,…

問題 辺に重みのついた無向木が与えられる。 二つの頂点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頂点からなる無向木が与えられる。最初1番の頂点だけが色つき。 この木に対して以下のクエリを処理せよ。 1 v : 頂点vに色をつける。 2 v : 頂点vに最も近い色つきの頂点の距離を出力する。 制約条件 n, クエリ≦100000

問題 フィボナッチ数のi番目をF[i]とする。 長さnの数列a[i]が与えられる。次のようなクエリがq個来るので処理せよ。 1 l r : l≦i≦rなるiに対してa[i]:=a[i] + F[i-l+1]と更新する 2 l r : l≦i≦rなるiに対してa[i]の和をmod 10^9 + 9で出力する。 制約条件 n,…

問題 文字列sが与えられる。次のようなクエリq個に答えよ。sの連続する部分文字列で、文字列x, yをともに連続する部分文字列として含むような文字列のうち、長さが最小のものの長さを出力せよ。 そのような文字列が存在しない場合-1を出力せよ。 x, yはオー…

問題 n頂点からなる無向木が与えられる。 各頂点には重みwiがついている。重みの初期値が与えられる。 この木に対して次のようなクエリがq個来るので、答えよ。 t a b c t = 1のとき、木の頂点aから頂点bへのパス上にある頂点全ての重みをcに変更する。 t = …

問題 n個のコップがあり、それぞれ1〜nの番号がついている。 最初順番がバラバラになって一列に並んでいる。 これに対してm回操作をした記録が与えられる。i番目の操作はx[i], y[i]により表され、 左からx[i]番目のコップにはy[i]の番号がかかれていて、 そ…

問題 n人の人がいて、この中の二人が犯人。 n人のそれぞれに犯人は誰だと思うと聞いた結果、i番目の人はa[i]とb[i]と答えた。 犯人の候補(x, y)は、x = a[i]またはy = a[i]またはx = b[i]またはy = b[i]を満たすとき、 i番目の人の同意を得られる。 最低p人…

問題 数直線上を走るロボットがいる。 最初ロボットは原点にいて、commandの文字列にしたがって動く。 i番目の文字がRのときロボットは+1, Lのときロボットは-1動く。 ロボットの座標が-A未満になるときまたはBより大きくなるときには命令は無視される。 (A,…

問題 長さ2^nの数列a[i]がある。 これに以下のクエリがm個来るので処理せよ。i番目のクエリでは、0≦qi≦nなる整数qiが来る。 数列を2^qi個ずつに区切り、それぞれを反転させた後、同じ順に結合した数列を新しいa[i]とする。 クエリ毎に、操作後のa[i]における…

問題 長さNの配列があり、次のようなクエリが来るので処理せよ。 1 l r : {a[i]|l≦i≦r}の最小値を求める。 2 l r x : l≦i≦rなるiについて、a[i] = a[i] ^ xとする。^はbitwise xor 制約条件 N≦250000 0≦a[i], x≦65535

問題 x軸上にn本の線分がある。i番目の線分は[l[i], r[i]]である。 これらの線分に対して以下のm個のクエリに答えよ。 i番目のクエリではk[i]個の点が与えられる。それぞれの座標はx[i][j]. これらの点を一つ以上含む線分の本数を出力する。 制約条件 n, m≦3…

問題 数直線上に駅がn個ある。i番目の駅はx[i]にある。 ここから駅をk個残してあとは廃止する。 残す駅は、全ての二つの駅間の距離の平均が最小になるようにしたい。 （Sを残す駅としたら、Σ[a, b∈S, a 駅の残し方をどれか一通り出力せよ。 制約条件 n≦3*10^…

問題 n枚の皿があって、i番目の皿の容量はa[i]リットル。 i番目の皿に水を注いで、容量を超えた分はi+1番目の皿に溢れる。（i+1番目の皿も一杯ならi+2番目に……となる） n番目の皿から溢れた水は捨てられる。 次のクエリがm個来るので答えよ。 i番目の皿にxリ…

問題 n枚のカードがあって、それぞれには1〜nの異なる整数どれかが書かれている。 何回でも次のような操作をすることができる。 残っているカードのうち連続するw枚のカードを選ぶ 数字が最小のカードを捨てる w点をもらう 操作を終えた後のカードの状態が与…

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