これは何？
AtCoderという競技プログラミングサイトの練習問題についての私の解答です。
入門者用の練習問題なのでそれほど難しくはないはずなんですが、自力では解けなかったので記録として載せます。
問題はこちら。
https://atcoder.jp/contests/abs/tasks/abc085_c
解答
n, y = gets.chomp.split.map(&:to_i)
not_found = true
# repeated_permutation(3)でも要件は満たすが、組み合わせ爆発でタイムアウトになってしまう
(0..n).to_a.repeated_permutation(2) do |a1, a2|
a3 = n - a1 - a2
next if a3 < 0
next if (a1 + a2 + a3) != n
sum = a1 * 10_000 + a2 * 5_000 + a3 * 1_000
if sum == y then
puts "#{a1} #{a2} #{a3}"
not_found = false
break
end
end
if not_found then
puts '-1 -1 -1'
end
repeated_permutation は重複順列を出力するメソッドで、レシーバの配列の要素から引数の個数の値を取り出す全てのパターンを出力してくれます。
ブロックを渡せば、順列をブロック引数として受け取って任意の処理を書けるのでそうしています。
コードのコメントにあるように当初はrepeated_permutation(3) でやってみていたのですが、これではパターンが多すぎて、入力値のnが大きい場合はタイムアウトになってしまいました。
(0..2000).to_a.repeated_permutation(3).size
# => 8012006001
nが最大値の2000だった場合、なんと80億件以上です。そりゃ遅いはずです。
しかし、後述の参考サイトを見てrepeated_permutation(2) でもできるとわかったので、それで試してみたらうまくいきました。
(0..2000).to_a.repeated_permutation(2).size
# => 4004001
repeated_permutation(2) にしたら約400万件になりました。多いといえば多いですが、これくらいなら現実的な時間で処理可能なようです。性能が劇的に改善され、nが2000の場合でもタイムアウトせずにクリアできました。
正直、自力で思いつけなかったのは悔しいです。精進します。