AtCoder ABC 264 D - "redocta".swap(i,i+1) (茶色, 400 点)

とてもいい感じの BFS の練習問題！

• 問題へのリンク

問題概要

"atcoder" の並び替えである文字列 が与えられます。

文字列 に対して「隣接する 2 要素を swap する」という操作を繰り返すことで、"atcoder" となるようにしたいとします。

最小何回の操作で実現できるかを求めてください。

制約

• は "atcoder" の並び替えによって得られる文字列

解法

この問題がグラフの問題になると言ったら驚く人もいるかもしれないですね。しかし、一見グラフの問題に見えなくても、グラフを用いて考察することが有効な場面はたくさんあります。

今回も、

• 頂点："atcoder" を並び替えて得られる文字列
• 辺：1 回の操作

に対応させたグラフを考えてみましょう。

このグラフ上で、与えられた文字列 を始点とした BFS をすることで、「各文字列が最小で何回の操作で得られるか」が求められます。文字列 "atcoder" までの距離を答えることで正解となります。

最後に計算時間を見積もってみましょう。"atcoder" を並び替えて得られる文字列の個数は 個ですので、グラフのサイズはそれほど大きくないと言えます。実行制限時間が 2 秒であれば、十分間に合います。

コード

BFS のやり方については、次の記事に詳しく書いたので、参考にしてもらえたらと思います。

qiita.com

#include <bits/stdc++.h>
using namespace std;
const string atcoder = "atcoder";

int main() {
    string S;
    cin >> S;
    
    // BFS のためのデータ構造
    queue<string> que;
    map<string, int> dist;
    
    // 初期条件
    que.push(S);
    dist[S] = 0;
    
    // BFS
    while (!que.empty()) {
        string v = que.front();
        que.pop();
        
        for (int i = 0; i+1 < atcoder.size(); ++i) {
            string v2 = v;
            swap(v2[i], v2[i+1]);
            if (!dist.count(v2)) {
                que.push(v2);
                dist[v2] = dist[v] + 1;
            }
        }
    }
    cout << dist[atcoder] << endl;
}