pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #338 (Div. 2) C. Running Track

問題文

codeforces.com

解法

次のような DP で解ける。

  • dp[i] := t の先頭 i 文字を構成するのに必要な最小回数

t[i..] の先頭 L 文字が s または rev(s) に含まれていれば dp[i] から dp[i+1]~dp[i+L] に遷移できる。s と t の LCP は O(|s||t|) の DP で計算できるので、これを使って最大の L を O(|s||t|) で計算しよう。

DP の復元が必要なので実装は辛い。

Codeforces Round #338 (Div. 2) C. Running Track

Good bye コンテストで得た知識を使えて嬉しい。でもコンテスト中に通したかった。