今回はpaiza 線形探索メニュー セクション3【特殊な探索】前半を解説します。
セクション3【特殊な探索】は、与えられた配列データの中から、複数条件に合致する値を探し出す問題です。
前半の4問は数列から条件付きで偶数・奇数・最大値・最小値を探す問題(D〜C級)となっています。
- STEP1：要素数n個の数列aで先頭から見た時に最初に現れる奇数の位置を出力する
- STEP2：要素数n個の数列aで先頭から見た時に最後に現れる偶数の位置を出力する
- STEP3：要素数n個の数列aで整数ｋ以上の最小値を出力する
- STEP4：要素数n個の数列aで整数ｋ以下の最小値を出力する
STEP問題を解いてみる
簡単な解説は付けていますが、難しいと感じたら下記の記事も参考にしてみて下さい。
STEP1: 偶数の探索 (paizaランク D 相当)
要素数n個の数列aで、先頭から順に見たときに最初に現れる偶数が何番目にあるかを出力する問題です。
※ 偶数は必ず存在します。
解答例1
INPUT1 = <<~"EOS"
5
1 3 5 6 8
EOS
OUTPUT1 = <<~"EOS"
4
EOS
def solve1(input_lines)
n, *ary = input_lines.split.map(&:to_i)
1.upto(n) do |i|
return i if ary[i - 1] % 2 == 0
end
end
puts solve(STDIN.read)
# 確認用コード
# puts solve1(INPUT1)
# > 4
数列aryの1番目からn番目までを順番に参照して2で割り切れるかを判定し、割り切れる（偶数）ならその位置を出力します。
解答例2
INPUT1 = <<~"EOS"
5
1 3 5 6 8
EOS
OUTPUT1 = <<~"EOS"
4
EOS
def solve2(input_lines)
n, *ary = input_lines.split.map(&:to_i)
1.upto(n).find { |i| ary[i - 1].even? }
end
puts solve2(STDIN.read)
# 確認用コード
# puts solve2(INPUT1)
# > 4
findメソッド・even?メソッドで数列aryの1番目からn番目までを順番に偶数か？を判定し、偶数ならその位置を出力します。
STEP2: 奇数の探索 (paizaランク D 相当)
要素数n個の数列aで、先頭から順に見たときに最後に現れる奇数が何番目にあるかを出力する問題です。
※ 奇数は必ず存在します。
解答例1
INPUT1 = <<~"EOS"
5
1 3 5 6 8
EOS
OUTPUT1 = <<~"EOS"
3
EOS
def solve1(input_lines)
n, *ary = input_lines.split.map(&:to_i)
n.downto(1) do |i|
return i if ary[i - 1] % 2 != 0
end
end
puts solve1(STDIN.read)
# 確認用コード
# puts solve1(INPUT1)
# > 3
数列aryのn番目から1番目までを順番に参照して2で割り切れるかを判定し、割り切れない（奇数）ならその位置を出力します。
解答例2
INPUT1 = <<~"EOS"
5
1 3 5 6 8
EOS
OUTPUT1 = <<~"EOS"
3
EOS
def solve2(input_lines)
n, *ary = input_lines.split.map(&:to_i)
n.downto(1).find { |i| ary[i - 1].odd? }
end
puts solve2(STDIN.read)
# 確認用コード
# puts solve2(INPUT1)
# > 3
findメソッド・odd?メソッドを使って、数列aryのn番目から1番目までを順番に奇数か？を判定し、奇数ならその位置を出力します。
STEP3: 条件付き最小値 (paizaランク D 相当)
要素数n個の数列aで、整数k以上で最小の値を出力する問題です。
※ k 以上の値は必ず存在します。
解答例1
INPUT1 = <<~"EOS"
5
-5 11 3 -9 0
-4
EOS
OUTPUT1 = <<~"EOS"
0
EOS
def solve1(input_lines)
n, *ary, k = input_lines.split.map(&:to_i)
min_val = Float::INFINITY
ary.each do |val|
min_val = val if k <= val && val < min_val
end
min_val
end
puts solve1(STDIN.read)
# 確認用コード
# puts solve1(INPUT1)
# > 0
数列aryを先頭から順番に参照して、k以下かつ現時点での最小値かを判定してmin_valを更新し、ループ終了後に出力します。
解答例2
INPUT1 = <<~"EOS"
5
-5 11 3 -9 0
-4
EOS
OUTPUT1 = <<~"EOS"
0
EOS
def solve2(input_lines)
n, *ary, k = input_lines.split.map(&:to_i)
ary.select { |val| val >= k }.min
end
puts solve2(STDIN.read)
# 確認用コード
# puts solve2(INPUT1)
# > 0
selectメソッドを使って、数列aryからk以上の値の配列を生成した後、minメソッドで最小値を探して出力します。
STEP4: 条件付き最大値 (paizaランク D 相当)
要素数n個の数列aで、整数以下で最大の値を出力する問題です。
※ k 以下の値は必ず存在します。
解答例1
INPUT1 = <<~"EOS"
5
-5 11 3 -9 0
-4
EOS
OUTPUT1 = <<~"EOS"
-5
EOS
def solve1(input_lines)
n, *ary, k = input_lines.split.map(&:to_i)
max_val = -Float::INFINITY
ary.each do |val|
max_val = val if val <= k && val > max_val
end
max_val
end
puts solve1(STDIN.read)
# 確認用コード
# puts solve1(INPUT1)
# > -5
数列aryを先頭から順番に参照して、k以下かつ現時点での最大値かを判定してmax_valを更新し、ループ終了後に出力します。
解答例2
INPUT1 = <<~"EOS"
5
-5 11 3 -9 0
-4
EOS
OUTPUT1 = <<~"EOS"
-5
EOS
def solve2(input_lines)
n, *ary, k = input_lines.split.map(&:to_i)
ary.select { |val| val <= k }.max
end
puts solve2(STDIN.read)
# 確認用コード
# puts solve2(INPUT1)
# > -5
selectメソッドを使って、数列aryからk以下の値の配列を生成した後、maxメソッドで最大値を探して出力します。
今回のまとめ
セクション3の前半では、数列の中から条件付きの偶数・奇数・最小値・最大値を探し出す方法を実装しました。
配列から特定の要素を抽出したり検索するメソッドが沢山あるので覚えておくと便利ですね！
