二次元ナップサックDP
LCS (Longest Common Subsequence) によく似た DP！！ 問題へのリンク 問題概要 (意訳) 長さ の整数列 と、長さ の整数列 が与えられる。これらに以下の操作を繰り返すことで、要素数が等しくなるようにしたい。 A の要素を 1 つ選んで削除する B の要素を 1…
結構悩んだ！！！ 問題へのリンク 問題概要 長さ の文字列 と、長さ の文字列 が与えられる。 の連続する部分文字列 と、 の連続する部分文字列 をとったとき、 とする。 の考えられる最大値を求めよ。 制約 考えたこと 単純にそれぞれの部分文字列を探索し…
三乗の解法はすぐに出てくるので、それを上手に高速化する！ 問題へのリンク 問題概要 のグリッドが与えられる。"." マス (通路) には行けるが "#" マス (壁) には行けない。左上のマスから右下のマスへと行きたい。毎回のターンで以下のいずれかの行動をと…
最初、同じ行の「連続する 3 個」しか選べないのだと誤読してしまった... 問題へのリンク 問題概要 二次元座標平面上で、(1, 1) から (R, C) へと格子点を辿って最短経路で進みたい (上か右にしか行けない)。 K 個の座標 () に価値 のアイテムがある。通った…
気持ち良く詰められた 問題へのリンク 問題概要 のオブジェに対し いずれかの列を選び、その列を一段沈める (このとき最下段ブロックは消える) という操作を 回繰り返してオブジェを完全に消し去りたい。1 回の操作に要するコストは、そのブロックがその時点…
もう文字列は怖くないっ！！！ 文字列検索に関するライブラリが充実していれば怖いものがない。でも文字列のことを知らなくても実は DP でも解ける！！！ Suffix Array Z-algorithm (editorial 解) ロリハ + 二分探索 「ロリハ + 二分探索」の高速化 (editor…
共通部分列に関する問題！！！！！ 最長共通部分列問題は有名だけど、今回は共通部分列を数え上げる問題。 問題へのリンク 問題概要 2 つの数列 が与えられる。 と の共通部分列が何通りあるかを求めよ。 ただし、 や から抜き取ってできる文字列が同じもの…
面白かった 問題へのリンク 問題概要 文字列 が与えられる。あらかじめ文字列の中の 文字を自由に変更することができる。 こうして得られた文字列と、それを反転した文字列の LCS (最長共通部分列) の長さとして考えられる最大値を求めよ。 制約 考えたこと …
