「最長共通部分列問題(LCS)」
文字列 $X$ と $Y$ の共通部分文字列の長さの最大値を求めてください。aoj
・クエリの数は $150$ 以下。
・$X, Y$ の長さは $1{,}000$ 以下。
・$X, Y$ のいずれかの長さが $100$ を超えるとき、クエリの数は $20$ 以下。
※共通部分文字列: 文字列 $X$ から $0$ 個以上の任意の要素を取り除き、文字列 $Y$ からも $0$ 個以上の任意の要素を取り除いたとする。
得られる文字列が一致したとき、これを $X$ と $Y$ の共通部分文字列という。
答えへのリンク

「最長増加部分列問題(LIS)」
数列 $a$ の増加部分列の長さの最大値を求めてください。テストケース
1行目はクエリの数($q$ とする)。2行目からは1行目が $a$ の長さ、2行目は $a$ が空白区切り、の2行1セットで $q$ 個。
・$q$ は $100$ 以下。
・$a$ の長さは $1{,}000$ 以下。
・$a$ の各要素は $1{,}000$ 以下。
※増加部分列: 数列 $a$ から $0$ 個以上の任意の要素を取り除いたとする。得られる数列が狭義単調増加であるとき、これを $a$ の増加部分列という。
答えへのリンク

アリスとボブがじゃんけんを $N$ 回します。
ボブが出す手をアリスは全て知っています。
アリスがちょうど $score$ 回勝つために $N$ 回出す手のパターン数を $\bmod 1{,}000{,}000{,}007$ で求めてください。SRM 653 Div2 Med
・$1 \le N \le 2{,}000$
・$0 \le score \le 2{,}000$
答えへのリンク

$N$ 個の商品の定価はそれぞれ $M_{i}$ 円です。
商品を購入すると「それまでに購入した商品の定価の合計」を $1{,}000$ で割った余りを値引きしてくれます。
最終的な購入金額が最小になるように商品を1つずつ $N$ 個購入した場合の購入金額を求めてください。yukicoder No.286
・$N$ は $15$ 以下。
・それぞれの商品の定価は $10{,}000$ 以下。
答えへのリンク

太古の文明には $N$ 個の建物がありました。$kind$ という $N$ 個の要素からなる配列のそれぞれは建物の種類を表しています。
考古学者がそのうちいくつかの種類の建物を全部で $K$ 個発掘しました。$found$ という $K$ 個以下の要素からなる配列のそれぞれも建物の種類です。
考古学者が発掘した建物を「$N$ 個のどれを発掘したか」という $K$ 個の要素からなる配列で表現したとき、
その配列のパターン数を数えてください。SRM 584 Div2 Hard
・建物の種類は $1$ 以上 $50$ 以下の整数で表現する。
・$1 \le N \le 50$
・$found$ の各要素に重複は無い。
・$found$ の各要素は $kind$ に必ず1つはある。
・$\left| found \right| \le K \le N$
答えへのリンク