betrue12 https://blog.hatena.ne.jp/betrue12/ ARMERIA https://betrue12.hateblo.jp/ AtCoder プログラミング 競技プログラミング お題箱より。 A - YahooYahooYahoo 解法 「編集距離DP」を知ろう まずは「編集距離DP」なるものを説明します。2つの文字列 の編集距離とは、文字列 に以下の操作を好きな順序で行って文字列 に一致させるための、操作回数の最小値です。 置換： の任意の1文字を選んで、それを任意の1文字に置き換える。 削除： の任意の1文字を選んで、それを取り除く。 挿入： の任意の位置に、任意の1文字を挿入する。 この3操作は今回の問題と同じですね。これは以下のようなDPで解くことができます。 文字列 の前から 文字目までを文字列 の前から 文字目までに一致させるための操作回数の最小値 このD… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbetrue12.hateblo.jp%2Fentry%2F2019%2F08%2F24%2F014746" title="「みんなのプロコン」本選 A - YahooYahooYahoo - ARMERIA" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.blog.st-hatena.com/images/theme/og-image-1500.png Hatena Blog https://hatena.blog 2019-08-24 01:47:46 rich https://betrue12.hateblo.jp/entry/2019/08/24/014746 1.0 100%