かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

Codeforces Round #635 (Div. 2) E - Kaavi and Magic Spell

競技プログラミング 解説 Codeforces 文字列 動的計画法 典型

問題はこちら

問題概要

長さ{1\le N\le 3000}の文字列{S}と長さ{1\le M\le N}の文字列{T}が与えられる. 空文字列{A}を用意して, {A}の先頭か末尾に{S_i}を挿入していくことを考える. {A}の接頭辞が{T}に等しくなるような挿入の仕方の総数を998244353で割った余りを求めよ.

思考の流れ

制約や操作からDPっぽさを感じるのでDPを考える.
「{S}の{i}番目までを使用」ってのはいるとして, 「{T[j:k]}になる」というのがあればよさそうだが空間計算量{O(NM^2)}で無理.

{\downarrow}

{i}が決まると{T[j:k]}の長さも決まるので{k}はいらないっぽい.
{dp[i][j]}を「{S}の{i}番目までを使って{T[j:j+i]}と一致する文字列を作るときの操作の数」とする.
{j+i}が範囲外になることがあるが, そのときは範囲内までのものを考える. つまり{T[j:\min(j+i,|T|)]}を考える.

  • {S[i]=T[j](j\le |T|-1)}のとき
    　{T[j+1:j+i]}までできているときに, 前に{S[i]}をつければ{T[j:j+i]}が作れる.

  • {S[i]=T[j](j==|T|)}のとき
    　いままでどのような操作を行って, どのような文字列になったかは関係ない. よって{2^i}を足せばいい.

  • {S[i]=T[j+i]}のとき
    　{T[j:j+i-1]}までできているときに, 後ろに{S[i]}をつければ{T[j:j+i]}が作れる.

  • {|T|\lt j+i}のとき
    　{T[j:j+i-1]}までできているときに, 後ろに{S[i]}をつけると{T[j:j+i]}が作れる.

以上のことを遷移式としてやるとできる. 具体的な実装はプログラムを参照.

提出プログラム

https://codeforces.com/contest/1337/submission/79305770

感想

DP定義の時点で分からなかった. どの状態がいらないか判断するの難しい.

コドフォ民の正解率高かったけどコドフォ民はDPが得意?