はまやんはまやんはまやん

hamayanhamayan's blog

LCS [Educational DP Contest / DP まとめコンテスト F]

競技プログラミング

https://atcoder.jp/contests/dp/tasks/dp_f

前提知識

解説

https://atcoder.jp/contests/dp/submissions/3947645

恐らく想定解ではないライブラリによる筋肉解法です
　
dp[s][t] := Sのs文字目まで、Tのt文字目まで使ってできる共通部分列の最大長
これを更新していく。
これの更新にはライブラリは必要ではないが、今回は復元をする必要があるので、ライブラリとあるテクを使っている。
　
まず、dp[s][t]ってのをどう思いつくかという部分であるが、正直、2つ文字列与えられて、どちらの長さも10^3位だったら、dp[s][t]を使うという問題をむちゃくちゃ見たから、それで考え始めたというのに尽きる。
DP問題では「復元」というパートがある場合がある。
これは、DP結果から、最適な結果が得られるパスを取得して、ある結果を出すことであり、DPの他に、遷移元を保持していくことで実現できる。
なので、
pre[s][t] := dp[ss][tt] -(c)-> dp[s][t] という遷移の{ss,tt,c}
も同時に更新していく。
このような遷移元を保持して復元する問題は良く見かける。
（遷移元を保持する必要は必ずしもないが、自分はこっちが好き）
　
遷移をどうするかという問題があるが、dp[s][t]の状態からある文字cを次に採用するときは、どちらの文字列についてもなるべく近い文字cを採用するのがいい。
DPテクの「遷移が多い場合は貪欲法を使うことで最適であろう遷移を絞ることができる」である。
ある文字cとして、どれを採用するかと言うのは、本当であれば、Sのs文字以降の文字cの個数をcs, Tのt文字以降の文字cの個数をctとすると、cs*ct通りある。
しかし、どちらも最も近い文字を採用するのが最適であるので、これだけ使う。
すると、遷移が26通りになるので、状態が|S|×|T|で間に合う。
　
ある文字cについて、最も近い座標をStringMaster.getNextというので取得しているが、独自ライブラリなので、気になる人は内部実装を見てみてほしい。
やっていることは累積minを使った実装である。
nxt[i][c] := i番目の文字以降で文字cが初めて現れる座標
をうまく累積minで構築している。
　
こうすると、dp[ss][tt] -(c)-> dp[s][t] という遷移を作れるので、DPをして復元をする。
復元パートはwhileを使って、初期状態になるまで戻すという感じ。

string S, T;
int NS, NT;
int dp[3010][3010];
tuple<int, int, char> pre[3010][3010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S >> T;
    NS = S.length(), NT = T.length();
 
    StringMaster SMS(S);
    StringMaster SMT(T);
 
    rep(s, 0, NS) rep(t, 0, NT) rep(c, 0, 26) {
        int ss = SMS.getNext(s, char('a' + c));
        int tt = SMT.getNext(t, char('a' + c));
 
        if (ss < NS and tt < NT) {
            if (chmax(dp[ss + 1][tt + 1], dp[s][t] + 1)) {
                pre[ss + 1][tt + 1] = make_tuple( s, t, char('a'+c) );
            }
        }
    }
 
    int ma = 0;
    rep(s, 0, NS + 1) rep(t, 0, NT + 1) chmax(ma, dp[s][t]);
 
    rep(s, 0, NS + 1) rep(t, 0, NT + 1) if (dp[s][t] == ma) {
        string ans = "";
        while (s != 0 and t != 0) {
            int ss, tt; char cc;
            tie(ss, tt, cc) = pre[s][t];
            ans += cc;
            s = ss, t = tt;
        }
        reverse(all(ans));
        cout << ans << endl;
        return;
    }
 
}