paiza プログラミング

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

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

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

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

第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を出力する。
  • iNfORMatIonが与えられたらinformationを出力する。
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 に追加する
  • 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" を出力

dpの表

# 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)

 

今回のまとめ

今回は文字列操作の問題が４問と、組み合わせに関する問題でした。

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


【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 カエレバ
楽天市場
Amazon
Yahooショッピング

-paiza, プログラミング

© 2024 じゃいごテック