Official

B - ABCDEFG Editorial by Nyaan


この問題は簡潔な実装方法を見つけられるかが重要になる問題です。実装に苦労した人は次回以降素早く実装できるように勉強してみるとよいでしょう。

解法はいくつかありますが、推奨しない解法の 1 つとして、答えを全部埋め込んでしまうという方法があります。入力としてあり得る \(p, q\) の組は \(7 \times 6 = 42\) 通りです。そして、それぞれの組に対する答えは手元で足し算を行えば答えを求められます。

# Python による(推奨されないアルゴリズムの)実装例
p, q = input().split()
if p == 'A' and q == 'B':
  print(3)
elif p == 'A' and q == 'C':
  print(4)
# 以下省略 (残りの 40 通りも列挙すると AC できる)

しかし、この方針はとにかく面倒なので、どうにか楽をできないか考えてみましょう。

簡単のため、頂点をアルファベットではなく 0 始まりの番号で呼ぶことにします。つまり、点 \(A, B, C, D, E, F, G\) を点 \(0, 1, 2, 3, 4, 5, 6\) に置き換えます。(この置き換えは 文字を ASCII コードに置き換える操作によって容易に実現できます。たとえば C++ では (pchar 型として) p - 'A' 、Python では (pstr 型として) ord(p[0]) - ord('A') のように書けばよいです。) そして、\(n=0,1,2,3,4,5\) について、点 \(n\) と点 \(n+1\) の間の辺を 辺 \(n\) と呼ぶことにします。(例えば辺 \(0\) は点 \(0\) と点 \(1\) を結ぶ長さ \(3\) の辺です。)

このように言い換えた上で解法を説明します。 まず、\(p \gt q\) の場合は 「点 \(p\) と点 \(q\) の距離」と「点 \(q\) と点 \(p\) の距離」は等しいので \(p\)\(q\) を swap しても問題ないです。よってこのような場合は \(p\)\(q\) を swap することで、\(p \lt q\) の場合のみを考えればよいことになります。 そして、\(p \lt q\) の場合、点 \(p\) と点 \(q\) の間にある辺は「番号が \(p\) 以上 \(q\) 未満の辺」であることが、辺の番号の定義からわかります。よって、条件を満たす範囲の辺の長さを for-loop 等を用いて足し合わせれば答えを得られます。

  • 実装例(C++)
#include <iostream>
using namespace std;

int main() {
  char p, q;
  cin >> p >> q;
  p -= 'A', q -= 'A';
  if(p > q) swap(p, q);
  int e[] = {3, 1, 4, 1, 5, 9}, ans = 0;
  for (int i = p; i < q; i++) ans += e[i];
  cout << ans << "\n";
}

別解として、\(A\) から \(G\) を何らかの座標に対応させる解法があります。
簡単に方針を説明します。\(A\) を数直線上の \(x=0\) の地点とみなして、\(B\) から \(G\) までの座標を計算すると順に \(x=3, 4, 8, 9, 14, 23\) になります。このとき地点間の距離は座標の差の絶対値になるので abs 関数を利用して計算できます。

  • 実装例 (C++)
#include <iostream>
using namespace std;

int main() {
  char p, q;
  cin >> p >> q;
  int e[] = {0, 3, 4, 8, 9, 14, 23};
  cout << abs(e[p - 'A'] - e[q - 'A']) << endl;
}

posted:
last update: