問題 n頂点からなる木がある。木には最初s[i]の値がかかれている。 次の操作をm回行う。 数字tiを手に入れる。捨てるか、好きな木の頂点cを選んで数字を置く。 頂点cにもともとあった数字はcの親に行く。cの親vにあった数字はvの親に行く。 ……と同様に根まで…

問題 n頂点m辺のグラフの全ての頂点を「直接良い状態にするか、良い道路を辿って良い頂点へ辿りつける」ようにしたい。 i番目の頂点が良い状態であるようにするにはci円 j番目の道路はaj, bjを結んでいて双方向に通行可能であり、良い道路にするにはcj円かか…

問題 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'なら場の石を自分のものにする（自…

問題 図があるので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2014Day1&pid=D） 3xnのグリッドに4種類のピースを当てはめて、格子点を結ぶパスを作る。 ピースa, b, c, dがa枚b枚c枚d枚使えるとき グリッドの左端の格子点か…

問題 長さ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 -…

これで全部の問題に解説をつけられた。 解くより解説書くほうがめんどい…… りんごさんが主催した全問DPのコンテストの、全問題の解説＆ソースコード記事へのリンクです。 コンテストのページはhttp://tdpc.contest.atcoder.jp/ Typical DP Contest A コンテ…

問題 幅w高さhのグリッドを、白黒に塗る。 左上および右下のマスは黒であり、左上から右下へ隣接する（辺を共有する）黒い正方形をたどっていけるような塗り方は何通りあるかmod 10^9 + 7で求めよ。 制約条件 w≦6 h≦100

問題 文字列sが与えられる。 sの（必ずしも連続しない）部分文字列でK番目のものを求めよ。 部分文字列は、文字列が同じならどこから切り出したかは区別しない。 K番目が存在しない場合はEelと出力せよ。 制約条件 sは英小文字からなる sの長さ≦10^6

問題 n頂点からなる木が与えられる。 この木を、辺を一本ずつ書いていく。書いている途中の辺は全て連結であるようにしたい。 辺を書く順番は何通りあるかmod 10^9 + 7で求めよ。 制約条件 n≦1000

問題 H階建ての家がある。各階は全て同じ構造をしていて、r部屋からなり、 g[i][j] = 1のとき部屋iから部屋jへ行くことができる。 また、h階の部屋iからはh-1階の部屋iへ降りることができる。（登れない） H階の部屋1から1階の部屋1まで、同じ部屋を２度通ら…

問題 一次元上に猫1, ..., Nをこの順に並べる。 猫同士には仲のよさf[i][j]が定まっている。 i番の猫の幸福度は、i番目の猫から距離1にいる猫の仲のよさの総和である。 猫を最適に並べたときの、幸福度の総和の最大値を求めよ。 制約条件 N≦1000 f[i][j]の絶…

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