SRM 560, Divison 2, Level 1 : TypingDistance

概要

横一列にレイアウトされたキーボードがある。
キーボードのレイアウトと、タイプする文字列が与えられる。
最初の文字をタイプしてから最後の文字をタイプするまでの指の移動距離の最小値を求
めよ。

本番中の思考

• タイプする文字列中で隣接する文字の距離の差（の絶対値）だけあればいいよね
  • 毎回ループ回して調べるの面倒だから先に map に入れとこう
• abs() って返却値の型 int だっけ？
  • max から min 引けばいいや

本番で書いたコード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

class TypingDistance
{
public:
	int minDistance(string keyboard, string word)
	{
		const int N = keyboard.size(), L = word.size();

		map< char, int > pos;

		REP( i, 0, N )
		{
			pos[ keyboard[i] ] = i;
		}

		int res = 0;

		REP( i, 0, L - 1 )
		{
			int a = pos[ word[i] ], b = pos[ word[ i + 1 ] ];

			res += max( a, b ) - min( a, b );
		}

		return res;
	}
};

本番での得点

244.70 pts