今回はpaiza 線形探索メニュー セクション3【特殊な探索】後半を解説します。
セクション3【特殊な探索】は、与えられたデータの中から、複数条件に合致する値を探し出す問題です。
後半の4問はX,Y座標や文字列と数値がセットになったデータを扱う問題(C級)となっています。
- STEP5：n個の点の座標(x, y)が与えられ、点nとそれぞれの点とでマンハッタン距離を求め、整数k以下になる点の個数を出力する
- STEP6：n個の点の座標(x, y)とx軸の下限上限、y軸の下限上限が与えられ、範囲内にある点の個数を出力する
- STEP7：n人の名前とテストの点数、合格基準kが与えられ、k点以上の名前を入力順に出力する
- FINAL：n人の名前とテストの点数、合格基準k, lが与えられ、k点以上、l点以下の名前を入力順に出力する
STEP問題を解いてみる
簡単な解説は付けていますが、難しいと感じたら下記の記事も参考にしてみて下さい。
STEP5: 点と点の距離 (paizaランク C 相当)
n個の点の座標(x, y)と整数kが与えられ、点nと、点nを含めたそれぞれの点とのマンハッタン距離がk以下になる点の個数を出力する問題です。
マンハッタン距離とは、2点間のx方向の差とy方向の差を足した値です。
点a (x_a, y_a) と点b (x_b, y_b) のマンハッタン距離は、| x_a - x_b | + | y_a - y_b | で求めることができます。
解答例1
INPUT1 = <<~"EOS"
5
-9 5
0 4
2 -6
7 -4
-3 -1
10
EOS
OUTPUT1 = <<~"EOS"
3
EOS
def solve1(input_lines)
input_lines = input_lines.split("\n")
n = input_lines.shift.to_i
ary = input_lines.shift(n).map { |l| l.split.map(&:to_i) }
k = input_lines.shift.to_i
ax, ay = ary[n - 1]
result = 0
ary.each do |bx, by|
dist = (ax - bx).abs + (ay - by).abs
result += 1 if dist <= k
end
result
end
puts solve1(STDIN.read)
# 確認用コード
# puts solve1(INPUT1)
# > 3
- 整数n, 座標[x, y]を要素に持つ配列ary, 整数kの入力データを受け取る
- 結果を記録する
result=0を設定する - 基準点(点n)の座標(ax, ay)を設定する
- 2点目の座標(bx, by)を点nを含めて先頭から順に参照する
- マンハッタン距離を求める
dist = |ax - bx| + |ay - by| - distがk以下ならresultに +1する
- マンハッタン距離を求める
解答例2
INPUT1 = <<~"EOS"
5
-9 5
0 4
2 -6
7 -4
-3 -1
10
EOS
OUTPUT1 = <<~"EOS"
3
EOS
def solve2(input_lines)
input_lines = input_lines.split("\n")
n = input_lines.shift.to_i
ary = input_lines.shift(n).map { |l| l.split.map(&:to_i) }
k = input_lines.shift.to_i
ax, ay = ary[n - 1]
ary.count { |bx, by| (ax - bx).abs + (ay - by).abs <= k }
end
puts solve2(STDIN.read)
# 確認用コード
# puts solve2(INPUT1)
# > 3
countメソッドで、点nと点nを含めたそれぞれの点とのマンハッタン距離がk以下かを判定し、k以下の座標の個数を出力します。
STEP6: 長方形に含まれる点 (paizaランク C 相当)
n個の点の座標(x, y)とx軸の下限xs上限xt、y軸の下限ys上限ytが与えられ、範囲内にある点の個数を出力する問題です。
※ 境界線上の点も範囲内に含む。
解答例1
INPUT1 = <<~"EOS"
5
-9 5
0 4
2 -6
7 -4
-3 -1
-5 5
-5 5
EOS
OUTPUT1 = <<~"EOS"
2
EOS
def solve1(input_lines)
input_lines = input_lines.split("\n")
n = input_lines.shift.to_i
ary = input_lines.shift(n).map { |l| l.split.map(&:to_i) }
xs, xt = input_lines.shift.split.map(&:to_i)
ys, yt = input_lines.shift.split.map(&:to_i)
result = 0
ary.each do |x, y|
if xs <= x && x <= xt &&
ys <= y && y <= yt
result += 1
end
end
result
end
puts solve(STDIN.read)
# 確認用コード
# puts solve(INPUT1)
# > 2
- 整数n, 座標[x, y]を要素に持つ配列ary, 整数xs, xt、整数ys, ytの入力データを受け取る
- 結果を記録する
result=0を設定する - 座標(x, y)をaryの先頭から順に参照する
- 「xがxs以上xt以下」かつ「yがys以上yt以下」resultに +1する
解答例2
INPUT1 = <<~"EOS"
5
-9 5
0 4
2 -6
7 -4
-3 -1
-5 5
-5 5
EOS
OUTPUT1 = <<~"EOS"
2
EOS
def solve2(input_lines)
input_lines = input_lines.split("\n")
n = input_lines.shift.to_i
ary = input_lines.shift(n).map { |l| l.split.map(&:to_i) }
xs, xt = input_lines.shift.split.map(&:to_i)
ys, yt = input_lines.shift.split.map(&:to_i)
ary.count do |x, y|
xs <= x && x <= xt &&
ys <= y && y <= yt
end
end
puts solve2(STDIN.read)
# 確認用コード
# puts solve2(INPUT1)
# > 2
countメソッドで、「xがxs以上xt以下」かつ「yがys以上yt以下」かを判定し、該当する座標の個数を出力します。
STEP7: 成績優秀者の列挙 1 (paizaランク C 相当)
n人の名前とテストの点数、合格基準kが与えられ、k点以上の名前を入力順に出力する問題です。
解答例1
INPUT1 = <<~"EOS"
5
alice 97
bob 25
carol 57
dave 46
ellen 10
35
EOS
OUTPUT1 = <<~"EOS"
alice
carol
dave
EOS
def solve1(input_lines)
input_lines = input_lines.split("\n")
n = input_lines.shift.to_i
ary = input_lines.shift(n).map do |l|
name, score = l.split
[name, score.to_i]
end
k = input_lines.shift.to_i
result = []
ary.each do |name, score|
result << name if k <= score
end
result
end
puts solve1(STDIN.read)
# 確認用コード
# puts solve1(INPUT1)
# > alice
# > carol
# > dave
- 整数n, [文字列name, 整数score]を要素に持つ配列ary, 整数kの入力データを受け取る
- 結果を記録する
result=[]を設定する - 名前nameと点数scoreをaryの先頭から順に参照する
- 「scoreがk以上」ならresultの末尾にnameを追加する
解答例2
INPUT1 = <<~"EOS"
5
alice 97
bob 25
carol 57
dave 46
ellen 10
35
EOS
OUTPUT1 = <<~"EOS"
alice
carol
dave
EOS
def solve2(input_lines)
input_lines = input_lines.split("\n")
n = input_lines.shift.to_i
hash = input_lines.shift(n).map do |l|
name, score = l.split
[name, score.to_i]
end
hash = hash.to_h
k = input_lines.shift.to_i
hash.select { |name, score| k <= score }.keys
end
puts solve2(STDIN.read)
# 確認用コード
# puts solve2(INPUT1)
# > alice
# > carol
# > dave
- 整数n, 「文字列nameをキー, 整数scoreを値」にもつハッシュhash, 整数kの入力データを受け取る
- selectメソッドで、「scoreがk以上のname」を要素に持つ配列を生成する
成績優秀者の列挙 2 (paizaランク C 相当)を解いてみる
※ paiza 線形探索メニューより
問題
n 人の生徒がテストを受けました。このテストで k 点以上 l 点以下の点数を取った人が合格です。
n 人の各生徒について、その人の名前とその人が取った点数が入力として与えられるので、このテストに合格した人の名前をすべて、入力された順に改行区切りで出力してください。
なお、合格者が一人もいない場合は、何も出力しないでください。
入力される値
入力は以下のフォーマットで与えられます。
n
s_1 t_1
s_2 t_2
...
s_n t_n
k l
- 1行目に、生徒の人数を表す整数 n が与えられます。
- 続く n 行のうち i 行目に、i 番目の生徒の名前 s_i とその生徒の得点 t_i が半角スペース区切りで与えられます。
- n+2 行目に、合格点の基準を表す整数 k, l が半角スペース区切りで与えられます。
入力値最終行の末尾に改行が１つ入ります。
期待する出力
テストに合格した人の名前をすべて、入力された順に改行区切りで出力してください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
なお、合格者が一人もいない場合は、何も出力しないでください。
条件
すべてのテストケースにおいて、以下の条件をみたします。
- 入力は s_i を除いて全て整数
- 1 ≦ n ≦ 100
- s_i は英小文字 'a', 'b', ... , 'z' からなる1文字以上10文字以下の文字列
- i ≠ j ならば s_i ≠ s_j
- 0 ≦ t_i ≦ 100
- 1 ≦ k, l ≦ 100
- k ≦ l
- 入力例1
- 5
alice 97
bob 25
carol 57
dave 46
ellen 10
35 80
- 出力例1
- carol
dave
攻略ポイント
ポイント
- 名前と点数をセットで保持する
（名前の重複がないことが分かっているのでハッシュでもOK） - 点数で合格判定を行い合格なら名前を記録する
デバッグを楽にするためにメソッドを作成します。メソッドについては下記の記事も参考にしてみて下さい。
問題を解く流れ
入出力例をコピペしてヒアドキュメントで変数に代入し、データを確認します。正しく受け取れていれば確認用コードは削除します。
INPUT1 = <<~"EOS" 5 alice 97 bob 25 carol 57 dave 46 ellen 10 35 80 EOS OUTPUT1 = <<~"EOS" carol dave EOS # 確認用コード p INPUT1 # > "5\nalice 97\nbob 25\ncarol 57\ndave 46\nellen 10\n35 80\n" p OUTPUT1 # > "carol\ndave\n"
続いて問題を解くメソッド（ solve メソッドとします）を変数の下に定義します。
まず、入力データを受け取る処理を書きます。
※ 表示されるデータが多いときはppメソッドを使うといい感じに整えて表示してくれます。
def solve(input_lines)
input_lines = input_lines.split("\n")
n = input_lines.shift.to_i
ary = input_lines.shift(n).map do |l|
name, score = l.split
[name, score.to_i]
end
k, l = input_lines.shift.split.map(&:to_i)
# 確認用コード
[n, ary, k, l]
end
# 確認用コード
pp solve(INPUT1)
# > [5,
# > [["alice", 97], ["bob", 25], ["carol", 57], ["dave", 46], ["ellen", 10]],
# > 35,
# > 80]
データが正しく受け取れていれば、solve メソッドに合格判定と合格者の名前を記録する処理を追加していきます。
result=[]で合格者リストを初期化する- 配列aryの1番目の要素をname、2番目の要素をscoreとして先頭から順に参照する
- もし「scoreがk以上かつl以下」ならresultの末尾にnameを追加する
def solve(input_lines)
input_lines = input_lines.split("\n")
n = input_lines.shift.to_i
ary = input_lines.shift(n).map do |l|
name, score = l.split
[name, score.to_i]
end
k, l = input_lines.shift.split.map(&:to_i)
result = []
ary.each do |name, score|
result << name if k <= score && score <= l
end
# 確認用コード
result
end
# 確認用コード
p solve(INPUT1)
# > ["carol", "dave"]
p solve(INPUT1) == OUTPUT1
# > false
あとは出力形式を整えれば完成です。
p solve(INPUT1) == OUTPUT1 -> true を確認するために、配列resultを改行で連結した文字列に変換して末尾に改行を加えます。
def solve(input_lines)
input_lines = input_lines.split("\n")
n = input_lines.shift.to_i
ary = input_lines.shift(n).map do |l|
name, score = l.split
[name, score.to_i]
end
k, l = input_lines.shift.split.map(&:to_i)
result = []
ary.each do |name, score|
result << name if k <= score && score <= l
end
# 改行で連結して末尾に改行を追加する
result.join("\n") << "\n"
end
# 確認用コード
p solve(INPUT1)
# > "carol\ndave\n"
p solve(INPUT1) == OUTPUT1
# > true
確認用コードを標準入力からのデータ受け取りに変更、標準出力をpメソッドからputsメソッドに変更して、動作確認をしたら提出します。
複数行のデータ受け取りなので STDIN.read を使います。（入力終了は Ctrl+D 又は Ctrl+Z)
解答コード
def solve(input_lines)
input_lines = input_lines.split("\n")
n = input_lines.shift.to_i
ary = input_lines.shift(n).map do |l|
name, score = l.split
[name, score.to_i]
end
k, l = input_lines.shift.split.map(&:to_i)
result = []
ary.each do |name, score|
result << name if k <= score && score <= l
end
# 改行で連結して末尾に改行を追加する
result.join("\n") << "\n"
end
puts solve(STDIN.read)
他の解答例
「名前をキー、点数を値」のハッシュでデータを受け取り、selectメソッドで合格者を絞り込んだ後にkeysメソッドで名前の配列を生成します。
def solve(input_lines)
input_lines = input_lines.split("\n")
n = input_lines.shift.to_i
hash = input_lines.shift(n).map do |l|
name, score = l.split
[name, score.to_i]
end
hash = hash.to_h
k, l = input_lines.shift.split.map(&:to_i)
hash.select { |name, score| k <= score && score <= l }.keys
end
puts solve(STDIN.read)
今回のまとめ
セクション3の後半では、線形探索法を使ってpaizaC級相当の問題を解いてみました。
座標を扱う問題は図を描いてみると理解しやすくなりますね！
