ABC373 B問題（1D Keyboard）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）373 B問題をC++とPythonで解いてみました。ABC373は、2024年9月28日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

B問題 1D Keyboard（Difficulty : 54）

問題の詳細は、リンク先をご覧ください。

ABC373 B問題 1D Keyboard

それぞれの文字の場所を調べて、シミュレーションします。AtCoder Problems による Difficulty は 54 でした。

解答案

文字 ‘A’ の位置を $P_A$ とします。指の動きをシミュレートすると、求める値は以下となります。

$$| P_A -P_B | + | P_B -P_C | + \cdots + | P_Y -P_Z | $$

C++ プログラム例（ABC373B）

文字 A から Z の位置を求めて配列 pos に格納します。次に考察した式の値を計算します。

以下が、C++プログラムです。

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

int main()
{
	string s;
	cin >> s;
	vector<int> pos(26);
	for (int i = 0; i < 26; ++i) {
		pos[s[i] - 'A'] = i;
	}

	int result = 0;
	for (int i = 0; i < 25; ++i) {
		result += abs(pos[i + 1] - pos[i]);
	}

	cout << result << endl;

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

Python プログラム例（ABC373B）

Python版も基本的な考え方は同じです。組込み関数 ord で文字コードを求めることができます。以下がプログラムです。

"""AtCoder Beginner Contest 373 B"""
s = input()
pos = [0] * 26
for i in range(26):
    pos[ord(s[i]) - ord('A')] = i

result = 0
for i in range(25):
    result += abs(pos[i + 1] - pos[i])

print(result)

こちらも「AC」と判定されました。

最後に

一次元キーボードの指の動きをシミュレーションして結果を求めることができました。

引き続き ABC の問題を紹介していきます。