みんなのプロコン (2017) 本選 A - YahooYahooYahoo

AtCoder みんなのプロコン みんなのプロコン2017本戦 問題記録 DP 編集距離

問題概要

与えられた文字列Sに対して以下の3種類の操作をひとつ選んで適用する、ということを繰り返し、Sを"yahoo"という文字列が0回以上繰り返された形にしたい。最小何回の操作でこれを達成できるか求めよ。

  • 操作1: Sの任意の1文字を別の文字に置き換える
  • 操作2: Sの任意の1文字を取り除く
  • 操作3: Sの任意の位置に任意の文字を挿入する

|S| <= 105

解法

編集距離DPだが、目標となる文字列がたくさんありうるので状態を設計するのが難しい。結論からいうと、一致させる目標としては以下の5つだけを考えればよい。

  • (yahooの0回以上の繰り返し)
  • (yahooの0回以上の繰り返し) + y
  • (yahooの0回以上の繰り返し) + ya
  • (yahooの0回以上の繰り返し) + yah
  • (yahooの0回以上の繰り返し) + yaho

あとは上の5つのいずれかに一致させるコストを計算するDPをやっていけばよい。具体的には

dp(i, j) = i文字目までを 「yahooの0回以上の繰り返し + yahooのj文字目まで」 という形にするための最小コスト (jは0～4）

とする。DPの遷移は基本的に編集距離DPと同じ（たぶん）。

感想

1年くらいわからなかった

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

immutable int INF = 1 << 29;
immutable string yahoo = "yahoo";

void main() {
    auto S = readln.chomp;
    auto N = S.length.to!int;
    
    auto dp = new int[][](N+1, 5);
    foreach (i; 0..N+1) dp[i].fill(INF);
    foreach (j; 0..5) dp[0][j] = j;

    foreach (i; 0..N) {
        foreach (j; 0..5) {
            // 変更
            dp[i+1][(j+1)%5] = min(dp[i+1][(j+1)%5], dp[i][j] + (S[i] != yahoo[j]));
            // 削除
            dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1);
        }
        // 挿入
        foreach (j; 0..10) {
            dp[i+1][(j+1)%5] = min(dp[i+1][(j+1)%5], dp[i+1][j%5]+1);
        }
    }

    dp[N][0].writeln;
}