[Ruby|Python]paiza paizaの森練習問題コンテスト過去問題6

2023-08-31

paizaの森練習問題コンテストは、「paizaの森 (Discord)」にて約2か月に1回のペースで開催されており、ユーザー同士が開催時刻にpaizaの森に集まり「よーいドン」で与えられた数問の練習問題をお好きなプログラミング言語で解答する早さを競います。
（第6回練習問題コンテストは D級3問, C級3問）
それほど難しい問題は出題されないですし、誤答によるペナルティーもありませんので初心者でも気軽に参加出来ます。
また、コンテストから数日後には出題された問題が一般公開され、だれでも挑戦できるようになります。

本記事で使用しているメソッド・アルゴリズムについて
第5回 paizaの森練習問題コンテスト
今回のまとめ

本記事で使用しているメソッド・アルゴリズムについて

解答例で使っているメソッドやアルゴリズムについて、下記の記事で詳しく解説していますので参考にしてみて下さい。

第5回 paizaの森練習問題コンテスト

1問目: 球数制限 (paizaランク D 相当)

1行目でイニング数 n と投球制限数 k が半角スペース区切り、続く n 行で各イニングの投球数 m_i が与えれられ、投球の合計が k 未満なら "Yes" そうでなければ "No" を出力する問題です。

入出力例

5 100 12 14 20 8 17が入力されたら、Yesを出力する。
(投球数 71 なのでまだ投げられる)

INPUT1 = <<"EOS"
5 100
12
14
20
8
17
EOS
OUTPUT1 = <<"EOS"
Yes
EOS

Ruby 解答例1-1

各イニングの投球数を配列 a で受け取り、sumメソッドで合計した値が k 未満か？を判定します。

# 解答例1-1
n, k = gets.split.map(&:to_i)
a = n.times.map { gets.to_i }

# 投球数の合計は k 球未満?
if a.sum < k
  puts "Yes"
else
  puts "No"
end

Ruby 解答例1-2

解答例1-1を短くまとめた書き方です。

# 解答例1-2
_, k, *a = $stdin.read.split.map(&:to_i)

puts a.sum < k ? "Yes" : "No"

Python3 解答例1-1

# 解答例1-1
n, k = map(int, input().split())
a = [int(input()) for _ in range(n)]

# 投球数の合計は k 球未満?
if sum(a) < k:
    print("Yes")
else:
    print("No")

Python3 解答例1-2

# 解答例1-2
n, k, *a = map(int, open(0).read().strip().split())

print("Yes" if sum(a) < k else "No")

2問目: 最大イニング (paizaランク D 相当)

1行目で投球制限数 k 、続く9行で各イニングの投球数が与えられ、
投球制限数を超える場合はそのイニング数、投球数が投球制数限丁度の場合には次のイニング数、完投できる場合は "Yes" を出力する問題です。

入出力例

99 6 16 14 22 8 11 7 10 4が入力されたら、Yesを出力する。(94球で投げ切れるので)

INPUT1 = <<"EOS"
99
6
16
14
22
8
11
7
10
4
EOS
OUTPUT1 = <<"EOS"
Yes
EOS

INPUT2 = <<"EOS"
70
6
16
14
22
8
11
7
10
4
EOS
OUTPUT2 = <<"EOS"
6
EOS

INPUT3 = <<"EOS"
77
6
16
14
22
8
11
7
10
4
EOS
OUTPUT3 = <<"EOS"
7
EOS

Ruby 解答例1-1

交代イニングを格納する変数 leaving_inning を nil で初期化する
トータル投球数を格納する変数 num_of_pitches を 0 で初期化する
i = 0 ～ 8 のループを設定する（1 から 9 のイニング）
- num_of_piches に現在イニングの投球数を加える
- 投球制限 k を超えたかを判定
  - 超えたらそのイニングを leaving_inning に記録してループを抜ける
leaving_inning が nil かを判定（完投か？）
- leaving_inning に値が入っていたらその値を出力
- leaving_inning に値が入っていなかったら "Yes" を出力

# 解答例1-1
n = 9
k = gets.to_i
a = n.times.map { gets.to_i }

leaving_inning = nil  # 交代イニング
num_of_pitches = 0    # 現在の投球数
0.upto(n - 1) do |i|
  num_of_pitches += a[i]

  # k 球を超えた?
  if num_of_pitches > k
    leaving_inning = i + 1
    break
  end
end

if leaving_inning.nil?
  puts "Yes"
else
  puts leaving_inning
end

Ruby 解答例1-2

解答例1-1を短くまとめた書き方。

# 解答例1-2
k, *a = $stdin.read.split.map(&:to_i)

leaving_inning = nil  # 交代イニング
num_of_pitches = 0    # 現在の投球数
a.each.with_index(1) do |v, i|
  num_of_pitches += v

  # k 球を超えた?
  if num_of_pitches > k
    leaving_inning = i
    break
  end
end

puts leaving_inning || "Yes"

Python3 解答例1-1

