Codeforces
問題 n個の箱があり、i番目の箱は 時刻in[i]に倉庫に入り、out[i]に倉庫から出る。 この荷物は重さがw[i]であり、上にs[i]までの荷物を載せることができる。 この荷物を倉庫に出し入れするとv[i]円もらえる。 倉庫には、同時に全体でSの重さの荷物しか入れら…
問題 wavy numberとは、数字を10進法で書いたときの数字をx1,x2,x3,...,xnとすると x1＜x2＞x3＜x4…が成り立つまたは、x1＞x2＜x3＞x4…が成り立つ数のことを言う。Nの倍数のwavy numberでK番目に小さいものを求めよ。 答えが存在しない場合や10^14より大きく…
問題 長方形の板がN枚並んで出来ているフェンスがある。 i番目の板は幅1, 高さがh[i]の長方形で、下側の辺は地面にぴったりとくっついている。 このフェンスに看板を貼る候補がQ通りある。 各候補は、l, r, wで表され、l枚目からr枚目の板の内部に幅wの長方…
問題 K日間にわたって写真を撮る。カメラの記憶容量はLであり、写真一枚が消費する記憶容量は非圧縮の場合Dである。 i日目にはti枚の写真を撮り、j番目の写真のできばえはQijである。 写真は好きなものを好きなだけ削除することができる。 また、同じ日の写…
問題 無限に広いグリッドがある。 N個の長方形があり、(xi, yi)を左下, (Xi, Yi)を右上としていて、範囲のマスにそれぞれ一人ずつ人間がいる。 長方形は重ならない。 M個の爆弾があり、(bxi, byi)に置かれていて、p1iの確率で、y = byiの直線にいる人が全員…
問題 n個の水銀の入ったチューブがあり、i番目にはh[i]リットルの水銀が入っている。 このとき次のクエリに答えよ。1 pi vi : pi番目のチューブの水銀の量をviにする。 2 xi : 合計viリットルの水を好きなようにチューブに入れる。使ったチューブのうち最大…
問題 hxwのグリッドの各マスをA-Zの文字いずれかで埋める。 隣り合う（辺を共有する）マスであって、同じ文字が書かれたタイルは繋がっているとする。 繋がったタイルの塊は必ず正方形をしていなければならない。 辞書順で最小の埋め方を求めよ。 制約条件 h,…
問題 n人の人が一列に並んでいて、k個のゴンドラにわけて乗せる。 一つのゴンドラには何人でも乗れるが、乗せる順番は並び順でなければならない。 人同士には仲の悪さが決まっていて、i番目とj番目の人の仲の悪さはa[i][j] (=a[j][i]). 一つのゴンドラ内の不…
問題 n人の人からなるべく大きい人数のグループを作る。 i番目の人はスキルがsiである。この人は、グループの他人全員のスキルがli以上ri以下じゃなければグループに入らない。 最大で何人のグループができるか。 制約条件 n≦10^5 0≦li≦ri≦si≦3*10^5
問題 n個の石を二人が取り合う。i番目の石の得点はa[i]点。 二人が取れる行動は予め決まっていて、第iターン目には、 プレイヤーt[i]が、 s[i] = 'b'なら場の石を一個捨てる（両プレイヤーに点数は入らない）、 s[i] = 'p'なら場の石を自分のものにする（自…
問題 長さnの数列a[i], b[i]が与えられる。 長さnmの対応の取れた括弧の列を書く。i番目に開き括弧を書くときコストa[i % n]が、 i番目に閉じ括弧を書くときコストb[i % n]がかかる。 長さnmの括弧の列を書く最小のコストを求めよ。 制約条件 n≦20 m≦10^7
問題 数列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個に答えよ。…
問題 座標平面の原点が恒星。その周囲を円軌道で惑星が反時計回りに速度vpで周っていて、 惑星はt = 0のとき(xp, yp)にいる。 宇宙船が(x, y)にいて、宇宙船は好きな方向に速度vで動くことができる。 太陽から距離r以内に入ると熱くて死ぬ。宇宙船は最短で何…
問題 座標平面上の(x, y)に宇宙船が固定されている。 最初、自分から距離r以下にある質量p以下の物体を回収できるマジックハンドをもっている。 宇宙空間にはn個のマジックハンドが散らばっており、 i番目のマジックハンドは座標(xi, yi)にあって、質量がmi…
問題 n枚の袋があって、i番目の袋の中にはa[i]枚のコインが入っている。コインは全体でs枚である。 ただし、袋の中にはさらに別の袋が入っていることがある。 a[i] = {1, 1, 3}で、全体でコインが3枚ということがある。 （3番目の袋には1番目の袋と2番目の袋…
問題 横一列に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[…
問題 英小文字のうちa-xの24文字のどれか、3文字からなる単語がn個与えられる。 24文字のうち好きな文字を母音にしてよい。 母音が一文字以上含まれている単語はよい単語である。 2^24の母音の選び方に対して、(良い単語の数)^2を求め、それらを全てxorした…
問題 長さnの数列a[i]が与えられる。 aの任意の空でない区間[l, r]で、a[i]の符号を好きに反転してよい。 このようにして[l, r]内の総和が0になるようにする方法は何通りあるか。 制約条件 n≦1000 -1000≦a[i]≦1000 a[i]の総和≦10000
問題 1番のノードが根であるような木が与えられる。各ノードは値a[i]をもっている。 木に対して次のクエリを行うことができる。 1 x val : x番の頂点にvalを足す。x番の直接の子に-valを足す。x番の頂点の２代目の子孫にvalを足す３代目の頂点に-valを足す………
問題 nxnのグリッドがあり(1, 1)から(n, n)へ、上または右に移動することを繰り返して進む。 グリッドのうちm個には障害物があり、そのマスへは入れない。 (1, 1)から(n, n)へ進むことはできるか。 制約条件 n≦10^9 m≦10^5
問題 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
問題 集合A = {1, 2, 3, ..., n}をm個disjointに分割したA1, A2, ..., Amが与えられる。 Aiからk個を選び、それらの和集合Bを作る。 Bの要素を小さい順に並べた数列をb1, b2, ..., b|b|とする。 与えられた数dに対して、 b1≦d, bi+1 - bi≦d（各iで） n + d -…
問題 nxnの小正方形が並んだ正方形がある。大きな正方形の外側は黒い。 この正方形に対して以下の操作をk回行う。 一辺の長さが3以上の奇数の正方形であって、内部が全部白で、外側は黒いものを選ぶ 辺の長さをLとしたとき、内部の小正方形で(L + 1) / 2行目…
問題 n個の点(si, fi, ti)が与えられるので次のQ個のクエリに答えよ。 クエリ：点(x, y, z)に対して、最初のn個の点の中から、s≦x, f≧y, t≧zを満たす点のうち、tがもっとも小さいものの番号を答える。 ただし、最初のn点のtiは全て異なる。 制約条件 n, Q≦10…
問題 n頂点m本の辺からなる重み付き無向グラフが与えられる。 m本の辺それぞれについて、 このグラフの最小全域木に含まれる場合とそうでない場合がある このグラフの最小全域木に必ず含まれる このグラフの最小全域木に含まれない のいずれかを判別せよ。 …
問題 長さnの数列a[i]が与えられる。 この数列に区間[L, R]に一様に1を足すという操作を何回でも行うことができる。 ただし、一度使ったLは二度とLとして使うことができず、一度使ったRは二度とRとして使うことができない。 （[1, 1]で操作をしたら、[1, 2]…
問題 ２次元のグリッドが与えられる。 Sはスタート。.は何もないマス。数字は宝の番号で、#は壁でBは爆弾。 SからスタートしてSまで戻ってくる閉路（同じマスを二回以上通ってもよい）で、宝を囲いたい。 閉路の長さをvとして、囲った宝の価値の総和をwとす…
問題 nxnのグリッドの各マスに'o'か'x'を、次の条件を満たすように入れる。 各マスについて、隣接する４マスのうち、'o'が書かれたマスは偶数個 nxnのうち、k個のマスに入るものがあらかじめ決まっているとき、 残りのマスの埋め方は何通りあるかmod 10^9 + …
