こんにちは、paizaランクAのtomosukeです。「paiza x Qiitaコラボ」投稿は2回目です。今回はランクA相当の問題にトライしました。
今回も、考え方を頑張ってかみ砕いて説明してみたいと思います。
コラボ企画へのリンクはこちら
今回のお題は「お菓子の詰め合わせ」
概要（筆者の脳内で変換されています）
↑ paizaからの引用
お菓子を買うためにお小遣いをもらいます。いくつかのお菓子が売っていて、それを次の条件に合わせて買ったときのお釣りを求めてください。
- 同じお菓子を買っちゃダメ。1種類のお菓子は1つだけ買える
- もらったお小遣い内で出来るだけたくさんお菓子を買いたい（種類を買いたい）
- その時に残ったお金を回答する
問題文に「お釣りを最小化したい」とありますが、そのあとに
- それよりもたくさん種類を買いたい
- その上でお釣りを最小化したい
という風に、条件に優先順位が設定されているのがポイントでしょうか。
考え方
その1．入力データをどう扱うか
以下に入力例1の内容を引用します。コメント（ // とその後ろ）は筆者が追記しています。
入力例１． ↓↓↓
3 300 // 条件
150 // 1つ目のお菓子の金額
120 // 2つ目のお菓子の金額
130 // 3つ目のお菓子の金額
1行目は問題の条件に該当する値で、
- 3 は お菓子が何種類あるか
- 300 は 使えるお小遣いの額
と意訳しました。それで、この問題の入力例の記述ルールは、2行目以降に各お菓子の金額が羅列されることになっており、「3種類」あるので以降の3行に数値が並んでいます。
今回はとりあえず、一次元配列にこの3つのお菓子の金額を入れておきましょう。条件として提示された2つの値は、それぞれ別の変数にでもセットしておきましょう。筆者は問題文にしたがって2つの値をそれぞれ N と Ｘ に入れています。
N,X = gets.split(" ").map(&:to_i)
のように。
文法簡易説明
① getsで標準入力から1行（"3 300" という文字列）を取得し
② split(" ")で、取得した文字列を「スペース」で区切って配列に入れる
③ 配列に入った各々の値を int型 に変換する
④ その結果は要素数2の配列型となるので、それを
⑤ N,X = 形式で値を格納する
という書き方すると配列の中身を分けて入れてくれます
その2．どんな作戦で解けばいいのか
全探索で行けるのでは、とすこし考えて思いました。全探索とは
全探索とは、問題の全ての可能な解を順に試して最適解を見つけるアルゴリズム手法です。 by ChatGPT4o
今回の場合だと、以下のように1つずつ条件を調べていくのが全探索になります。
- 1つ目のお菓子だけ買ったら総額がいくらで、お釣りがいくらで、買ったお菓子の数はいくつか
- 2つ目のお菓子だけ買ったら総額がいくらで、お釣りがいくらで、買ったお菓子の数はいくつか
- :
- 1つ目のお菓子と2つ目のお菓子を買ったら総額がいくらで、お釣りがいくらで、買ったお菓子の数はいくつか
- :
- 1つ目のお菓子と2つ目のお菓子と3つ目のお菓子を買ったら総額がいくらで、お釣りがいくらで、買ったお菓子の数はいくつか
のように、1つずつ書き出していきます（頭が慣れたら書き出さなくてもOK）。
ソースコード（ruby）
他の言語の解が必要な方は、OpenAI ChatGPTやGoogle Gemini、Microsoft Copilotなどの生成AIをご利用ください。プロンプトとしては、ソースコードをテキストファイルに保存して生成AIにアップロードした上で
添付ファイルをPython3に書き換えてください
こんな感じで変換できると思います。ただし変換結果が完全に正しいかは保証できかねるのでご了承ください。
# すべての組み合わせを計算させていって、足した種類数を出しておき、sumKindが大きいところから順に、oturiが小さいのを拾う
# calcPattern sumResult sumKind oturi
# 000 0 0 300
# 001 150 1 150
# 010 120 1 180
# 011 270 2 30
# 100 130 1 170
# 101 280 2 20
# 110 250 2 50
# 111 400 3 -100
# 良い関数名が浮かばなかったので hoge で妥協
# ary は Array：配列です
# sumRule は、足すときのルール（Rule）という意味
# 引数名は適当にせず、見たときに役割が想像
def hoge(ary, sumRule)
# sumRuleをbitに分解して配列へ
ruleAry = sumRule.chars.map(&:to_i)
# 足す。足した回数も計算する
sum = 0 # 足し合わせた結果を入れる
sumCnt = 0 # 足した回数を入れる
# 以下の1行はrubyならではの書き方なので、詳しくは生成AIに「教えて」と聞いてみてください
ary.each_with_index do |v, idx|
if ruleAry[idx] == 1 then
sum += v
sumCnt += 1
end
end
return sum,sumCnt
end
# -----
# 1st step : 問題の条件を受け取る
N,X = gets.split(" ").map(&:to_i)
# 2nd step : 入力データを配列に入れる
dataAry = Array.new
N.times do |i|
d = gets.to_i
dataAry.push(d)
end
# 3rd step : 全探索
oturi = 5000 # 問題文の条件より。より小さい値を入れていきたいときは、初期値を大きくしておくのが基本
# 2のN乗の回数分のループ（全探索なので）
# 何故2のN乗かというと、各お菓子を「買う」「買わない」という2パタンあると考えると、1種類のお菓子を買う買わないは 2通り となります
# 2種類のお菓子を買う買わないは、それぞれが買う買わないで2通りあり、それが2種類あるから 2*2 となります
# 3種類のお菓子となると、同様の考え方をすれば 2*3 = 8 通りある、と考えます
# この考え方を、「うんうん」うなって理解出来たとき、プログラマーとしてのLVアップとなる（？）と思います。自身の理解を加速させるために、絵も描いてみましょう
(2**N).times do |i|
next if i==0 # 最初だけは「全部買わない」となるので、skipして次のループへ
# お菓子の種類数分の bit長 のbit文字列を作成
rulePtn = sprintf("%0#{N}b",i)
# 関数 hoge は 2つの値を返す
sum,cnt = hoge(dataAry, rulePtn)
# sum が X 以下ならば、お釣りが出るので計算
if sum <= X then
# puts "cnt=#{cnt}, sum=#{sum}, rulePtn=#{rulePtn}"
oturiTmp = X - sum
oturi = oturiTmp if oturiTmp < oturi
end
end
p oturi
こんなところでしょうか。あまり難しい文法は使ってないので、ソースコードをコピペしてChatGPT-4oに次のような書き方で聞いてみてください。するとChatGPT-4oはいい感じに返してくれます。
わたしはRuby言語をよく知らないけれど、先輩からソースコード渡されて「読め、分からないところは聞け」と言われています。そこで、この下にそのコードを貼り付けるので、各処理ブロックでやっていることをおしえてください。
（ここに、わからないソースコードを貼り付ける）
例えばですけど、
ChatGPT-4o
以下の関数が何をしようとしているか、整理してまとめてください
def hoge(ary, sumRule)
# sumRuleをbitに分解して配列へ
ruleAry = sumRule.chars.map(&:to_i)
# 足す。足した回数も計算する
sum = 0
sumCnt = 0
ary.each_with_index do |v, idx|
if ruleAry[idx] == 1 then
sum += v
sumCnt += 1
end
end
return sum,sumCnt
end
とかね。
この解説記事で、１人でも paiza ランクＡ に近づいてくれると嬉しいです。