コンテンツへスキップ

【Ruby基礎】AtCoder Beginner Contest 021 B – 嘘つきの高橋くん

  • by

INDEX

■はじめに

Rubyの基礎的な問題をたくさん解くことで基本的な考え方やメソッドの使い方を定着させたい。
基本的にはAtCoderというプログラミングコンテスト（競技プログラミング）の過去問を使う。（AtCoderは難易度が分かれており、難易度の低いA問題かB問題を解いていく）

（5/23時点の方針）
メソッドの切り分け方や値の受け渡しを練習するために、コード長の短さについては気にせずに書くことにする。

（2022/10/17時点の方針）
しばらくはB問題を小さい番号の方からやっていく。たまにA問題もやるかも。

■問題

●出典

AtCoder Beginner Contest 021のB問題
https://atcoder.jp/contests/abc021/tasks/abc021_b

●問題文

あなたと高橋君は、AtCoder 王国に住んでいます。AtCoder 王国には、N 個の町と、町同士を結ぶ何本かの道路が存在し、道路は双方向に移動可能です。 N 個の町はそれぞれ 町 1,町 2,…,町 N と呼ばれています。

高橋君はあなたの家に遊びに行くことにしました。そして、高橋君は町 a から出発して、ちょうど K 回 AtCoder 王国のどこかの町を経由して町 b にあるあなたの家に到着しました。

高橋君は町 a から町 b まで最短経路で移動してきたと主張していますが、あなたには彼が嘘をついているよう思えます。 しかし、あなたは具体的に町同士を結ぶ道路がどのような構成になっているか全く知らないため、高橋君が辿った経路が本当に最短経路なのかどうか判定できません。

あなたは高橋君がどの順番で町を経由したかを聞き出すことに成功しました。ただし、この情報には出発/到着地点である町 a と町 b が含まれません。

あなたはこの情報を元に、高橋君が最短経路で移動していた可能性があるかどうかを出力するプログラムを書くことにしました。 町 a から町 b への最短経路とは、町 a から町 b への移動経路において道路を通る回数が最小となるような経路のことを言います。

高橋君が辿った経路が最短経路となるような町と道路の構成が 1 つでも存在する場合、最短経路で移動した可能性があると言えます。一方、そのような構成がない場合、その可能性は無いと言えます。

●入力

入力は以下の形式で標準入力から与えられる。

N
a b
K
P1 P2 … PK
  • 1 行目には、AtCoder 王国に存在する町の個数を表す整数 N(2≦N≦100) が与えられる。
  • 2 行目には、高橋君が出発する町とあなたの家がある町の番号を表す 2 つの整数 a,b(1≦a,b≦N,a≠b) が空白区切りで与えられる。
  • 3 行目には、高橋君の移動において経由した町の個数を表す整数 K(1≦K≦100) が与えられる。
  • 4 行目には、高橋君の移動において経由した町の番号が順番に空白区切りで与えられる。そのうち i(1≦i≦K) 番目の整数は、町 a を出発した後 i 番目に経由した町の番号 Pi
    (1≦Pi ≦N) を表す。
  • {Pi } の隣接する要素は全て異なる。つまり全ての j(2≦j≦K)について、Pj≠Pj−1 が成り立つ。さらに、P1≠a かつ PK≠b が成り立つ。

●出力

1 行目に、高橋君が最短経路で移動していた可能性があるならば YES、その可能性がないならば NO と出力せよ。
末尾の改行を忘れないこと。

■回答

●愚直に書く

問題文がややこしいけど汗、条件を整理すればそこまでややこしくない、はず？

  • 出発点となる1つの数値a
  • 到着点となる1つの数値b
  • 経由するいくつかの数値P1、P2、...Pk

上記があって、
Pxの中に重複するものがあったら同じ町を2回経由してしまうことになるのでNOだし、Pxにaかbが含まれていたら出発点or到着点を途中でも経由してしまうことになるのでNO。そうでなければYES、という感じかな…？

まずは標準入力をちゃんと取らないといけない。

n = gets.to_i
a, b = gets.split.map(&:to_i)
k = gets.to_i
p = gets.split.map(&:to_i)

p n
p a
p b
p k
p p

これで5種類の標準入力を分けて取得できた。aとbは、1行だから1つの配列に入れるのではなくて、別々で取得しておいた。
次に上述した条件を反映していく。

n = gets.to_i
a, b = gets.split.map(&:to_i)
k = gets.to_i
p = gets.split.map(&:to_i)

if p != p.uniq
  puts "NO"
elsif p.include?(a) || p.include?(b)
  puts "NO"
else
  puts "YES"
end

通った！問題がややこしかったので、まず通ったのが嬉しい。
もうちょっとスマートな感じにしたいけど、ここまで来るのに時間がかかったので今回は割愛。

●メソッド化して書く

メソッドを作る練習のために、あえてそういう書き方をする。

def main
  n = read_nums_all_towns
  a, b = read_start_goal
  k = read_nums_via_towns
  p = read_via_towns
  puts true_or_false?(p, a, b)
end

def true_or_false?(p, a, b)
  if p != p.uniq
    "NO"
  elsif p.include?(a) || p.include?(b)
    "NO"
  else
    "YES"
  end
end

def read_nums_all_towns
  gets.to_i
end

def read_start_goal
  gets.split.map(&:to_i)
end

def read_nums_via_towns
  gets.to_i
end

def read_via_towns
  gets.split.map(&:to_i)
end

main

通った！

●リファクタリング／別アプローチ

今回は割愛。

●他の方の回答例

上位層の回答は今回も短くてすごい…！
順番に見ていって、自分の回答を改善できる点がわかった。
僕の解答だとuniqとinclude?を分けてやっているのが冗長で、aをbをxに追加して全体としてuniqになっているかを確認すれば良い。

修正したものが下記。

n = gets.to_i
ab = gets.split.map(&:to_i)
k = gets.to_i
p = gets.split.map(&:to_i)
x = p + ab
puts x != x.uniq ? "NO" : "YES"

さらにリファクタリング。
nとkは使わないのでto_iは削除して、あとは条件の方で!=ならNOと書くよりも==ならYESと書いた方が意味的に綺麗な気がするので修正。

n = gets
ab = gets.split.map(&:to_i)
k = gets
p = gets.split.map(&:to_i)
x = p + ab
puts x == x.uniq ? "YES" : "NO"

通った！
もっと言うと変数abは何かアルファベット1文字にしても良いんだけど、a地点とb地点があるのでこのままにしておいた方が意味的にはわかりやすいかなと思った。

●出てきたメソッド等

公式リファレンスを見る訓練。

■振り返りなど

考え方としては合っていたけど、よりシンプルに削ぎ落とす部分がまだ余地があった。