はじめに
AtCoder過去問D問題をRubyで解いてみました。
よろしくお願いします。
問題はこちらから確認してください↓
D - Brick Break
まずは入力を受け取ります。
後に、繰り返し文を使用して答えを出力させるので変数cntを用意して0を代入しておきます。
n = gets.to_i
a = gets.split.map(&:to_i)
cnt = 0
この問題の引っかかりやすいポイントとして、レンガを一つも壊す必要がなかった時と、レンガを一つも壊せずすぬけが満足しなかった場合の出力を同じにしてしまうと不正解です。
前者は0を出力させます。後者はすぬけが満足していないので-1を出力させなければなりません。
簡単に言えば、とりあえず配列aに1が存在していなかったらすぬけは絶対に満足できないので-1を出力します。逆に1があればすぬけは必ず満足するので、レンガを壊した数を出力させます。
if文で-1を出力させる記述を先に書いておきます。
n = gets.to_i
a = gets.split.map(&:to_i)
cnt = 0
if a.include?(1)
else
puts -1
end
それではif文のa.include?(1)がtrueのときの処理を書いていきます。
とりあえず書き終えたコードを見てください、解説を後述します。
n = gets.to_i
a = gets.split.map(&:to_i)
cnt = 0
if a.include?(1)
(1..n).each do |i|
if a.index(i) == nil
break
else
cnt += a.index(i)
a.shift(a.index(i)+1)
end
end
puts cnt + a.length
else
puts -1
end
解説します。
まず、ブロック変数iに1~nの数字が一つずつ入れていくeach文を作ります。
a.index(i)とすることで1から順に各々のインデックス番号を表現できます。
もし対応するインデックス番号が存在しない数字が入ったときはそのとき処理を止めます。
インデックス番号が存在しているならばelseで処理を続けます。
cntにa.index(i)を足して代入します。
例えばiが1であれば配列aの1の場所を特定します。それはa.index(i)として表現されています。
a.index(i)はiのインデックス番号を表現しているのと同時に、iにたどり着くまでのレンガの数を表しています。つまり壊したレンガの数をcntに足しているということです。
足した後は左から（配列の先頭から)iまでをshiftメソッドで消します。
そして繰り返すと言った感じです。
最後にcntとa.lengthを足したものを出力すればすぬけが壊すレンガの数が分かります。
a.lengthを足すのは最後に余った(配列aに残った)レンガも壊すこと可能なのでcntに含めてあげています。
おまけ
a.index(i)がいくつもeach文の中に出てくるので変数に代入しておくと少し処理が早くなりました。
n = gets.to_i
a = gets.split.map(&:to_i)
cnt = 0
if a.include?(1)
(1..n).each do |i|
x = a.index(i)
if x == nil
break
else
cnt += x
a.shift(x+1)
end
end
puts cnt + a.length
else
puts -1
end