paiza プログラミング

[Ruby]paiza 線形探索メニュー 特殊な探索(前半)

線形探索メニュー_特殊な探索 前半

今回はpaiza 線形探索メニュー  セクション3【特殊な探索】前半を解説します。

セクション3【特殊な探索】は、与えられた配列データの中から、複数条件に合致する値を探し出す問題です。
前半の4問は数列から条件付きで偶数・奇数・最大値・最小値を探す問題(D〜C級)となっています。

  • STEP1:要素数n個数列aで先頭から見た時に最初に現れる奇数の位置を出力する
  • STEP2:要素数n個数列aで先頭から見た時に最後に現れる偶数の位置を出力する
  • STEP3:要素数n個数列a整数k以上の最小値を出力する
  • STEP4:要素数n個数列a整数k以下の最小値を出力する

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の前半では、数列の中から条件付きの偶数・奇数・最小値・最大値を探し出す方法を実装しました。

配列から特定の要素を抽出したり検索するメソッドが沢山あるので覚えておくと便利ですね!



アルゴリズム学習でお世話になった本


アルゴリズム関連の技術書は大抵C/C++で書かれていますが、ある程度プログラムが出来れば、処理の流れは理解することが出来ます。






通称: 螺旋本。C++で解説されています。AOJ(Aizu Online Judge)を運営している会津大学の渡辺准教授が書いた本です。データ構造や計算量の内容から丁寧に書いてありますのでアルゴリズム学習の最初の参考書としてオススメです。







通称: 蟻本。C++で解説されています。競技プログラミング中級者の定番書と言われていて、競技プログラミングで利用できる色々なアルゴリズムを学ぶことが出来ます。かなり高度な内容も含まれているので1冊分を完全に理解するのにはかなりの時間がかかりそうですが、手元に置いて何度も読み返しています。







通称: チーター本。C#, C++, JAVAでTopcoderの問題を解説しています。初心者~中級者向けに書かれているので解説が非常に丁寧です。







Python3でアルゴリズムを解説している本です。講義スタイルの本で、図やフローチャートを使ってアルゴリズムとデータ構造についてしっかりと説明されています。代わりにコードは少なめです。Pythonコードが読めなくても十分理解できると思います。


-paiza, プログラミング
-, ,

© 2023 じゃいごテック