TechFUL 難易度7「最良のキャッチコピー」

TechFULの難易度7「最良のキャッチコピー」を解いた。
問題は下記のURL

問題概要

整数$N,Q$、文字列$S$が与えられる。
文字列$S$の長さは$N$である。
以下に示す$Q$回の操作によって$Q$個の新たな文字列$S1,S2,…,SQ$を生成することにしました。

• $ i (1≤i≤Q) $回目の操作では、$Si−1$の左から$Xi$文字目と左から$Yi$文字目を入れ替えた文字列を$Si$として生成する($Si−1$には変更は加えない)。

ここで、最良のキャッチコピーを$S0,S1,S2,…,SQ$のうちで辞書順最小の文字列と定義したとき
最良のキャッチコピーである最小の整数$k$を求めてください。

（詳しい問題文・制約は上記のURLに。）

解説

ここで、入れ替える⇒swapとして記載します。

Queryによって、$S[X]$と$S[Y]$をswapした文字列を$S2$とする。
最終的に欲しいものは作成される$S2$全種類ででの辞書順最小である文字列。
よって

• 入れ替える毎に元の文字列$S$と$S2$を比較する。
• $S > S2$なら、$S$を$S2$に更新し、その時点での添え字を保存しておく。

swapした結果$S = S2$となる場合の時は更新しないことに注意。（求めるものが最小の添え字。）

C++による実装例

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

int main(){
    int N, Q; cin >> N >> Q;
    string S; cin >> S;
    string S2 = S;
    int ans = 0;

    for(int i = 1; i <= Q; i++){
        int X, Y; cin >> X >> Y;
        X--; Y--;
        swap(S2[X], S2[Y]);
        if(S > S2){
            S = S2;
            ans = i;
        }
    }
    cout << ans << endl;
}

感想

• 文章って書くの難しい。
• 公式解説ではsetで管理していました。