問題 英小文字からなる文字列が与えられる。 文字列の必ずしも連続しない部分文字列のうち、回文であるものは何種類あるか。 同じ回文は一つと数える。 制約 文字列の長さ2000以下。

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

問題 黒と白の円盤を積み上げてタワーを作る。タワーは以下の条件を満たす必要がある 一枚以上の円盤がある 円盤の厚さの合計はl以下 最も外側の円盤は黒 同じ色同士の円盤が隣り合ってはいけない 黒の円盤は厚さ1またはkのどちらかを選ぶことができて、白の…

問題 各成分が0, 1であらわされる行列Aが与えられる。 Aの行の部分集合A[i]で、任意の列jに対してΣi_s[i][j]が偶数になるものを考える。 このようなA[i]のうち最大のサイズはいくつか。 例）Aが 010 011 110 101 だったら、2, 3, 4行目を選ぶと全ての列の和…

問題 n個の箱があり、i番目の箱は 時刻in[i]に倉庫に入り、out[i]に倉庫から出る。 この荷物は重さがw[i]であり、上にs[i]までの荷物を載せることができる。 この荷物を倉庫に出し入れするとv[i]円もらえる。 倉庫には、同時に全体でSの重さの荷物しか入れら…

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

問題 n人の人が一列に並んでいて、k個のゴンドラにわけて乗せる。 一つのゴンドラには何人でも乗れるが、乗せる順番は並び順でなければならない。 人同士には仲の悪さが決まっていて、i番目とj番目の人の仲の悪さはa[i][j] (=a[j][i]). 一つのゴンドラ内の不…

問題 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枚使えるとき グリッドの左端の格子点か…

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

問題 n枚の袋があって、i番目の袋の中にはa[i]枚のコインが入っている。コインは全体でs枚である。 ただし、袋の中にはさらに別の袋が入っていることがある。 a[i] = {1, 1, 3}で、全体でコインが3枚ということがある。 （3番目の袋には1番目の袋と2番目の袋…

問題 長さnの数列a[i]が与えられる。 aの任意の空でない区間[l, r]で、a[i]の符号を好きに反転してよい。 このようにして[l, r]内の総和が0になるようにする方法は何通りあるか。 制約条件 n≦1000 -1000≦a[i]≦1000 a[i]の総和≦10000

これで全部の問題に解説をつけられた。 解くより解説書くほうがめんどい…… りんごさんが主催した全問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の数列a[i]が与えられる。 この数列に区間[L, R]に一様に1を足すという操作を何回でも行うことができる。 ただし、一度使ったLは二度とLとして使うことができず、一度使ったRは二度とRとして使うことができない。 （[1, 1]で操作をしたら、[1, 2]…

問題 n個の円があり、それぞれの中心はx軸上にある。 i番目の円の中心はxi, 半径はriである。 円の列C1, C2, ..., Cnは、円Ci+1がCiの真に内部に入っているときにターゲットであると言う。作れるターゲットの最大のサイズを求めよ。 制約条件 n≦100000

問題 一直線上にn個の目標があり、i番目の座標はxi. xの位置にボールを投げると、1/3の確率でx-1, x, x+1のどれかに飛ぶ。 最適な戦略を取った時、全ての目標を倒すまでのボールを投げる回数の期待値はいくつか。 前に投げたボールの結果を見て、ボールを投…

問題 i, wからなる文字列が与えられる。 この文字列から、連続する"iwi"という三文字を取り除く操作が何度でもできる。 操作ができる回数の最大値を求めよ。 制約条件 文字列の長さ≦300

問題 n個の品物があり、i番目の品物は重さがwi, 色がci, 価値がviである。 ナップサックに重さの合計がW以下, 色の合計がC色以下であるように品物を詰める。 価値の最大はいくつか。 制約条件 n≦100 W≦10000 C≦50

問題 N頂点からなる有向グラフが与えられる。 最初全ての頂点は白で、グラフにパス（同じ頂点を何度通ってもよい）を描くと、 パス上の頂点の色が全て黒になる。 この操作を２回できるとき、黒にできる頂点の個数の最大値を求めよ。 制約条件 N≦300

問題 0, 1からなるn個の文字列wiが与えられる。 wiを並べて書いた文字列で、長さがLであるものはいくつあるか。 出来る文字列が同じならば、wiの並べ方は区別しないものとする。 制約条件 答えはmod 10^9 + 7で求める n≦510 wi ≦8 L≦100

問題 N頂点からなる木に、交わらないK本のパスを書く書きかたは何通りあるか。mod 10^9 + 7で求めよ。 パスを書く順序は区別しない。 制約条件 N≦1000 K≦50

問題 英小文字からなる文字列で、 aをちょうどfreq[1]個 bをちょうどfreq[2]個… zをちょうどfreq[26]個含み、同じ文字が隣り合わないものはいくつあるか、 mod 10^9 + 7で求めよ。 制約条件 freq[i]≦10

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

問題 無向木で表されるような島と橋が与えられる。 辺の重みが、橋を渡る時間であり、その橋を壊す時間である。（両者は等しい） 好きな島から出発し、橋を渡るか、今いる島につながっている橋を壊すかすることができる。 終了時には好きな島にいてよい。 全…