AtCoder が提供しているABC(AtCoder Beginner Contest)373 B問題をC++とPythonで解いてみました。ABC373は、2024年9月28日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 1D Keyboard(Difficulty : 54)
問題の詳細は、リンク先をご覧ください。
それぞれの文字の場所を調べて、シミュレーションします。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 の問題を紹介していきます。