コンテンツへスキップ

【Ruby基礎】AtCoder Beginner Contest 024 B – 自動ドア

■はじめに

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

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

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

■問題

●出典

AtCoder Beginner Contest 024のB問題
https://atcoder.jp/contests/abc024/tasks/abc024_b

●問題文

ABCマーケットは高橋王国で最も人気なスーパーマーケットです。 入り口は自動ドアになっています。

この自動ドアは人が前を通りかかると自動で開き、そこから T 秒後まで開き続け、その後自動的に閉じます。 ドアが開いている状態で新たに人が前を通りかかると、通りかかった時刻のさらに T 秒後まで開き続ける時間が延長されます。

今日はのべ N 人の客が自動ドアの前を通りかかりました。 i 番目の人が通りかかった時刻はABCマーケットが開店してから Ai 秒経った時刻です。

今日、この自動ドアが開いていた合計秒数を求めてください。

●入力

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

N T
A1
A2
:
AN
  • 1 行目に今日自動ドアの前を通りかかった人数を表す整数 N(1≦N≦10^5) とドアが開き続ける時間を表す整数 T(1≦T≦10^5) が空白区切りで与えられる。
  • 2 行目からの N 行のうち i 行目には i 番目の客が自動ドアの前を通りかかった時刻 Ai (1≦Ai ≦10^6 ) が与えられる。
  • A1 ≦ A2 ≦…≦ AN が成り立つ。

●部分点

この問題には部分点が設定されている。

  • 1≦T≦100を満たすデータセットに正解した場合は 50 点が与えられる。
  • 1≦T≦10^5 を満たすデータセットに正解した場合はさらに 50 点が与えられる。合計で100点となる。

●出力

ドアが開いていた秒数を 1 行に出力せよ。 出力の末尾に改行を入れること。

■回答

●愚直に書く

まずは標準入力をちゃんと取る。
次に、最終的な計算を考える。もしも、全く重複することなく人が通りかかったとしたら、シンプルに「人数×秒数」が答えになる。正し実際には重複がある(ドアが開いている状態で新たに人が通る)ケースがあるので、その計算が必要。
aさんが通りかかった時刻から、その前に通りかかったbさんの時刻を引いて、それがtより小さい場合に重複が発生していることになる。
この考え方を表すコードは…。

n, t = gets.split.map(&:to_i)
a = n.times.map {|a| a = gets.to_i}

diffs = (1...n).map do |x|
  diff = (a[x] - a[x-1])
  t - diff if diff < t
end

puts n * t - diffs.compact.sum

通った!
mapで回した際に重複しない要素はnilになるので、.compactnilを消しておくのがポイント。

ひとまずは正解に辿り着けた…。もっとスマートな書き方があるような気もするが、今回はここで他の回答を見させていただくことにする。

●他の方の回答例

B問題になってくると、最上位層の回答がわからなすぎて参る…。
色々と見て、良いなと思った回答があったので自分なりに少しアレンジして書いてみる。

n, t = gets.split.map(&:to_i)
a = n.times.map {|a| a = gets.to_i}

ans = t
(n - 1).times do |i|
  ans += [t, a[i + 1] - a[i]].min
end

puts ans

まず変数anstを入れておく。
つまり初めの1回分はもうtが入っているので、次に繰り返すのはn-1回になる。その中身としては、
ta[i + 1] - a[i]、つまりaさんが通りかかった時刻から、その前に通りかかったbさんの時刻を引いた数字、これをminすることで、どちらか小さい方だけをans+=で足し上げていくことになる。
なるほど!!!

●出てきたメソッド等

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

■振り返りなど

minmaxをこうやってサラッと使えるようになりたい。