paizaの森練習問題コンテストは、「paizaの森 (Discord)」にて約2か月に1回のペースで開催されており、ユーザー同士が開催時刻にpaizaの森に集まり「よーいドン」で与えられた数問の練習問題をお好きなプログラミング言語で解答する早さを競います。
( 第3回練習問題コンテストは D級3問 C級1問 B級1問 )
それほど難しい問題は出題されないですし、誤答によるペナルティーもありませんので初心者でも気軽に参加出来ます。
また、コンテストから数日後には出題された問題が一般公開され、だれでも挑戦できるようになります。
本記事で使用しているメソッド・アルゴリズムについて
解答例で使っているメソッドやアルゴリズムについて、下記の記事で詳しく解説していますので参考にしてみて下さい。
- [Ruby] 標準入力によるデータ取得1
- [Ruby] 標準入力によるデータ取得2
- [Ruby] 標準入力によるデータ取得3
- [Ruby] 標準出力(データを任意に整形して出力する)
- [Ruby] 文字列の連結・繰り返し・インデックス指定・置き換え
- [Ruby] 文字列を操作するメソッド
- [Ruby]配列の基本操作1
- [Ruby]繰り返し処理
- [Ruby]条件分岐
- [アルゴリズム(Ruby)]線形探索法
- [アルゴリズム(Ruby)]動的計画法
第3回 paizaの森練習問題コンテスト
1問目: 文字列の逆順 (paizaランク D 相当)
文字列sが与えられ、sを逆順にした文字列を出力する問題です。
入出力例
paizaが入力されたら、aziapを出力する。appleが入力されたら、elppaを出力する。
INPUT1 = <<"EOS" paiza EOS OUTPUT1 = <<"EOS" aziap EOS INPUT2 = <<"EOS" apple EOS OUTPUT2 = <<"EOS" elppa EOS
Ruby 解答例1
文字列sを末尾から順に参照して、空文字列で初期化したr_sに追加していきます。
# ruby 解答例1 # 入力 s = gets.chomp # s の文字数 n を取得 n = s.length # 空文字列 r_s を用意 r_s = "" # i を n-1 から 0 まで 1 ずつ減らしながら繰り返す (n - 1).downto(0) do |i| # s[i] を r_s 末尾に追加 r_s <<= s[i] end # 出力 puts r_s
Ruby 解答例2
reverseメソッドを使った書き方。
# ruby 解答例2 puts gets.chomp.reverse
Python3 解答例1
# ptyhon3 解答例1
# 入力
s = input()
# s の文字数 n を取得
n = len(s)
# 空文字列 r_s を用意
r_s = ""
# i を n-1 から 0 まで 1 ずつ減らしながら繰り返す
for i in range(n-1, -1, -1):
# s[i] を r_s 末尾に追加
r_s += s[i]
# 出力
print(r_s)
Python3 解答例2
スライスを使った書き方。
# python3 解答例2 print(input()[::-1])
2問目: 英単語の生成(連結) (paizaランク D 相当)
半角スペースで区切で文字列s1, s2が与えられ、s1とs2を連結した文字列を出力する問題です。
入出力例
play ingが入力されたら、playingを出力する。un balanceが入力されたら、unbalanceを出力する。
INPUT1 = <<"EOS" play ing EOS OUTPUT1 = <<"EOS" playing EOS INPUT2 = <<"EOS" un balance EOS OUTPUT2 = <<"EOS" unbalance EOS
Ruby 解答例1
文字列sを先頭から順に参照して、半角スペース以外なら空文字列で初期化したwに追加していきます。
# ruby 解答例1
# 入力
s = gets.split
# 空文字列 w を用意
w = ""
# s の文字数 n を取得
n = s.length
# i を 0 から n-1 まで 1 ずつ増やしながら繰り返す
0.upto(n - 1) do |i|
# もし、s[i] が 半角スペース以外なら
if s[i] != " "
# s[i] を w 末尾に追加
w <<= s[i]
end
end
# 出力
puts w
Ruby 解答例2
splitメソッドで分割して文字列s1, s2を受け取り、s1+s2を出力します。
# ruby 解答例2 s1, s2 = gets.split puts s1 + s2
Ruby 解答例3
splitメソッドで文字列を分割して配列にして、joinメソッドで連結して出力します。
# ruby 解答例3 puts gets.split.join
Ruby 解答例4
gsubメソッドで半角スペースを空文字列に置換(半角スペースを削除)して出力します。
# ruby 解答例4
puts gets.gsub(" ", "")
Python3 解答例1
# python3 解答例1
# 入力
s = input()
# 空文字列 w を用意
w = ""
# s の文字数 n を取得
n = len(s)
# i を 0 から n-1 まで 1 ずつ増やしながら繰り返す
for i in range(n):
# もし、s[i] が 半角スペース以外なら
if s[i] != " ":
# s[i] を w 末尾に追加
w += s[i]
# 出力
print(w)
Python3 解答例2
# python3 解答例2 s1, s2 = input().split() print(s1 + s2)
Python3 解答例3
#python3 解答例3
print("".join(input().split()))
Python3 解答例4
# python3 解答例4
print(input().replace(" ", ""))
3問目: 小文字にする (paizaランク D 相当)
アルファベット大文字・小文字混合の文字列sが与えられ、全て小文字にした文字列を出力する問題です。
入出力例
pAIzaが与えられたらpaizaを出力する。が与えられたらiNfORMatIoninformationを出力する。
INPUT1 = <<"EOS" pAIza EOS OUTPUT1 = <<"EOS" paiza EOS INPUT2 = <<"EOS" iNfORMatIon EOS OUTPUT2 = <<"EOS" information EOS
Ruby 解答例1
- アルファベット大文字・小文字の対応をハッシュで用意する。
{"A"=>"a", "B"=>"b", ... "Z"=>"z"} - 空文字列
l_cを用意する。 - 文字列
sの先頭から順に大文字かを調べて、大文字なら小文字に変換、小文字ならそのままl_cへ追加する。 l_cを出力する。
# ruby 解答例1-1
# 大文字と小文字の対応のハッシュを用意する
ALPHABET = {
"A" => "a", "B" => "b", "C" => "c", "D" => "d", "E" => "e", "F" => "f",
"G" => "g", "H" => "h", "I" => "i", "J" => "j", "K" => "k", "L" => "l",
"M" => "m", "N" => "n", "O" => "o", "P" => "p", "Q" => "q", "R" => "r",
"S" => "s", "T" => "t", "U" => "u", "V" => "v", "W" => "w", "X" => "x",
"Y" => "y", "Z" => "z",
}
# 入力
s = gets.chomp
# 空文字列 l_s を用意
l_s = ""
# s を 先頭から順に s_i で参照
s.chars.each do |s_i|
# s_i が大文字なら小文字、 s_i が小文字なら nil を l_c に代入
l_c = ALPHABET[s_i]
if l_c
# s_i の小文字を l_s に追加
l_s <<= l_c
else
# s_i を l_s に追加
l_s <<= s_i
end
end
# 出力
puts l_s
ruby解答例1-1と同じ内容を短くまとめた書き方。
# ruby 解答例1-2
# 大文字と小文字の対応のハッシュを用意する
ALPHABET = ("A".."Z").zip("a".."z").to_h
# 入力
s = gets.chomp
# s 先頭から順番に1文字ずつ参照して、
# 大文字なら小文字に変換、小文字ならそのままの配列を生成
# 配列の要素を全て結合して l_s に代入
l_s = s.chars.map { |s_i| ALPHABET[s_i] || s_i }.join
# 出力
puts l_s
Ruby 解答例2
解答例1と同じ方針で、ASCIIコードを利用した書き方。
# 解答例2 # ASCII コード # A: 65, B: 66, C: 67, D: 68, ... W: 87, X: 88, Y: 89, Z: 90 # a: 97, b: 98, c: 99, d: 100, ... w: 119, x: 120, y: 121, z: 122 # 入力 s = gets.chomp # 空文字列 l_s を用意 l_s = "" # s を先頭から順に s_i で参照 s.chars.each do |s_i| # s_i を文字コードに変換 cd = s_i.ord # もし、大文字なら小文字の文字コードに変換 cd += 32 if cd <= 90 # 文字コードを文字に変換して l_s に追加 l_s <<= cd.chr end # 出力 puts l_s
Ruby 解答例3
downcaseメソッドを使った書き方。
# 解答例3 puts gets.downcase
Python3 解答例1
# python3 解答例1
# 大文字と小文字の対応のハッシュを用意する
# ALPHABET = {
# "A": "a", "B": "b", "C": "c", "D": "d", "E": "e", "F": "f",
# "G": "g", "H": "h", "I": "i", "J": "j", "K": "k", "L": "l",
# "M": "m", "N": "n", "O": "o", "P": "p", "Q": "q", "R": "r",
# "S": "s", "T": "t", "U": "u", "V": "v", "W": "w", "X": "x",
# "Y": "y", "Z": "z",
# }
# 文字コードを使って書くと
ALPHABET = {chr(c): chr(c+32) for c in range(65, 91)}
# 入力
s = input()
# 空文字列 l_s を用意
l_s = ""
# s を 先頭から順に s_i で参照
for s_i in s:
# ALPHABET の key に s_i が含まれているか?
if s_i in ALPHABET:
# s_i の小文字を l_s に追加
l_s += ALPHABET[s_i]
else:
# s_i を l_s に追加
l_s += s_i
# 出力
print(l_s)
Python3 解答例2
# python3 解答例2
# 入力
s = input()
# 空文字列 l_s を用意
l_s = ""
# s を先頭から順に s_i で参照
for s_i in s:
# s_i を文字コードに変換
cd = ord(s_i)
# もし、大文字なら小文字の文字コードに変換
if cd <= 90:
cd += 32
# 文字コードを文字に変換して l_s に追加
l_s += chr(cd)
# 出力
print(l_s)
Python3 解答例3
pythonだとlowerメソッドを使います。
# python3 解答例3 print(input().lower())
4問目: キーボードのシミュレーション (paizaランク C 相当)
1行目で整数 n が与えられ、続く n 行の半角スペース区切りで文字列key1, key2が与えられ、下記のルールで生成された文字列を出力する問題です。
- 押されるキーは
a, b, c, d, ... x, y, xとshift, capslockのみ a, b, c, d, ... x, y, xとshiftを同時に押すと対応する大文字が出力される- capslockを押すと、再びcapslockが押されるまで大文字が出力される
入出力例
3
a
shift b
c
が入力されたらaBcが出力される。
7
a
capslock
b
c
d
capslock
f
が入力されたらaBCDfが出力される。
INPUT1 = <<"EOS" 3 a shift b c EOS OUTPUT1 = <<"EOS" aBc EOS INPUT2 = <<"EOS" 7 a capslock b c d capslock f EOS OUTPUT2 = <<"EOS" aBCDf EOS
Ruby 解答例
- 整数 n, 文字列の配列c を受け取る(n は使わない)
- 文字列 display を空文字列で初期化する
- フラグ capslock をfalseで初期化する
- c の先頭から順にkeysでループを回す
- keys を半角スペースで分割してkey1, key2 に代入する
(1文字の場合、key2はnil) - key1 が "capslock" なら capslockフラグを反転させる
- key1 が "shift" なら key2 を大文字に変換して display に追加する
- それ以外(アルファベット)なら
- capslock が true なら大文字を display に追加する
- capslock が false なら小文字を display に追加する
- keys を半角スペースで分割してkey1, key2 に代入する
- display を出力する
Ruby 解答例
# ruby 解答例
# 入力
n = gets.to_i
c = n.times.map { gets.split }
display = ""
capslock = false
# n 行の入力で繰り返し処理
c.each do |keys|
key1, key2 = keys
case key1
when "capslock"
# capslock の ON/OFF 切り替え
capslock = !capslock
when "shift"
# shift と一緒に押されたキーの大文字を display に追加
display <<= key2.upcase
else
# capslock ON なら大文字, OFF なら小文字を display に追加
display <<= capslock ? key1.upcase : key1
end
end
# 出力
puts display
Python3 解答例
# python3 解答例
# 入力
n = int(input())
c = [input() for _ in range(n)]
display = ""
capslock = False
# n 行の入力で繰り返し処理
for row in c:
keys = row.split()
if keys[0] == "capslock":
# capslock の ON/OFF 切り替え
capslock = not capslock
elif keys[0] == "shift":
# shift と一緒に押されたキーの大文字を display に追加
display += keys[1].upper()
else:
# capslock ON なら大文字, OFF なら小文字を display に追加
display += keys[0].upper() if capslock else keys[0]
# 出力
print(display)
5問目: ラッキーナンバー (paizaランク B 相当)
1行目で整数n 、続く n 行の数列aが与えられ、数列aの要素を任意に組み合わせて合計した値が 777 になるかを調べて、下記の出力を行う問題です
- 777 を作れない場合、 "no answer" と出力
- 777 を作れる組み合わせが1つの場合、組み合わせた数値を昇順の半角スペース区切りで出力
- 777 を作れる組み合わせが複数の場合、 "multiple answers" と出力
入出力例
4
333
222
444
666
が入力されたら333 444が出力される。
4
111
222
333
444
入力されたらmultiple answersが出力される。([333, 444], [111, 222, 444])
4
800
125
310
602
入力されたらno answerが出力される。
INPUT1 = <<"EOS" 4 333 222 444 666 EOS OUTPUT1 = <<"EOS" 333 444 EOS INPUT2 = <<"EOS" 4 111 222 333 444 EOS OUTPUT2 = <<"EOS" multiple answers EOS INPUT3 = <<"EOS" 4 800 125 310 602 EOS OUTPUT3 = <<"EOS" no answer EOS
Ruby 解答例1
ビット全探索を使う方法
- 数列 a を受け取る
- 数列 a から777 を超える要素を除外する
- 数列 a の要素数 を n に代入する
- 配列 win_comb を空で初期化する
- i を 1 ~ 2n - 1 まで1 ずつ増やしながら繰り返す
(数列の要素1つ以上を選択する全ての組み合わせ)- i を2進数に変換し、数列aの対応した要素をtmp_combに追加
- tmp_comb の合計が 777 の場合
- win_comb が空なら tmp_comb を win_comb に追加
- win_comb が複数ならループを抜ける
- 出力
- win_comb が空なら "no answer" を出力
- win_comb の要素数が1個なら、その要素(配列)を取り出し昇順ソート・半角スペースで連結して出力
- それ以外(複数) なら "multiple answers" を出力
入力例2のイメージ

