Created by
cia_rana
last modified
| Accepted
こんにちは、Ozy(@ozy4dm)です。
『ぎゅうぎゅうシーケンス』に挑戦していただきありがとうございます。
そして、正解おめでとうございます!!
この問題は、2月27日発売の『世界で闘うプログラミング力を鍛える本 コーディング面接189問とその解法』
の中で解説されている問題を少し簡略化したものです。いかがでしたか?
ラクラク解けてしまった方にとっては少し物足りないかもしれませんが、
本書にはさまざまな解法や具体的な例が書かれていますので、是非一度手に取ってみてください。
ちなみに、私の解答コード(Ruby)は次のようなものでした。
# ruby
n = gets.to_i
v = gets.split.map(&:to_i)
def solve(n, v)
e = [1, 2, 3]
# eが出現するインデックスのリスト
q = Array.new(e.size).map{Array.new}
v.each_with_index{|vk, i|
# eの各要素が出現するインデックスを抽出
e.each_with_index{|ek, j| q[j] << i if vk==ek }
}
m = Float::INFINITY # 最小値をmとする
loop{
# どれかが空になったら終わり
q.each{|r| return m if r.empty? }
t = q.map{|r|r[0]} # qの先頭要素のリスト
m = [m, t.max - t.min + 1].min # max-min+1が区間サイズ
q[t.index(t.min)].shift # 最小のインデックスは削除
}
end
puts solve(n, v)
|
| gets
gets
l=m=1.0/i=0
while l
m=[l,m].min
i,l=[*1..3].permutation.map{|q|
(j=" #{$_.chop} ".index(/ #{q*"( | .*? )"} /,i))?[j+1,$&.split.size]:[1e9]}.min
end
p m
|
| n=gets.to_i
gets
p [*0...n].combination(2).map{|i,j|(%w(1 2 3)-$_.split[i..j]).size<1? j-i+1:n}.min
|
| goalNums = 1..3
n = gets.to_i
seq = gets.split.map(&:to_i)
goalNumIndices = {}
goalIntervalNums = []
goalIntervalIndicesMin = []
seq.each_with_index{|num, i|
if goalNums.include?(num)
goalNumIndices[num] = (goalNumIndices[num] || []) << i
unless goalIntervalNums.include?(num)
goalIntervalNums << num
goalIntervalIndicesMin << i
end
end
}
intervalDistance = ->(min, max){max - min + 1}
goalNumItervalMin = intervalDistance[*goalIntervalIndicesMin.minmax]
loop do
intervalIndexMin = goalIntervalIndicesMin.shift
intervalNum = goalIntervalNums.shift
goalNumIndices[intervalNum].shift
index = goalNumIndices[intervalNum][0]
break if index.nil?
goalIntervalNums.insert(goalIntervalIndicesMin.push(index).sort!.index(index), intervalNum)
goalNumItervalMin = [goalNumItervalMin, intervalDistance[*goalIntervalIndicesMin.minmax]].min
end
p goalNumItervalMin
|