AtCoder ABC 370 C - Word Ladder (4Q, 灰色, 300 点)

操作回数を最小化せよ、という問題だけど、実際には「複数ある場合は辞書順最小のものを求めよ」という部分に本質がある問題！

• 問題へのリンク

問題概要

文字列 は文字数が等しい。 に対して「1 文字変更する」という操作を繰り返すことで にしたい。

そのうちの最小回数のものを求めよ（最小回数を とする）。

複数通りあるときは、 回目の操作後の文字列 をこの順に concat してできる文字列が辞書順最小であるものを求めよ。

制約

• 

考えたこと

最小回数はとてつもなく簡単に求められることに注意しよう！！（意外と忘れがちなのだ）

それは、 であるような の個数である。 のハミング距離などとも呼ばれている値である。

さて、 を 回で にする方法というのは、次のように特徴づけられる。

---

その時点における について、 と文字が異なる添字 を好きなように選んで と に置き換える

---

さて、concat してできる文字列が辞書順最小であるためには、実は単純に、次のような Greedy 解法を考えれば良い（これは操作後の の長さが毎回等しいことから言える）。

• 1 回目の操作後の文字列 のうち、辞書順最小のものを新たな とする
• 2 回目の操作後の文字列 のうち、辞書順最小のものを新たな とする
• ...
• 回目の操作後の文字列 のうち、辞書順最小のものを新たな とする

この処理は、愚直に の計算量で実装できる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    string S, T;
    cin >> S >> T;

    // 文字列 S を文字列 T に向かって一文字変更してできる文字列のうち、辞書順最小のもの
    auto solve = [&]() -> string {
        string res = "";
        for (int i = 0; i < S.size(); i++) {
            if (S[i] != T[i]) {
                char c = S[i];
                S[i] = T[i];
                if (res == "") res = S;
                else res = min(res, S);
                S[i] = c;  // 元に戻しておく
            }
        }
        return res;
    };

    vector<string> res;
    while (S != T) {
        S = solve();
        res.push_back(S);
    }
    cout << res.size() << endl;
    for (auto str : res) cout << str << endl;
}