# ruby 解答例1
BINGO = 777
# 入力
_, *a = $stdin.read.split.map(&:to_i)
# BINGO 以下の数字だけ調べる
a.select! { |x| x <= BINGO }
n = a.length
# 数字の組み合わせ数 - 1
max_cnt = (1 << n) - 1
win_comb = []
# i を 1 から max_cnt までカウントアップ
1.upto(max_cnt) do |i|
# n 桁の 2 進数に変換
bits = i.to_s(2).rjust(n, "0")
# 数字の組み合わせを作る
tmp_comb = []
0.upto(n - 1) do |j|
tmp_comb << a[j] if bits[j] == "1"
end
# 数字の合計が BINGO のとき
if tmp_comb.sum == BINGO
# win_comb に数字の組み合わせを追加
win_comb << tmp_comb
# BINGO が複数ならループを抜ける
break if win_comb.length > 1
end
end
# 出力
puts case win_comb.length
when 0
# BINGO が作れない場合
"no answer"
when 1
# BINGO の組み合わせが 1 個
win_comb[0].sort.join(" ")
else
# BINGO の組み合わせが 2 個以上
"multiple answers"
end
Ruby 解答例2
combinationメソッドを使って組み合わせを生成する方法
[111, 222, 333, 444].combination(1) で生成される組み合わせ -> [[111], [222], [333], [444]]
[111, 222, 333, 444].combination(2) で生成される組み合わせ -> [[111, 222], [111, 333], [111, 444], [222, 333], [222, 444], [333, 444]]
[111, 222, 333, 444].combination(3) で生成される組み合わせ -> [[111, 222, 333], [111, 222, 444], [111, 333, 444], [222, 333, 444]]
[111, 222, 333, 444].combination(4) で生成される組み合わせ -> [[111, 222, 333, 444]]
# ruby 解答例2
BINGO = 777
# 入力
_, *a = $stdin.read.split.map(&:to_i)
# BINGO 以下の数字だけ調べる
a.select! { |x| x <= BINGO }
n = a.length
win_comb = []
# BINGO が複数あるかのフラグ
is_multiple = false
# 1 ~ n 個の組み合わせを全て調べる
1.upto(n) do |i|
# i 個の組み合わせを作って tmp_comb で繰り返す
a.combination(i) do |tmp_comb|
if tmp_comb.sum == BINGO
# BINGO なら win_comb に tmp_comb を追加
win_comb << tmp_comb
if win_comb.length > 1
# BINGO が複数なら
# is_multiple を true にしてループを抜ける
is_multiple = true
break
end
end
end
# is_multiple が true ならループを抜ける
break if is_multiple
end
# 出力
puts case win_comb.length
when 0
# BINGO が作れない場合
"no answer"
when 1
# BINGO の組み合わせが 1 個
win_comb[0].sort.join(" ")
else
# BINGO の組み合わせが 2 個以上
"multiple answers"
end
Ruby 解答例3
動的計画法を使う方法
- 数列 a を受け取る
- 数列 a から777 を超える要素を除外する
- 配列 dp を要素数 777+1 の空配列で初期化する
- a の要素を先頭から順に num で繰り返す
i を 777 から num まで1ずつ減らしながら繰り返す- dp[i - num] が空ならスキップする
- dp[i -num] の要素を先頭から順に ary で繰り返す
- dp[i] に ary と [num] を連結した配列を追加する
- dp[777] の要素数が複数ならループを抜ける
- dp[num] に [num] を追加する
- 出力
- win_comb が空なら "no answer" を出力
- win_comb の要素数が1個なら、その要素(配列)を取り出し昇順ソート・半角スペースで連結して出力
- それ以外(複数) なら "multiple answers" を出力

# ruby 解答例3
BINGO = 7
# 入力
_, *a = INPUT0.split.map(&:to_i)
# BINGO 以下の数字だけ調べる
a.select! { |x| x <= BINGO }
# dpテーブル初期化
dp = Array.new(BINGO + 1) { [] }
# 数字の組み合わせで作れる数を記録していく
a.each do |num|
p num
BINGO.downto(num) do |i|
next if dp[i - num].empty?
dp[i - num].each do |ary|
dp[i] << ary + [num]
end
end
# BINGO が複数ならループを抜ける
break if dp[BINGO].length > 1
# 単体で作れる数
dp[num] << [num]
end
# 出力
puts case dp[BINGO].length
when 0
# BINGO が作れない場合
"no answer"
when 1
# BINGO の組み合わせが 1 個
dp[BINGO][0].sort.join(" ")
else
# BINGO の組み合わせが 2 個以上
"multiple answers"
end
Python3 解答例1
ビット全探索を使う方法
# python3 解答例1
BINGO = 777
# 入力
_, *a = [int(x) for x in open(0).read().split()]
# BINGO 以下の数字だけ調べる
a = [x for x in a if x <= BINGO]
n = len(a)
# 数字の組み合わせ数
max_cnt = (1 << n)
win_comb = []
# i を 1 から max_cnt - 1 までカウントアップ
for i in range(1, max_cnt):
# n 桁の 2 進数に変換
bits = bin(i)[2:].zfill(n)
# 数字の組み合わせを作る
tmp_comb = []
for j in range(n):
if bits[j] == "0":
continue
tmp_comb.append(a[j])
# 数字の合計が BINGO のとき
if sum(tmp_comb) == BINGO:
# win_comb に数字の組み合わせを追加
win_comb.append(tmp_comb)
# BINGO が複数ならループを抜ける
if len(win_comb) > 1:
break
# 出力
if len(win_comb) == 0:
# BINGO が作れない場合
res = "no answer"
elif len(win_comb) == 1:
# BINGO の組み合わせが 1 個
res = " ".join(map(str, sorted(win_comb[0])))
else:
# BINGO の組み合わせが 2 個以上
res = "multiple answers"
print(res)
Python3 解答例2
itertools.combinationsメソッドを使って組み合わせを生成する方法
import itertools
# python3 解答例2
BINGO = 777
# 入力
_, *a = [int(x) for x in open(0).read().split()]
# BINGO 以下の数字だけ調べる
a = [x for x in a if x <= BINGO]
n = len(a)
win_comb = []
# BINGO が複数あるかのフラグ
is_multiple = False
# 1 ~ n 個の組み合わせを全て調べる
for i in range(1, n+1):
for tmp_comb in itertools.combinations(a, i):
if sum(tmp_comb) == BINGO:
# BINGO なら win_comb に tmp_comb を追加
win_comb.append(tmp_comb)
if len(win_comb) > 1:
# BINGO が複数なら
# is_multiple を true にしてループを抜ける
is_multiple = True
break
# is_multiple が true ならループを抜ける
if is_multiple:
break
# 出力
if len(win_comb) == 0:
# BINGO が作れない場合
res = "no answer"
elif len(win_comb) == 1:
# BINGO の組み合わせが 1 個
res = " ".join(map(str, sorted(win_comb[0])))
else:
# BINGO の組み合わせが 2 個以上
res = "multiple answers"
print(res)
Python3 解答例3
動的計画法を使う方法
# python3 解答例3
BINGO = 777
# 入力
_, *a = [int(x) for x in open(0).read().split()]
# BINGO 以下の数字だけ調べる
a = [x for x in a if x <= BINGO]
n = len(a)
# dpテーブル初期化
dp = [[] for _ in range(BINGO+1)]
# 数字の組み合わせで作れる数を記録していく
for num in a:
for i in range(BINGO, num-1, -1):
if len(dp[i - num]) == 0:
continue
for ary in dp[i - num]:
dp[i].append(ary + [num])
# BINGO が複数ならループを抜ける
if len(dp[BINGO]) > 1:
break
# 単体で作れる数
dp[num].append([num])
# 出力
if len(dp[BINGO]) == 0:
# BINGO が作れない場合
res = "no answer"
elif len(dp[BINGO]) == 1:
# BINGO の組み合わせが 1 個
res = " ".join(map(str, sorted(dp[BINGO][0])))
else:
# BINGO の組み合わせが 2 個以上
res = "multiple answers"
print(res)
今回のまとめ
今回は文字列操作の問題が4問と、組み合わせに関する問題でした。

最終問題はちょっと難しかったですね(*'ω'*)