質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Ruby

Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Q&A

解決済

1回答

1329閲覧

atcoder ABC054 DでWAになる原因

or3

総合スコア13

Ruby

Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

0グッド

1クリップ

投稿2019/02/08 13:00

お世話になります。問題はこちらです。以下のコードを提出しているのですがいくつかのケースが通らず、自分では原因が特定できません。

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

半日ほど考えたのですがやはり浮かびませんでした。お気づきになった点ありましたらよろしくおねがいします。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

これで通りました。

diff

1 # メモ化再帰でやる 2 N, A, B = gets.chomp.split.map(&:to_i) 3 @a_arr, @b_arr, @c_arr = [], [], [] 4 N.times do 5 a, b, c = gets.chomp.split.map(&:to_i) 6 @a_arr << a; @b_arr << b; @c_arr << c 7 end 8 9 @memo = Array.new(N).map{Array.new(40*10+1).map{Array.new(40*10+1, -1)}} 10 11 def 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+ return @memo[i][a][b] == 10**10 ? @memo[i][a][b] : @memo[i][a][b] + c 24 end 25 ret = [rec(i+1, a+@a_arr[i], b+@b_arr[i], c+@c_arr[i]), rec(i+1, a, b, c)].min 26- @memo[i][a][b] = ret 27+ @memo[i][a][b] = ret == 10**10 ? ret : ret - c 28 return ret 29 end 30 31 ans = rec(0, 0, 0, 0) 32 puts ans==10**10 ? -1 : ans

ある (i, a, b) に至る経路によって蓄積した c の値が異なるのに、それをメモしちゃってるのが原因でした。

投稿2019/02/12 12:44

set0gut1

総合スコア2413

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

or3

2019/02/12 14:00

ありがとうございます!数日回答がなかったので諦めかけてました。 > ある (i, a, b) に至る経路によって蓄積した c の値が異なるのに、それをメモしちゃってるのが原因でした。 確かに....指摘されてみるとものすごい初歩的なミスでした。手癖でそのまま再帰をメモ化すればいい(し、適当に大きな数を返しておけば万事良い)と思い込んでいたようです。ご回答ありがとうございます。助かりました。
set0gut1

2019/02/12 14:09

僕もしばらく悩みました。アキュムレータとメモ化にこのような相性の悪さがあるとは…。ベストアンサーありがとうございました。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問