公式

B - 1D Keyboard 解説 by MtSaka


文字 \(c\) に対して、\(c\) に対応するキーが配置されている座標を \(X_c\) とします。

この時、求めるべき値は\(|X_A-X_B|+|X_B-X_C|+\ldots+|X_Y-X_Z|\) です。

実際に \(S\) から \(X\) を求めることができれば、for文を用いて求めるべき値を計算できます。

一般的なプログラミング言語では配列は非負整数を用いて要素を指定し、文字では要素を指定できません。 この問題の実装の際は、\(A\) に対応する数を \(0\)\(B\) に対応する数を\(1\)\(\ldots\) \(Z\) に対応する数を \(25\) とすることで先ほど示した \(X\) を配列として管理することができます。 他にも、文字型をキーとした連想配列などを用いることもできます。

実装例(C++):

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

int main() {
    string s;
    cin >> s;
    vector<int> x(26);
    for (int i = 0; i < 26; ++i)
        x[s[i] - 'A'] = i;
    int ans = 0;
    for (int i = 0; i < 25; ++i)
        ans += abs(x[i] - x[i + 1]);
    cout << ans << endl;
}

実装例(Python3):

s = input()
x = [0] * 26
for i in range(26):
    x[ord(s[i]) - ord("A")] = i
ans = 0
for i in range(25):
    ans += abs(x[i] - x[i + 1])
print(ans)

投稿日時:
最終更新: