https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-procon-tahoiya-ga-tokuiya/problem

前提知識

動的計画法

解説

https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-procon-tahoiya-ga-tokuiya/submissions/code/1317862484

競技プログラミングでは編集距離といえば、DPで解くという典型がある。
今回もこの典型を発展させることで解ける。

DP[i1][i2][i3] := 文字列S1をi1文字目まで、S2をi2文字目まで、S3をi3文字目までカバーしたTを作成したときのコストの最小値
これの遷移を、Tに文字を追加する操作として考えよう。
Tに追加する文字は26パターンありそうだが、実際はS1[i1]かS2[i2]かS3[i3]のどれかを採用すればいい。
全く関係無いものを採用するより、少しでも関係あるものをなるべく採用する方が最適手に近づくであろうということは雰囲気分かるだろう。
といっても26パターンやっても問題ない。
DPでは遷移を最適解に絞ることが本質の問題もあるが、最適解に至る遷移が含まれていれば、無駄な遷移があっても問題ないし、
それを許容することで実装を簡単にするということも強くなるには必要だろうと思う。

あとは、Tに3パターンの文字を追加することを考えればいい。
文字列の最大値らへんに注意しながら、遷移を作る。
コードの遷移にコメントをつけると以下のようになる。

         // T += S1[i1]
            if (i2 < L2 and i3 < L3) {
                chmin(dp[i1 + 1][i2 + 1][i3 + 1], dp[i1][i2][i3] + (S1[i1] != S2[i2]) + (S1[i1] != S3[i3])); // S1[i1]をi2,i3に対応させる（変更が必要なら変更する）
            }
            if (i2 < L2) chmin(dp[i1 + 1][i2 + 1][i3], dp[i1][i2][i3] + 1 + (S1[i1] != S2[i2])); // S1[i1]をi2に対応させる（i3の方はS1[i1]を消す）
            if (i3 < L3) chmin(dp[i1 + 1][i2][i3 + 1], dp[i1][i2][i3] + 1 + (S1[i1] != S3[i3])); // S1[i1]をi3に対応させる（i2の方はS1[i1]を消す）
            chmin(dp[i1 + 1][i2][i3], dp[i1][i2][i3] + 1); // S1[i1]を消す

最後の遷移であるが、S1[i1]を対応させて、i2,i3は削除することで+2の遷移が行えそう。
しかし、それをやるよりもS1[i1]自体をTに足さずに消すことで+1で同様の結果が得られるので、そっちを採用している。
これをあと2パターンやってくと、DP[L1][L2][L3]が答え。

int L1, L2, L3;
string S1, S2, S3;
int dp[101][101][101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> L1 >> S1 >> L2 >> S2 >> L3 >> S3;

    rep(i1, 0, L1 + 1) rep(i2, 0, L2 + 1) rep(i3, 0, L3 + 1) dp[i1][i2][i3] = inf;
    dp[0][0][0] = 0;
    rep(i1, 0, L1 + 1) rep(i2, 0, L2 + 1) rep(i3, 0, L3 + 1) {
        if (i1 < L1) {
            // T += S1[i1]
            if (i2 < L2 and i3 < L3) {
                chmin(dp[i1 + 1][i2 + 1][i3 + 1], dp[i1][i2][i3] + (S1[i1] != S2[i2]) + (S1[i1] != S3[i3]));
            }
            if (i2 < L2) chmin(dp[i1 + 1][i2 + 1][i3], dp[i1][i2][i3] + 1 + (S1[i1] != S2[i2]));
            if (i3 < L3) chmin(dp[i1 + 1][i2][i3 + 1], dp[i1][i2][i3] + 1 + (S1[i1] != S3[i3]));
            chmin(dp[i1 + 1][i2][i3], dp[i1][i2][i3] + 1);
        }
        if (i2 < L2) {
            // T += S2[i2]
            if (i1 < L1 and i3 < L3) {
                chmin(dp[i1 + 1][i2 + 1][i3 + 1], dp[i1][i2][i3] + (S2[i2] != S1[i1]) + (S2[i2] != S3[i3]));
            }
            if (i1 < L1) chmin(dp[i1 + 1][i2 + 1][i3], dp[i1][i2][i3] + 1 + (S1[i1] != S2[i2]));
            if (i3 < L3) chmin(dp[i1][i2 + 1][i3 + 1], dp[i1][i2][i3] + 1 + (S2[i2] != S3[i3]));
            chmin(dp[i1][i2 + 1][i3], dp[i1][i2][i3] + 1);
        }

        if (i3 < L3) {
            // T += S3[i3]
            if (i1 < L1 and i2 < L2) {
                chmin(dp[i1 + 1][i2 + 1][i3 + 1], dp[i1][i2][i3] + (S1[i1] != S3[i3]) + (S2[i2] != S3[i3]));
            }
            if (i1 < L1) chmin(dp[i1 + 1][i2][i3 + 1], dp[i1][i2][i3] + 1 + (S1[i1] != S3[i3]));
            if (i2 < L2) chmin(dp[i1][i2 + 1][i3 + 1], dp[i1][i2][i3] + 1 + (S2[i2] != S3[i3]));
            chmin(dp[i1][i2][i3 + 1], dp[i1][i2][i3] + 1);
        }
    }

    cout << dp[L1][L2][L3] << endl;

    //rep(i1, 0, L1 + 1) rep(i2, 0, L2 + 1) rep(i3, 0, L3 + 1) printf("dp[%d][%d][%d] = %d\n", i1, i2, i3, dp[i1][i2][i3]);
}

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

hamayanhamayan's blog

Tahoiya ga Tokuiya [TSG LIVE! 4 プログラミングコンテスト E]

前提知識

解説