# 解答例1-1
n = 9
k = int(input())
a = [int(input()) for _ in range(n)]

leaving_inning = None   # 交代イニング
num_of_pitches = 0      # 現在の投球数
for i in range(n):
    num_of_pitches += a[i]

    # k 球を超えた?
    if num_of_pitches > k:
        leaving_inning = i + 1
        break

if leaving_inning is None:
    print("Yes")
else:
    print(leaving_inning)

Python3 解答例1-2

# 解答例1-2
k, *a = map(int, open(0).read().strip().split())

leaving_inning = None   # 交代イニング
num_of_pitches = 0      # 現在の投球数
for (i, v) in enumerate(a, 1):
    num_of_pitches += v

    # k 球を超えた?
    if num_of_pitches > k:
        leaving_inning = i
        break

print(leaving_inning or "Yes")

3問目: ロボットの移動 (paizaランク D 相当)

整数の座標 x, y が半角スペースで与えられ、現在の座標が (0, 0) で上下左右に1 ずつ移動できるとした場合、何ステップで座標 (x, y) に到達できるかを出力する問題です。

img6-3

入出力例

5 3が与えられたら8を出力する。

INPUT1 = <<~"EOS"
  5 3
EOS
OUTPUT1 = <<~"EOS"
  8
EOS

Ruby 解答例1-1

マンハッタン距離を求めます。

# 解答例1-1
sx = 0  # スタート座標 x
sy = 0  # スタート座標 y
x, y = gets.split.map(&:to_i)

# マンハッタン距離
puts (x - sx).abs + (y - sy).abs

Ruby 解答例1-2

現在座標が (0, 0) なので、目標座標 (x, y) それぞれの絶対値を足し合わせます。

# 解答例1-2
x, y = gets.split.map(&:to_i)

# (0, 0) からのマンハッタン距離
puts x.abs + y.abs

Python3 解答例1-1

# 解答例1-1
sx = 0  # スタート座標 x
sy = 0  # スタート座標 y
x, y = map(int, input().split())

# マンハッタン距離
print(abs(x - sx) + abs(y - sy))

Python3 解答例1-2

# 解答例1-2
x, y = map(int, input().split())

# (0, 0) からのマンハッタン距離
print(abs(x) + abs(y))

4問目: 最大の差 (paizaランク C 相当)

5行で、5教科のテストの点数 m_i が与えられ、最大の点数と最低の点数の差を出力する問題です。

入出力例

35 48 51 67 72が入力されたら37を出力する。（72 - 35 = 37）

INPUT1 = <<"EOS"
35
48
51
67
72
EOS
OUTPUT1 = <<"EOS"
37
EOS

Ruby 解答例1-1

線形探索法で最大値と最小値を求めます。

# 解答例1-1
n = 5
a = n.times.map { gets.to_i }

# 0 ≦ m_i ≦ 100
max_sc = -1
min_sc = 101
a.each do |sc|
  max_sc = [max_sc, sc].max
  min_sc = [min_sc, sc].min
end

puts max_sc - min_sc

Ruby 解答例1-2

minmaxメソッドを使って最小値と最大値を求めます。

# 解答例1-2
a = $stdin.read.split.map(&:to_i)

min_sc, max_sc = a.minmax

puts max_sc - min_sc

Python3 解答例1-1

# 解答例1-1
n = 5
a = [int(input()) for _ in range(n)]

# 0 ≦ m_i ≦ 100
max_sc = -1
min_sc = 101
for sc in a:
    max_sc = max([max_sc, sc])
    min_sc = min([min_sc, sc])

print(max_sc - min_sc)

Python3 解答例1-2

# 解答例1-2
a = list(map(int, open(0).read().strip().split()))

max_sc = max(a)
min_sc = min(a)

print(max_sc - min_sc)

5問目: 中央値 (paizaランク C 相当)

5行で5テストの点数 m_i が与えられ、その中央値を出力する問題です。

入出力例

92 35 61 81 65

が入力されたら65を出力する。
[35, 61, 65, 81, 95]

INPUT1 = <<"EOS"
92
35
61
81
65
EOS
EOS1 = <<"EOS"
65
EOS

Ruby 解答例1-1

テストの点数を配列に格納し、昇順ソートして3番目の点数を出力します。
（テストの点数は5科目固定）

# 解答例1-1
n = 5
a = n.times.map { gets.to_i }

# 昇順ソート
a.sort!

# n = 5 固定なので
puts a[n / 2]

Ruby 解答例1-2

蛇足ですが、テスト科目数n 不明の場合にも対応した書き方。(科目数が偶数なら小数の答えが出る)

# 解答例1-2
a = $stdin.read.split.map(&:to_i)

# 昇順ソート
a.sort!
l = a.length

puts l.odd? ? a[l / 2] : (a[l / 2 - 1] + a[l / 2]) / 2.0

Python3 解答例1-1

# 解答例1-1
n = 5
a = [int(input()) for _ in range(n)]

