私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「ホワイトデーのお返しの個数」（CodeIQ）を参照してください。
この問題の挑戦終了日はホワイトデー。
ということで、バレンタインデーにもらったプレゼントにお返しを送ろうと思っています。
もらったプレゼントの金額はわからないので、もらった個数に対してお返しの個数を変えることにします。
・義務チョコの場合はもらった個数と同じ数
・義理チョコの場合はもらった個数の２倍の数
・本命チョコの場合はもらった個数の３倍の数
※もらった時点で「義務チョコ」か「義理チョコ」か「本命チョコ」かはわかるものとします。
バレンタインには合計 m 個のプレゼントをもらいました。
お返しに用意した個数が n 個のとき、もらったプレゼントの種類について、義務チョコ・義理チョコ・本命チョコの個数の組み合わせを考えます。
例えば、m = 5, n = 10 のとき、以下の3パターンがあります。
パターン 義務チョコ 義理チョコ 本命チョコ (1) 0個 5個 0個 (2) 1個 3個 1個 (3) 2個 1個 2個
標準入力から m, n が与えられるとき、上記の組み合わせの数を標準出力に出力してください。
(m, n は m < n を満たす整数とし、n は最大で1,000,000とします)
【入出力サンプル】
標準入力
5 10
標準出力
3
Rubyで解答しています。
#!/usr/bin/ruby
def solve(m, n)
cnt = 0
for i in 0..(n/3)
rm = m - i
rn = n - 3 * i
cnt += 1 if (rn >= rm) && (2*rm >= rn)
end
return cnt
end
# main
while line = gets
line.strip!
if line.empty? then next end
m,n = line.split.map{|a| a.to_i}
p solve(m,n)
end
コードは簡単ですが高校レベルの数学が要求されます。
| 本命チョコの人数 | 残り人数 | お返し残り | 義理、義務の人数 |
|---|---|---|---|
| 0 | 5 | 10 | 義理5、義務0 |
| 1 | 4 | 7 | 義理3、義務1 |
| 2 | 3 | 4 | 義理1、義務2 |
| 3 | 2 | 1 | NG |
入力値を数値にしてsolve()に渡し、結果を印字します。
考え方の通りのロジックを実装しています。
6〜11行目のループのiは本命の人数候補です。
rmが残り人数、rnが残りお返し数なので(rn >= rm) かつ (2*rm >= rn)であればOKとしてカウントします。
最後までやったらカウントを返却します。
お返しの数が1,000,000はスゴイなぁ。
それはどうでも良いとして、私は最初義理チョコのパターンまで列挙するコードを書き、ローカルでm=500,000、n=1,000,000をやって見たら時間的に全然ダメでm=5,000、n=10,000でもダメだったので「あー、これはループを1回にしないどダメだ」ということになり、途中状態の出力を眺めていたら「本命のパターン1つに対して義理と義務のパターンは最大1パターンしかないんじゃないか」ということに気づいたのがブレークスルーでした。