yutasの競技プログラミング勉強帖

競技プログラミングの問題についての解説記事を主に書いています。

B - Pentagon / トヨタ自動車プログラミングコンテスト2023#8 (AtCoder Beginner Contest 333)

ABC333 AtCoder C++ AtCoder Beginner Contest 200点 幾何問題 競技プログラミング

問題

頂点が時計回りに順に \mathrm{A, B, C, D, E} である正五角形 P がある。

P の2頂点 {S}_{1}, {S}_{2} を結ぶ線分と、2頂点 {T}_{1}, {T}_{2} を結ぶ線分の長さが等しいか判定せよ。

入力

まず最初の1行に、2文字の文字列 {S}_{1}{S}_{2} が与えられる。

そして次の1行に、2文字の文字列 {T}_{1}{T}_{2} が与えられる。

条件

  • 実行時間制限: 2s
  • メモリ制限: 1024MB
  • {S}_{1}, {S}_{2}, {T}_{1}, {T}_{2} は A, B, C, D, E のいずれかの文字
  • {S}_{1} \ne {S}_{2}
  • {T}_{1} \ne {T}_{2}

出力

線分の長さが等しいときは Yes を、等しくないときは No を出力すること。

解法

\mathrm{dist} ({S}_{1}, {S}_{2}) を、点 {S}_{1} から点 {S}_{2} までをつなぐ辺の本数の最小値として定めます。 （ T についても同様です。）

各頂点はアルファベット順に並んでいるため、与えられた2文字がアルファベット順でどれだけ離れているかを考えることで、それぞれまでに辿り着く辺の本数を求めることができます。

ただし、「アルファベット順でどれだけ離れているか」は時計回りで頂点を見たときの辺の本数であるため、最小値にならないときがあります。 「アルファベット順でどれだけ離れているか」を表す整数を \mathrm{diff} とおくと、正五角形について考えているため、 \begin{align} \mathrm{dist} = \min (\mathrm{diff}, 5 - \mathrm{diff}) \end{align} によって \mathrm{dist} が与えられます。

この問題では正多角形について考えているため、 \mathrm{dist} ({S}_{1}, {S}_{2}) = \mathrm{dist} ({T}_{1}, {T}_{2}) が成立すれば、2つの線分の長さが等しいと判定できます。 逆に、これが成立しないときは、2つの線分の長さは等しくありません。

ソースコード

main() 関数の中に直接答えを出力する部分を実装しました。

int main() {
  // 文字列の入力
  string s, t;
  cin >> s;
  cin >> t;

  // diff は abs(s[0] - s[1]) で求めることができる
  int dist_s = min(abs(s[0] - s[1]), 5 - abs(s[0] - s[1])); 
  int dist_t = min(abs(t[0] - t[1]), 5 - abs(t[0] - t[1]));

  // 答えの出力
  if (dist_s == dist_t) {
    Yes();
  } else {
    No();
  }

  return 0;
}