お世話になります。問題はこちらです。以下のコードを提出しているのですがいくつかのケースが通らず、自分では原因が特定できません。
ruby
1# メモ化再帰でやる 2N, A, B = gets.chomp.split.map(&:to_i) 3@a_arr, @b_arr, @c_arr = [], [], [] 4N.times do 5 a, b, c = gets.chomp.split.map(&:to_i) 6 @a_arr << a; @b_arr << b; @c_arr << c 7end 8 9@memo = Array.new(N).map{Array.new(40*10+1).map{Array.new(40*10+1, -1)}} 10 11def rec(i, a, b, c) 12 # 見つかった場合は終了 13 if a*b>0 && a*B == A*b 14 return c 15 end 16 # 探索できなかったら終了 17 if i==N 18 return 10**10 19 end 20 # 既に探索済みならそれを返す 21 if @memo[i][a][b] > 0 22 return @memo[i][a][b] 23 end 24 ret = [rec(i+1, a+@a_arr[i], b+@b_arr[i], c+@c_arr[i]), rec(i+1, a, b, c)].min 25 @memo[i][a][b] = ret 26 return ret 27end 28 29ans = rec(0, 0, 0, 0) 30puts ans==10**10 ? -1 : ans
参考になるのかはわかりませんが、上記のものは下記の全探索のコードをそのままメモ化したものです。こちらがWAではなくTLEとなるのを確認したので、単純にこれにメモ化を施したものが上記のコードでした。それだけで通ると思っていたのですが、予想に反してWAとなってしまいました(全探索で通ったとあるケースが、メモ化を施したバージョンでは通りませんでした)。
ruby
1# 全探索する 2N, A, B = gets.chomp.split.map(&:to_i) 3@a_arr, @b_arr, @c_arr = [], [], [] 4N.times do 5 a, b, c = gets.chomp.split.map(&:to_i) 6 @a_arr << a; @b_arr << b; @c_arr << c 7end 8 9def rec(i, a, b, c) 10 # 見つかった場合は終了 11 if a*b>0 && a*B == A*b 12 return c 13 end 14 # 探索できなかったら終了 15 if i==N 16 return 10**10 17 end 18 ret = [rec(i+1, a+@a_arr[i], b+@b_arr[i], c+@c_arr[i]), rec(i+1, a, b, c)].min 19 return ret 20end 21 22ans = rec(0, 0, 0, 0) 23puts ans==10**10 ? -1 : ans
半日ほど考えたのですがやはり浮かびませんでした。お気づきになった点ありましたらよろしくおねがいします。
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2019/02/12 14:00
2019/02/12 14:09