C++で2本の指を使って単語を入力するための最小距離

以下のようなキーボードレイアウトがあるとします。

各大文字アルファベットは座標に配置されています。例えば、Aは(0,0)、Bは(0,1)、Pは(2,3)、Zは(4,1)にあります。与えられた単語を2本の指のみで入力する際の最小総移動距離を求めます。2地点(x1,y1)と(x2,y2)間の距離はマンハッタン距離 |x1-x2| + |y1-y2| で定義され、開始位置はキーボード上の任意の場所から始められます。

問題の例

入力が "HAPPY" の場合、出力は6となります。

• Hから開始（コスト0）
• Aへ移動：H(1,1)→A(0,0) でコスト2
• Pへ移動：もう片方の指でP(2,3)を押す（コスト0）
• 再びP：同じ指で押す（コスト0）
• Yへ移動：P(2,3)→Y(4,1) でコスト4

総コスト = 2 + 4 = 6

解法アプローチ

メモ化再帰（動的計画法）を用いて解きます。状態は「指1の位置、指2の位置、現在処理中の文字インデックス」で定義されます。

主要な関数

• getXY(char c): 文字から座標(row, col)を取得。'A'からのオフセットを6で割った商と余りで計算。
• getDist(x1,y1,x2,y2): 2点間のマンハッタン距離。未配置(-1,-1)の場合は距離0。
• solve(x1,y1,x2,y2,word,idx): 再帰関数。現在の文字を指1または指2のどちらで打つか最小コストを探索し、メモ化する。
• getHash(...): 状態を一意の整数キーに変換（メモ化用）。

C++実装例

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

class Solution {
    map<int, int> memo;
    
    int getHash(int a, int b, int c, int d, int e) {
        int temp = 0;
        while (a) { temp = temp * 10 + a % 10; a /= 10; }
        while (b) { temp = temp * 10 + b % 10; b /= 10; }
        while (c) { temp = temp * 10 + c % 10; c /= 10; }
        while (d) { temp = temp * 10 + d % 10; d /= 10; }
        while (e) { temp = temp * 10 + e % 10; e /= 10; }
        return temp;
    }
    
    pair<int, int> getXY(char c) {
        int a = c - 'A';
        return {a / 6, a % 6};
    }
    
    int getDist(int x1, int y1, int x2, int y2) {
        if (x1 == -1 && y1 == -1) return 0;
        return abs(x1 - x2) + abs(y1 - y2);
    }
    
    int solve(int x1, int y1, int x2, int y2, string &word, int idx) {
        if (idx == word.size()) return 0;
        
        int state = getHash(x1 + 2, y1 + 2, x2 + 2, y2 + 2, idx + 2);
        if (memo.count(state)) return memo[state];
        
        auto [nx, ny] = getXY(word[idx]);
        
        int cost1 = getDist(x1, y1, nx, ny) + solve(nx, ny, x2, y2, word, idx + 1);
        int cost2 = getDist(x2, y2, nx, ny) + solve(x1, y1, nx, ny, word, idx + 1);
        
        return memo[state] = min(cost1, cost2);
    }
    
public:
    int minimumDistance(string word) {
        memo.clear();
        return solve(-1, -1, -1, -1, word, 0);
    }
};

int main() {
    Solution ob;
    cout << ob.minimumDistance("HELLO") << endl; // 出力: 4
    return 0;
}

実行結果

計算量

• 時間計算量: O(N × 26²) ≈ O(N) — Nは単語の長さ。状態数は文字位置の組み合わせ(26×26)とインデックス(N)の積。
• 空間計算量: O(N × 26²) — メモ化テーブルのサイズ。