AtCoder Beginner Contest 185 E - Sequence Matching 解説

やらかし反省録が増えました！！！！！！！！！！！！！！！！！！！

問題リンク

https://atcoder.jp/contests/abc185/tasks/abc185_e

問題概要

要素からなる整数列 があります。 からいくつかの要素をコスト で取り除くことができます。取り除いたあと、 の要素数が同じでなくてはなりません。
取り除いたあとの について である要素があれば、その個数だけコストが ずつ上乗せされます。
コストの最小値を求めてください。

制約

考察・解法

のうちそれぞれ から 要素目までを見たときのコストの最小値で DP を考えます。これを と定義します。 のときは、空の数列であるとします。
DP なので、初期条件及び についての遷移が分かれば良いです。

初期条件ですが、 とすると、空の数列と 要素の数列におけるコストは なので、 です。 のときも同様です。

では、 をそれまでに見た値で計算できないか考えます。
以下のように パターンに分けて説明します。

• の最後の数を削除するとき
  コスト で可能です。よって、 です。

• の最後の数を削除するとき
  同様に、 です。

• の最後の数をどちらも残すとき
  この場合、 であれば違う値であるときのコストは発生しないので、 です。
  そうでない場合は、違う値であるときのコストが発生します。 です。
  なお、 の両方を削除することは無意味です。両方残せば高々 の追加のコストであるからです。

以上の通りの DP をすればよいです。

実装

実装を展開する

       public void Solve()
        {
            var (n, m) = cin.ReadValue<int, int>();
            var a = cin.ReadIntArray(n);
            var b = cin.ReadIntArray(m);
            var dp = new int[n + 1][];
            for (int i = 0; i < n + 1; i++)
            {
                dp[i] = new int[m + 1];
            }
            for (int i = 0; i < n + 1; i++)
            {
                dp[i][0] = i;
            }
            for (int i = 0; i < m + 1; i++)
            {
                dp[0][i] = i;
            }
 
            for (int i = 1; i <= n; i++)
            {
                for (int j = 1; j <= m; j++)
                {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (a[i - 1] == b[j - 1]) dp[i][j]--;
                    dp[i][j].Chmin(dp[i][j - 1] + 1);
                    dp[i][j].Chmin(dp[i - 1][j] + 1);
                }
            }
            Console.WriteLine(dp[n][m]);
        }

ACコード: https://atcoder.jp/contests/abc185/submissions/18769369

感想

コンテスト本番やらかし案件です。ABCDF の 5 完時点では 50 位橙パフォだったのに、E が解けずずるずると水パフォまで落ちてしまいました。うわああ……。

この問題は編集距離を求める DP そのものであり、典型です。典型を典型と見抜けなかったのもまずいのですが、この程度の DP を再発明できなかった (しかも過去に類似の DP である LCS の DP で痛い目に遭っているのに！) のは、正直に言って青コーダー失格レベルだと思います。大反省です。

fairy-lettuce.hatenadiary.com

DP で頭が爆発することが多いし、今回も過去の教訓があったにも関わらずこれを通せなかったし、反省として、今週は DP 強化週間とします。EDPC 及び TDPC を全部埋める気でいきます。対戦よろしくお願いします。