文字列を印刷するために必要なダイヤルの回転数を求めるC++コード

すべての小文字の英字アルファベットが刻まれた回転式ダイヤルがあるとします。ダイヤルにはプリンターが取り付けられており、ポインタのある位置の文字が3秒間留まると、その文字が出力（印刷）されます。ダイヤルは初期状態では「a」を指しており、文字を出力した後も初期位置に戻ることはありません。

ここで、文字列 s が与えられるので、この文字列を出力する必要があります。ダイヤルを別の文字へ移動させるたびに、1回分の回転が発生します。与えられた文字列 s を出力するために必要な総回転数を求めてください。

例えば、入力が s = "elephant" の場合、出力は 63 となります。

解法のアプローチ

この問題を解くには、以下の手順に従います。

• 現在のポインタ位置を表す変数 t を「a」で初期化します。
• 答えを格納する変数 res を 0 で初期化します。
• 文字列の各文字について、前の文字から現在の文字への移動に必要な最小回転数を計算して加算します。ダイヤルは円環状になっているため、順方向と逆方向のうち短い方を選びます（min(|t - s[i]|, 26 - |t - s[i]|)）。
• 現在の文字を次の基準位置として更新します。
• すべての文字を処理し終えたら、res を返します。

t := 'a'
res := 0
for initialize i := 0, when i < size of s, update (increase i by 1),
do:
    res := res + minimum of (|t - s[i]|, 26 - |t - s[i]|)
    t := s[i]
return res

C++での実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
#define N 100
int solve(string s) {
    char t = 'a';
    int res = 0;
    for(int i = 0; i < s.size(); i++){
        res += min(abs(t - s[i]), 26 - abs(t - s[i]));
        t = s[i];
    }
    return res;
}
int main() {
    string s = "elephant";
    cout<< solve(s);
    return 0;
}

入力

"elephant"

出力

63

計算の内訳

"elephant" の場合、各文字間の移動に必要な回転数は以下の通りです。

合計：4 + 7 + 7 + 11 + 8 + 7 + 13 + 6 = 63 回転となり、プログラムの出力と一致します。