ECR153-E Fast Travel Text Editor

問題

https://codeforces.com/contest/1860/problem/E (2400diff)

文字列が与えられる。

内にカーソルが一つあることを考える。カーソルは文字と文字の間にある。あなたはカーソルに対して以下の操作を行うことができる

• カーソルを左に動かす
• カーソルを右に動かす
• カーソルの左にある文字を、右にある文字をとする。を満たすを一つ選び、文字目と文字目の間にカーソルを移動する

個のクエリが与えられる。

• はじめ文字目と文字目の間にカーソルがある。文字目と文字目の間にカーソルを移動するために必要な最小の操作回数を求めよ

制約

• 
• 

解説

グラフの最短経路の問題に帰着させることを考える。

頂点集合をカーソルの位置としてあり得る点と、文字の二つ組を代表する頂点とする。頂点数は

一つ目、二つ目の操作はそのまま辺を張る。

三つ目の操作は頂点から頂点にコストを張り、頂点から頂点にコストの辺を張る。

このグラフ上で各頂点からBFSを行う。

クエリ処理を考える。からへの最短経路が既に求まっている。これは「から三つ目の操作を回以上行う」場合の最短経路である。

から三つ目の操作を回も行わない場合も求めておいた最短経路テーブルを用いて求めることができる。

で解けた。

実装

#include <bits/stdc++.h>

#include "Src/Template/IOSetting.hpp"
using namespace zawa;

int main() {
    SetFastIO();

    std::string s; std::cin >> s;
    int n{(int)s.size()};
    int N{n + 26 * 26};
    std::vector<std::vector<std::pair<int, int>>> g(N);
    std::vector<std::vector<int>> pos(26 * 26);
    for (int i{} ; i + 1 < n ; i++) {
        int f{s[i] - 'a'}, b{s[i + 1] - 'a'};
        int v{n + f * 26 + b};
        pos[f * 26 + b].push_back(i);
        g[i].emplace_back(v, 1);
        g[v].emplace_back(i, 0);
        if (i) g[i].emplace_back(i - 1, 1);
        if (i + 1 + 1 < n) g[i].emplace_back(i + 1, 1);
    }
    const int INF{(int)1e9};
    std::vector mingo(26 * 26, std::vector<int>(n, INF));
    for (int i{} ; i + 1 < n ; i++) {
        for (int j{} ; j < 26 * 26 ; j++) {
            auto it{std::lower_bound(pos[j].begin(), pos[j].end(), i)};
            if (it != pos[j].end()) {
                mingo[j][i] = std::min(mingo[j][i], *it - i);
            }
            if (it != pos[j].begin()) {
                mingo[j][i] = std::min(mingo[j][i], i - *std::prev(it));
            }
        }
    }
    std::vector dist(26 * 26, std::vector<int>(N, INF));
    for (int i{} ; i < 26 ; i++) {
        for (int j{} ; j < 26 ; j++) {
            int st{i * 26 + j};
            dist[st][n + st] = 0;
            std::deque<int> que;
            que.emplace_back(n + st);
            while (que.size()) {
                auto v{que.front()};
                que.pop_front();
                for (auto [x, w] : g[v]) if (dist[st][x] > dist[st][v] + w) {
                    dist[st][x] = dist[st][v] + w;
                    if (w) que.emplace_back(x);
                    else que.emplace_front(x);
                }
            }
        }
    }

    int q; std::cin >> q;
    while (q--) {
        int st, gl; std::cin >> st >> gl;
        if (st == gl) {
            std::cout << 0 << '\n';
            continue;
        }
        st--; gl--;
        int sp{(s[st] - 'a') * 26 + (s[st + 1] - 'a')};  
        // int gp{(s[gl] - 'a') * 26 + (s[gl + 1] - 'a')};
        int ans{dist[sp][gl] + 1};
        ans = std::min(ans, std::abs(st - gl));
        for (int i{} ; i < 26 * 26 ; i++) {
            ans = std::min(ans, mingo[i][st] + dist[i][gl] + 1);
        }
        std::cout << ans << '\n';
    }
}

感想

• 初めて赤diffを完全自力で解けた。ECR154-E(2300diff)と並列で考察していたが、こっちの方が先に解けた。
• 上で書いた計算量から更にlogをつけたが、なんか通った。助かる