データ構造
問題 n人の人がいて、それぞれの責任感r[i]および年齢a[i]が与えられる。 この人の中から、次の条件を満たすグループを作りたい。 責任感r[i]が最大の人（タイの場合はタイの中の誰でもいい）をリーダーとする。 リーダーと、他の全員の年齢の差がkである。 …
問題 数列a[i]が与えられる。 この数列のうち、最大k個の符号を好きに変えることができる。このとき、連続するlen個の区間の和の絶対値| Σ[j = i to i + len - 1]a[j] | の最大値を求めよ。 制約条件 n≦10^5 a[i]≦10000 k≦n
問題 n個の整数の列がある。それぞれの数は1以上m以下である。 この列から最大k個を取り除いて、同じ整数の続く部分の長さを最大にしたい。 同じ整数の続く部分の最大の長さを求めよ。 制約条件 n≦2*10^5 m≦10^5 k≦n
問題 n個の箱があり、それぞれに次の条件を満たすように石をいくつか入れる。 石は無限にある i番目の箱には、石をまったく入れないか、lowerBound[i]以上upperBound[i]以下の石を入れる。 全ての箱の石の合計が9000個より多い このとき、全ての石の合計とし…
問題 h x wの長方形の土地がある。 それぞれのマスの危険度grid[i][j]が与えられる。 このとき、次のようなクエリq個に答えよ。 (r1[i], c1[i]), (r2[i], c2[i])を頂点とするような長方形の中で、 最も危険度が低いマスの危険度の値を答える。 制約条件 h * …
問題 木の棒がN本、環状に並んでいる。 i番目とi+1番目、0番目とN-1番目はそれぞれ隣り合っている。 0番の木の棒を(startR, startG, startB)の色に塗る。 i番目の棒を塗り終えた後、i+1番目の棒を、次のようにして塗る。 i番目の棒の色を(R', G', B')、新し…
問題 日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2359） 制約条件 Q≦5*10^4 tiは0か1 a[i]≦b[i]≦10^9 y[i]≦10^9
問題 n両の客車からなる電車がある。 一両の長さはlengthで、時刻0に電車の左端がx=0に位置している。 電車は数直線の正の向きに、trainSpeedで移動している。 泥棒が電車の左端から右端へ移動したい。 泥棒が移動する速度はrobberSpeedである。 線路には橋…
問題 数列t[i]が与えられる。 長さKの連続する部分列の中央値の、全ての合計を求めよ。 ただし、長さnの数列の中央値とは、nを小さい順に並び替えたときにn/2番目の要素を指すものとする。 制約条件 t[i]の長さ≦250000 K≦5000 0≦t[i]≦65535
問題 n本のビルがあり、それぞれのビルは幅1高さh[i]の長方形をしていて、 (i,0)を左下の頂点、(i+1,h[i])を右上の頂点としている。 このビルに収まる、軸に平行な長方形のうち、面積が最大のものの面積を求めよ。 制約条件 n≦100000 h[i]≦835454957
問題 項数nの数列a[i]を以下のようにして作る。 a[0]=A0 a[i]=(a[i]*X+Y)%M s(i,k)をa[i]+a[i+1]+……+a[i+k-1]とする。 s(i,k)とs(j,k)の和の範囲が重ならないようなi,jについて、 abs(s(i,k)-s(j,k))の最小値および、最小値をとるときのkを求めよ。 ただし、…
問題 n個の区間が与えられる。 区間のうち、他の区間に完全に含まれるようなものはいくつあるか、求めよ。 制約条件 n≦10^5 1≦区間の左端、右端≦10^9 区間の左端の値、右端の値は全て異なる
問題 n個の穴があり、穴はそれぞれa[i]のエネルギーがを持つ。 i番目の穴にボールを入れると、i+a[i]番目の穴へボールが飛ぶ。 飛んだ先の穴からまた連鎖的に同じことがおこる。 a[i]がnを超えると、その時点で連鎖は終了する。 このとき、次のm個のクエリに…
問題 n人の人が自分の色のカードa[i]枚ずつ持っている。 次のような条件を満たす「交換」を何度か行い、各人が持っているカードが全て自分以外の色になっているようにしたい。 それが可能であれば、Yesと、その交換手順を具体的に一通り出力し、不可能ならNo…
問題 各桁の数字が全て4または7である数をlucky numberという。 例えば（4,7,477など） n項の数列に対してm個のクエリに答えよ。 add l r x 区間[l,r]の項全てにxを加算する count l r 区間[l,r]の項のうちlucky numberである数の個数を出力する 制約条件 n,…
問題 n冊の本がある。それぞれの高さはh[i]である。 この本から、 連続するa冊で 最も高い本と最も低い本の差がk以下 であるように本を選びたい。 aの最大値、そのときの本の選び方の数b、 具体的な本の選び方b通りを出力せよ。 制約条件 n≦10^5 h[i],k≦10^6
問題 男女n人が一列に並んでいる。 それぞれの性別およびスキルの値が与えられる。 この列に対して、以下のような方法でペアを作れるだけ作る。 列で隣り合う男女のうち、スキルの差の絶対値が最も小さいペア（複数ある場合最も左のペア）を選び、ペアを作る…
問題 切符には二つの番号(x,y)がついている。 切符がluckyであるとは、x*y=rev(x)*rev(y)が成り立つことをいう。 ただし、rev(x)は、xの数字を反転させたもので、 例えばrev(132)=231, rev(1200)=21である。 今、xとyをx≦maxx,y≦maxyとなるように決め、 (p,q…
問題 nxnのチェス盤にm個のクイーンが置かれている。 クイーンのうち、 他の0個のクイーンの効きにあるような駒の数、 他の1個のクイーンの効きにあるような駒の数、 …… 他の8個のクイーンの効きにあるような駒の数 をそれぞれ求めよ。 制約条件 n≦10^5 m≦10…
問題 チェスに新たにビリヤード球という駒を導入する。 この駒はビショップのように動くが、盤の端で（何度でも）跳ね返ることができる。 盤の角で跳ね返った場合、元の進行方向へ戻る。 nxmのチェス盤に、互いに効きのないビリヤード球が最大いくつ置けるか…
問題 集合S={a1,a2,..,ak}に対して、Sのsum of Mediansとは、 Σ[i≦k かつ i mod 5 = 3]a[i]により定義される。 最初集合Sは空である。 次のn個のクエリが与えられるので、それらに答えよ。 add x 集合Sにxを加える。この操作の時点でSにxは存在しない。 del …
問題 n人の人が以下のようなルールで列に並ぶ。 i番目の人が来て、列の最後尾に加わる。i番目の人は重要度a[i]と、常識度c[i]を持っている。 一つ前の人の重要度a[i-1]が、自分の重要度より低かったら、その人前へ割り込む。 割り込みはc[i]回だけできる。 n…
問題 n個のハンガーが一列に並んでいて、左から順に1からnの番号がついている。 以下のようなクエリがq個来るので処理せよ。 0 l r l以上r以下の番号のハンガーのうち、上着がかけられているハンガーの数を出力する。 (0以外の数字) 数字のidをもつ人が、次…
問題 n項の数列が与えられる。 この数列に対してt個のクエリに答えよ。クエリ： 整数l,rに対して、次の値を求める。 a[l],a[l+1],...,a[r]における、値sの出現回数をKsとする。 全ての整数sについて、Σs*Ks*ks 制約条件 n,t≦200000 1≦a[i]≦10^6
問題 1〜nを並べ替えた数列のうち、 転置がちょうどm個あるもので、辞書順最小のものを求めよ。 制約条件 n≦50000 m≦n(n-1)/2
問題 単調非減少な数列A[i]が与えられる。 m個のクエリが与えられるのでそれに答えよ。クエリ： 二つの整数l,rが与えられる。Aのl番目〜r番目の項のうち、最も出現回数が多い数字の出現回数はいくつか。 制約条件 -100000≦A[i]≦100000 m≦100000 数列の項≦100…
大体理解した。 完全にソラで書けるように何回か復習すべきである。 問題 N個の線分が接続されたクレーンがある。 それぞれの線分の長さはL[i]で与えられる。 はじめは全ての線分がまっすぐ上を向いて接続されている。 ここにC個の命令がくる。命令iは二つの…
問題 地球上の二点が緯度と経度により指定される。 その二点間の、地表での距離を1メートルの精度で求めよ。 ただし地球は半径6370kmの真球と仮定せよ。 制約条件 なし
問題 N人が橋を渡りたい。 橋は同時に2人までしか渡ることができず、また一つしかない懐中電灯を持って渡る必要がある。 それぞれの人に対して橋を渡るのにかかる時間が決まっている。 二人が同時に渡るときは遅い人に合わせる。 全員が橋を渡り終えるのにか…
問題 平面上に、N個の長方形の建物がある。 建物の一辺はx軸上にある。 建物の上の辺は二点(A[i],H[i]),(B[i],H[i])を結んでいる。 建物一つ以上に覆われている領域の面積の総和を求めよ。 制約条件 N≦40000 A[i],B[i],H[i]≦10^9
