drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AtCoder300点 ABC-C 灰色diff NoviSteps4Q Greedy:辞書順最小を求める 辞書順 Greedy 最小回数・最小個数を求める 最適化問題 文字列 操作 SをTにすることが目的の操作の問題 操作:1文字を変更する 操作回数を最小化せよ、という問題だけど、実際には「複数ある場合は辞書順最小のものを求めよ」という部分に本質がある問題！ 問題へのリンク 問題概要 文字列 は文字数が等しい。 に対して「1 文字変更する」という操作を繰り返すことで にしたい。 そのうちの最小回数のものを求めよ（最小回数を とする）。 複数通りあるときは、 回目の操作後の文字列 をこの順に concat してできる文字列が辞書順最小であるものを求めよ。 制約 考えたこと 最小回数はとてつもなく簡単に求められることに注意しよう！！（意外と忘れがちなのだ） それは、 であるような の個数である。 のハミング距離などとも呼ばれている値で… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2024%2F09%2F13%2F002646" title="AtCoder ABC 370 C - Word Ladder (4Q, 灰色, 300 点) - けんちょんの競プロ精進記録" 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.user.blog.st-hatena.com/default_entry_og_image/80936665/1687765056723440 Hatena Blog https://hatena.blog 2024-09-13 00:26:46 rich https://drken1215.hatenablog.com/entry/2024/09/13/002646 1.0 100%