AtCoder ABC 373 B - 1D Keyboard (6Q, 灰色, 200 点)

各文字がどこにあるのかを求めると楽になる。

• 問題へのリンク

問題概要

'A' から 'Z' までの文字を 1 つずつ含む文字列 が与えられる。 内部での

• 'A' から 'B' への移動距離 (index の差分)
• 'B' から 'C' への移動距離 (index の差分)
• 'C' から 'D' への移動距離 (index の差分)
• ...
• 'Y' から 'Z' への移動距離 (index の差分)

の総和を求めよ。

考えたこと

最初に、文字列 の中で各文字がどこにあるかを求めよう。つまり、次の配列 pl を求めよう。

---

pl[c]：文字 がどこにあるか。つまり、 となる

---

これを求めたあとは、abs(pl[i+1] - pl[i]) の総和を求めていけばよい。

コード

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

int main() {
    int res = 0;
    string S;
    cin >> S;
    vector<int> pl(26);
    for (int i = 0; i < S.size(); i++) {
        pl[S[i] - 'A'] = i;
    }
    for (int i = 0; i+1 < 26; i++) {
        res += abs(pl[i+1] - pl[i]);
    }
    cout << res << endl;
}