Go で AtCoder Educational DP Contest F - LCS を解いてみた #Go

Educational DP Contest F - LCS を解きました。

問題

文字列 s および t が与えられます。 s の部分列かつ t の部分列であるような文字列のうち、最長のものをひとつ求めてください。
注釈
文字列 x の部分列とは、 x から 0 個以上の文字を取り除いた後、残りの文字を元の順序で連結して得られる文字列のことです。
( https://atcoder.jp/contests/dp/tasks/dp_f より引用)

制約

s および t は英小文字からなる文字列である。
$ 1 \le |s|, |t| \le 3000 $

考え方

LCS (Longest Common Subsequence) は DP における超典型の問題で、 diff コマンドみたいなメジャーな応用があります。

DPは苦手意識がありますが、 LCS は解いた記憶があったので楽勝だと思ったら、普通と違っていたのが「最大長を求めよ」ではなく、「最長の文字列を求めよ」となっているところです。適当に書いて出したら無事死亡。
「ACできない！ナンデ！？」と思いながら試行錯誤してなんとか自力 AC できましたが、たぶんこれまで自分では「最大長を求めよ」のパターンしか解いたことがなかったみたいです。

初 AC のコードは DP 計算用の2次元配列にリストによるスタックを保持しておいて、共通シーケンスを枝分かれさせつつスタックしていく感じで書きました。
go の配列への append もそれと同じようなもんだろ、と思ってましたが、 append したときに Capacity がオーバーしない限りは既存の配列を上書きしてしまうので、途中で中身が破壊されてしまいます。
一方で文字列や配列を保持してコピーするとかなり効率が悪いので、場合によっては TLE してしまいます。

実践的には次のようなやり方が良いようです。

まず、最大長を求める場合と同じように dp の表(int の2次元配列)に共通シーケンスの最大長を記録していく
表が埋まったら右下から $ s[i] == t[j] $ の場所、つまり共通シーケンスの最大長を増やしたタイミングの $i$ を見つけては $ s[i] $ から共通シーケンスを復元していく

LCS の文字列の求め方について、 Qiita 上では @_rdtr さんの記事に詳しい解説がありました。

提出コード

最終的に次のようなコードを書きました（抜粋）。全体はこちら

func main() {
    defer stdout.Flush()
    s := []byte(readString())
    t := []byte(readString())
    dp := make([][]int, len(s))
    for i := range dp {
        dp[i] = make([]int, len(t))
    }

    for i := range dp {
        for j := range dp[i] {
            if 0 < i {
                dp[i][j] = dp[i-1][j]
            }
            if 0 < j {
                dp[i][j] = max(dp[i][j], dp[i][j-1])
            }
            if s[i] == t[j] {
                p := 0
                if 0 < i && 0 < j {
                    p = dp[i-1][j-1]
                }
                p++
                dp[i][j] = max(dp[i][j], p)
            }
        }
    }

    i := len(s) - 1
    j := len(t) - 1

    b := make([]byte, 0)
    for 0 <= i && 0 <= j && 0 < dp[i][j] {
        for 0 < i && dp[i][j] == dp[i-1][j] {
            i--
        }
        for 0 < j && dp[i][j] == dp[i][j-1] {
            j--
        }
        b = append(b, s[i])
        i--
        j--
    }

    for i, j := 0, len(b)-1; i < j; i, j = i+1, j-1 {
        b[i], b[j] = b[j], b[i]
    }
    println(string(b))
}

func max(a, b int) int {
    if a < b {
        return b
    }
    return a
}