# 昇順ソート
a.sort()

# n = 5 固定なので
print(a[n // 2])

Python3 解答例1-2

# 解答例1-2
a = list(map(int, open(0).read().strip().split()))

# 昇順ソート
a.sort()
l = len(a)

print(a[l // 2] if l % 2 == 1 else (a[l // 2 - 1] + a[l // 2]) / 2)

6問目: 採点 (paizaランク C 相当)

1行目で、試験の回答数 n 、続く n 行で試験の回答の文字列が与えられ、以下のルールで点数が計算されるときの点数の合計を出力する問題です。

点数のルール

correct （正解）の場合、 2 点
incorrect （不正解）の場合、 -1 点
no_answer （無回答）の場合、0 点

入出力例

4 correct correct incorrect no_answerが入力されたら3を出力する。(2 + 2 + (-1) + 0)

INPUT1 = <<"EOS"
4
correct
correct
incorrect
no_answer
EOS
OUTPUT1 = <<"EOS"
3
EOS

Ruby 解答例1

合計点数を0で初期化して試験結果を順番に参照し、 "correct" なら合計点数 +2 、"incrrect" なら合計点数 -1 を計算し、出力します。

# 解答例1
n = gets.to_i
a = n.times.map { gets.to_i }

score = 0
a.each do |res|
  case res
  when "correct"
    score += 2
  when "incorrect"
    score -= 1
  end
end

puts score

Ruby 解答例2

ハッシュで得点表を設定しておき、試験の回答に対応した点数を取得します。

# 解答例2
SCORE_LIST = {
  "correct" => 2,
  "no_answer" => 0,
  "incorrect" => -1,
}
_, *a = $stdin.read.split

puts a.map { |k| SCORE_LIST[k] }.sum

Python3 解答例1

# 解答例1
n = int(input())
a = [input() for _ in range(n)]

score = 0
for res in a:
    if res == "correct":
        score += 2
    elif res == "incorrect":
        score -= 1

print(score)

Python3 解答例2

# 解答例2
SCORE_LIST = {
    "correct": 2,
    "no_answer": 0,
    "incorrect": -1,
}
_, *a = open(0).read().strip().split()

print(sum(map(lambda k: SCORE_LIST[k], a)))

今回のまとめ

繰り返し、配列（ソート）、条件分岐、四則演算が出来れば問題なく解けると思います！
何気に2問目（Dランク）が難しかったかも？

今回はCランク3問ありましたが、易しめの問題でしたね(*'ω'*)

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

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

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

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 [ 渡部有隆 ]

posted with カエレバ

楽天市場

Amazon

Yahooショッピング

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

プログラミングコンテストチャレンジブック第2版問題解決のアルゴリズム活用力とコーディングテクニッ [ 秋葉拓哉 ]

posted with カエレバ

楽天市場

Amazon

Yahooショッピング

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

最強最速アルゴリズマー養成講座プログラミングコンテストTopCoder攻略ガイド【電子書籍】[ 高橋直大 ]

posted with カエレバ

楽天市場

Amazon

Yahooショッピング

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

Pythonで体験してわかるアルゴリズムとデータ構造 [ 西澤弘毅 ]

posted with カエレバ

comment

: paiza プログラミング

[Ruby|Python]paiza paizaの森練習問題コンテスト過去問題1

paizaの森練習問題コンテストは、「paizaの森 (Discord)」にて約2か月に1回のペースで開催されており、ユーザー同士が開催時刻にpaizaの森に集まり「よーいドン」で与えられた数問（第1 ...

: paiza プログラミング

[Ruby]paiza Bランクレベルアップメニュー占い (paizaランク C 相当)の解説

こんにちは！じゃいごテックのあつしです。今回はpaiza Bランクレベルアップメニューから占いという問題を解説します。この問題集はハッシュ（連想配列）に関する5個のSTEP問題(D～C級)とFI ...

: paiza プログラミング

[Ruby]paiza リアルイベント問題セット本の整理 (paizaランク A 相当)

今回はpaiza リアルイベント問題セット「本の整理」 (paizaランク A 相当)を解説します。順番がバラバラになっている本を指示されたルールに従って並び替えた時の入れ替え回数を答える問題です ...

: paiza プログラミング

[Ruby|Python]paiza 標準出力メニュー【特定の文字で区切り 1 行で出力】

今回はpaiza 標準入力メニューセクション5【特定の文字で区切り 1 行で出力】を解説します。セクション5は、任意の文字列で区切って1から入力された整数n までを改行区切りで出力する問題です。目 ...

: paiza プログラミング

[Ruby]paiza DPメニュー部分和

こんにちは！じゃいごテックのあつしです。今回はpaiza DPメニュー「セクション5【部分列】 STEP1, FINAL」を解説します。 DPメニューは動的計画法(Dynamic Program ...

PREV: [Ruby|Python]paiza paizaの森練習問題コンテスト過去問題5
NEXT: [Ruby|Python]paiza 累積和メニュー1 【区間の和】