Codeforces Round #683 Div.2-D/Div.1-B - Catching Cheaters 解説

Rated コンテストにたくさん出たいのでこどふぉに出ました。冷えました。つらいです……。

今回はその冷えたこどふぉで解けなかった問題の解説です。解けて然るべき問題を解けなかった時の辛さは全競プロer共通だと勝手に思っています。

問題リンク

https://codeforces.com/contest/1447/problem/D

問題概要

文字列 $A,\ B$ の部分文字列を $C,\ D$ とします。 $C,\ D$ のスコアを $4\times LCS(C,\ D)-|C|-|D|$ とします。ただし、 $LCS(C,\ D)$ は $C,\ D$ の最長部分列の長さとします。スコアの最大値を求めて下さい。
部分文字列は連続していなければならず、部分列は連続していなくてもいいことに注意して下さい。

制約

$1\le |A|,\ |B|\le 5000$

考察

優しいことに、最長部分列問題の Wikipedia 解説記事のリンクが貼られているので、最長部分列問題の日本語記事を漁ります(例えばこれなどが分かりやすいです)。
これを読むと、LCS と似たような感じのDPが出来たら嬉しいなという気持ちになります。dp[i][j]を $A$ の $i$ 文字目、 $B$ の $j$ 文字目までの最大スコアとしましょう。
LCS ではスコアは $LCS(C,\ D)$ でしたが、今回の問題でのスコアは $4\times LCS(C,\ D)-|C|-|D|$ です。 $4\times LCS(C,\ D)$ が増えるタイミングはLCS単体の時同様ですが、 $|C|,\ |D|$ が厄介です。しかし、これらが変化するタイミングは DP 遷移でいうと $i,\ j$ のどちらかが増えたときなので、dp[i-1][j]またはdp[i][j-1]から遷移する際にスコアを $1$ 減らすと良いと分かります。

解法

先程同様、dp[i][j]を $A$ の $i$ 文字目、 $B$ の $j$ 文字目までの最大スコアとします。dp[i][j]は、 $A_i=B_j$ を満たすとき $2$ 、そうでないとき $0$ で初期化します。
このとき、DP 遷移式は次のように¹なります。貰う DP で考えるものとします。

$dp_{i,\ j}=dp_{i-1,\ j-1}+2\ (A_{i-1}=B_{j-1})$
$dp_{i,\ j}=\max(dp_{i-1,\ j},\ dp_{i,\ j-1})-1\ (otherwise)$

あとはこれを実装するだけです。

実装・ACコード

実装を展開する

public static void Solve(Scanner cin)
{
    var (n, m) = cin.ReadValue<int, int>();
    var a = cin.ReadString();
    var b = cin.ReadString();
    var dp = new long[n][];
    for (int i = 0; i < n; i++)
    {
        dp[i] = new long[m];
        for (int j = 0; j < m; j++)
        {
            if (a[i] == b[j])
            {
                dp[i][j] = 2;
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            var plus = 0;
            if (a[i] == b[j])
            {
                if (0 <= i - 1 && 0 <= j - 1)
                {
                    dp[i][j] = Math.Max(dp[i][j], dp[i - 1][j - 1] + 2);
                }
            }
            if (0 <= i - 1)
            {
                dp[i][j] = Math.Max(dp[i][j], dp[i - 1][j] - 1);
            }
            if (0 <= j - 1)
            {
                dp[i][j] = Math.Max(dp[i][j], dp[i][j - 1] - 1);
            }
        }
    }
    long ans = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (ans < dp[i][j]) ans = dp[i][j];
        }
    }
    Console.WriteLine(ans);
}

ACコード: https://codeforces.com/contest/1447/submission/98498090

展開機能を覚えました。見やすいですね。

感想と反省

LCS は DP で解けるけどこの問題は DP 以外の天才解法があるのか……？ということに固執して正しい方向の解法に辿り着くまでに時間がかかってしまいました……。解法ガチャでは自明にありえない解法を弾く能力も大切ですね。
というか、この問題は LCS のような DP をしないと計算量的にヤバいとか色々あるので、必然性をもって DP 解をすぐに考察するべきでした。

また、DP であるという方針が立っても遷移が間違っていました(変遷でスコアが増える $(i,\ j)$ から $(i+1,\ j+1),\ (i+2,\ j+1),\ (i+1,\ j+2)$ への変遷しか考えていなかった)。DPに慣れないといけないなと痛感しました。

おまけ話

最近コンテストに出たりバチャをしたりしていて思ったことですが、Upsolve を怠る癖があったり、一度間違えたことをきちんと吸収できていない気がしたので、これから解法ブログを頻繁に更新していくことにします。知識の定着が目的なので、効率のため記事は校正・推敲をあまりせず短い時間で書き上げます。誤字脱字等の指摘や、解説記事の方向性についてご意見がある方は、是非コメントを下さい！
なお、基本的にコンテストでの失敗から得られた知識を忘れずにまとめておきたいときに更新することにします²。他人と違う解法での AC や、高難易度の AC を記録していくという観点からでの丁寧な解説記事はこれまで通り続けます。

ノートを見やすくまとめて後から復習できるようにしたことはあまりしたことがないのですが、三日坊主にならず上手く続くといいですね。

どうでもいいんですけど、はてなブログの Markdown 記法で書いた時の TeX の扱いが面倒くさすぎて、きちんと align することを放棄しました。直すのは後回しです。ごめんなさい。↩
これ、どこかで見たことあるなと思ったんですけど、東大のシケプリ制度にそっくりな気がします。↩

Growth Record of Lettuce Farm

競プロの記録・解説をします