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

問題 整数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頂点からなる無向木が与えられる。最初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はオー…

問題 a[i]が与えられる。 (i - j)^2 + (Σ[k=j,i]a[k]) ^ 2の最小値を求めよ。 制約条件 a[i]の要素≦10^5 |a[i]|≦10^4

問題 n頂点からなる木で、各頂点以下の部分木のサイズがc[i]であるような木であり、 葉以外の頂点では直接の子が二つ以上のものが存在するか、 存在するならYESを、そうでないならNOを出力せよ。 制約条件 n≦24

問題 hxwのグリッドがある。各セルには得点が定められている。 Aは(1, 1)から(h, w)へ移動し、Bは(h, 1)から(1, w)へ移動する。 Aは右または下にのみ移動できて、Bは右または上にのみ移動できる。 A, Bの軌跡で共通部分はただ１つのセルでなければならない。…

問題 n頂点からなる根付き木が与えられる。各頂点は最初0または1である。 このグラフに対して次の操作が好きなだけできる。 操作：好きな頂点vをえらび、vおよび、vの子孫uでdepth(u)-depth(v)が偶数の頂点uの0, 1を反転させる。 最終状態が与えられるとき、…

問題 座標平面上にn個の円がある。 原点から好きな方向にボールを投げる。 ボールは距離dの地点でバウンドし、2*dでバウンドし…とk*dでバウンドして無限に跳ぶ。円の内部または周でバウンドすると1点もらえる。 もらえる得点の最大値を求めよ。 制約条件 n≦2…

問題 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人…

問題 n人の人がいて、その人たちが参加したチャットの入退室のログがある。 ログはある時刻からある時刻までしか記録されていないが、その間の記録は全て含まれる。 このチャットにおいて、誰か一人でもオンラインになっているときは、 必ずその人がオンライ…

Div1のコンテストで8位だった。 けどレート130くらいしか上がらなかった… 問題 英大文字からなる入力が与えられる。 この文字を左右に反転させても同じかどうかを判定せよ。 文字列を左右反転とは、各アルファベットを鏡像反転させて、逆順に読むことを言う…

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

問題 n頂点からなる木が与えられる。根は0番のノード。 各頂点には水槽がついている。お金をp円もっている。 最初にk個以下の好きなノードを選び、そのノードの水槽に1リットルずつ水を入れる。 次から全ての水槽が空になるまで以下の操作を繰り返す。 水槽…

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

問題 n人がいて、それぞれ番号が1〜n番である。 全員がピストルとk発の弾をもっていて、k回つぎのことを行う。 自分以外の生存者のうち、番号がもっとも小さい人に向けて同時に銃を撃つ。 i番目の人が撃った銃は、p[i]%の確率で当たる。弾が当たった人は死ぬ…

問題 n個の都市が双方向に通行可能な道路n-1本の道路で結ばれている。 任意の二都市をつなぐパスが存在する。 道路はいくつかが壊れている。 i番の都市を選ぶと、1番の都市からi番の都市へ行くのに必要な道路がすべて修理される。 最低いくつの都市を選べば…

問題 n人がコンテストをした。全員l以上r以下の整数の得点を取った。 全員の得点の合計はsall点。上位k人の得点の合計はsk点である。 このような条件を満たす全員の得点の取り方をどれか一通り出力せよ。 解が存在することは保証されている。 制約条件 n, l,…

問題 n個の料理を順番に食べる。n番目の料理はa[i]. a[i] = 1のときはボウルで食べる。 a[i] = 2のときはボウルかプレートどちらでも食べられる。 最初綺麗なボウルをm個、プレートをk枚もっていて、 食事のたびに料理の種類に応じて、綺麗なボウルまたはプ…

問題 数直線上に駅が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リ…

問題 ハンバーガー一個を作るにはSがrs個, Bがrb個, Cがrc個必要である。 最初Sをns個、Bをnb個、Cをnc個持っている。 足りない材料はSを一個ps円、Bを一個pb円、Cを一個pc円で買えるが、 予算はr円。 最大でハンバーガーはいくつ作れるか求めよ。 制約条件 …

問題 二数a, bに対して次の操作ができる。 どちらか一方を2で割る（割り切れるときだけ） どちらか一方を3で割る（割り切れるときだけ） どちらか一方を5で割る（割り切れるときだけ） この操作を何度か行いa, bを等しくしたい。 必要な操作の回数の最小値は…

問題 各要素が1または2の長さnの数列a[i]が与えられる。 与えられたnの約数kについて、a[i]を周期kにするには、a[i]の要素を最低いくつ変更しなければならないか。 制約条件 n, k≦100 a[i]は1または2

問題 nxnのグリッドがあって、最初(sx, sy)にいる。 最初の速度は(dx, dy)で、速度(dx, dy)で移動すると、 x' = (x + dx - 1) mod n + 1 y' = (y + dy - 1) mod n + 1に移動する。 移動の前に、今いるグリッドを(x, y)とすると、dx, dyがともに(今のターン数…

問題 数直線上y = 0の線を、x = lからx = rまで移動したい。 n個のライトがあって、それぞれの座標は(x[i], y[i])で、 a[i]度の角度の範囲だけを照らすことができる。 移動できる部分は、線分に一つ以上のライトがかかっているところだけ。 最大でどれだけ移…

問題 n項からなる数列x[i]が与えられる。 素数pに対してf(p)は、xのうちpの倍数であるものの個数とする。 [l, r]が与えられるので、l以上r以下の素数p全てについてf(p)の和を求めよ、 というクエリがm個くるので答えよ。 制約条件 n≦10^6 m≦50000 x[i]≦10^7 …