実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 228

問題概要

英子文字からなる長さの等しい2つの文字列 $S, T$ が与えられる。 $X$ を空の配列として、以下の操作を $S, T$ が等しくなるまで繰り返す。

$S$ の文字を1文字書き換え、 $X$ の末尾に $S$ を追加する。

こうして得られる文字列の配列 $X$ のうち、要素数最小かつ辞書順最小のものを求めよ。

制約

$S, T$ の長さは $1$ 以上 $100$ 以下。

考察

問題の意味がいまいちつかみにくいので、サンプルケース1 ( $S =$ adbe, $T =$ bcbc) でいろいろ試してみる。以下では、 $S, T$ の長さを $l$ とする。

要素数最小ということは文字の入れ替え回数が最小ということなので、「 $i = 1, 2, \cdots, l$ に対して、 [tex :S_i \neq T_i] ならば操作を行う」という方針が基本となる。

ただし、単純にこの方針をとると

$X = ($ bdbe, bcbe, bcbc $)$

のようになり、この $X$ は辞書順最小でない。

ここで、1回の操作で置き換える文字によって $S$ がどのように変わるかを考えてみる。

adbeの1文字目をaからbに置き換える : bdbeは元の文字列より辞書順が後ろになる。
adbeの2文字目をdからcに置き換える : acbeは元の文字列より辞書順が前になる。

つまり、辞書順最小を目指すためには「 $S_i \gt T_i$ のときに置き換えを実行し、そうでないときは行わない」という方針で $i = 1, 2, \cdots, l$ とした後に「 $S_i \lt T_i$ のときに置き換えを実行し、そうでないときは行わない」という方針で $i = l, l-1, \cdots, 1$ とすればよいことになる。

計算量は $O(l^2)$ で、今回の制約下では高速に動作する。

コードではdiffという配列に $S_i$ と $T_i$ の辞書順での差を格納しており、値が正なら $S_i$ の方が辞書順後ろ、負ならば辞書順前ということを表している。

コード

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

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
#define rrep(i, start, end) for (auto i = (start); (i) >= (end); (i)--)

// ======================================== //

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

    int l = S.size();
    vector<int> diff(l, 0);
    rep(i, 0, l) diff[i] = S[i] - T[i];

    vector<bool> changed(l, false);
    vector<string> X;
    rep(i, 0, l) {
        if (!changed[i] && diff[i] > 0) {
            S[i] = T[i];
            X.push_back(S);
            changed[i] = true;

            continue;
        }
    }
    rrep(i, l - 1, 0) {
        if (!changed[i] && diff[i] < 0) {
            S[i] = T[i];
            X.push_back(S);
            changed[i] = true;

            continue;
        }
    }

    cout << X.size() << endl;
    for (auto x : X) cout << x << endl;
}