atcoder ABC054 DでWAになる原因
解決済
回答 1
投稿
- 評価
- クリップ 1
- VIEW 716
お世話になります。問題はこちらです。以下のコードを提出しているのですがいくつかのケースが通らず、自分では原因が特定できません。
# メモ化再帰でやる
N, A, B = gets.chomp.split.map(&:to_i)
@a_arr, @b_arr, @c_arr = [], [], []
N.times do
a, b, c = gets.chomp.split.map(&:to_i)
@a_arr << a; @b_arr << b; @c_arr << c
end
@memo = Array.new(N).map{Array.new(40*10+1).map{Array.new(40*10+1, -1)}}
def rec(i, a, b, c)
# 見つかった場合は終了
if a*b>0 && a*B == A*b
return c
end
# 探索できなかったら終了
if i==N
return 10**10
end
# 既に探索済みならそれを返す
if @memo[i][a][b] > 0
return @memo[i][a][b]
end
ret = [rec(i+1, a+@a_arr[i], b+@b_arr[i], c+@c_arr[i]), rec(i+1, a, b, c)].min
@memo[i][a][b] = ret
return ret
end
ans = rec(0, 0, 0, 0)
puts ans==10**10 ? -1 : ans
参考になるのかはわかりませんが、上記のものは下記の全探索のコードをそのままメモ化したものです。こちらがWAではなくTLEとなるのを確認したので、単純にこれにメモ化を施したものが上記のコードでした。それだけで通ると思っていたのですが、予想に反してWAとなってしまいました（全探索で通ったとあるケースが、メモ化を施したバージョンでは通りませんでした）。
# 全探索する
N, A, B = gets.chomp.split.map(&:to_i)
@a_arr, @b_arr, @c_arr = [], [], []
N.times do
a, b, c = gets.chomp.split.map(&:to_i)
@a_arr << a; @b_arr << b; @c_arr << c
end
def rec(i, a, b, c)
# 見つかった場合は終了
if a*b>0 && a*B == A*b
return c
end
# 探索できなかったら終了
if i==N
return 10**10
end
ret = [rec(i+1, a+@a_arr[i], b+@b_arr[i], c+@c_arr[i]), rec(i+1, a, b, c)].min
return ret
end
ans = rec(0, 0, 0, 0)
puts ans==10**10 ? -1 : ans
半日ほど考えたのですがやはり浮かびませんでした。お気づきになった点ありましたらよろしくおねがいします。
-
気になる質問をクリップする
クリップした質問は、後からいつでもマイページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
クリップを取り消します
-
良い質問の評価を上げる
以下のような質問は評価を上げましょう
- 質問内容が明確
- 自分も答えを知りたい
- 質問者以外のユーザにも役立つ
評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。
質問の評価を上げたことを取り消します
-
評価を下げられる数の上限に達しました
評価を下げることができません
- 1日5回まで評価を下げられます
- 1日に1ユーザに対して2回まで評価を下げられます
質問の評価を下げる
teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。
- プログラミングに関係のない質問
- やってほしいことだけを記載した丸投げの質問
- 問題・課題が含まれていない質問
- 意図的に内容が抹消された質問
- 過去に投稿した質問と同じ内容の質問
- 広告と受け取られるような投稿
評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。
質問の評価を下げたことを取り消します
この機能は開放されていません
評価を下げる条件を満たしてません
質問の評価を下げる機能の利用条件
この機能を利用するためには、以下の事項を行う必要があります。
- 質問回答など一定の行動
-
メールアドレスの認証
メールアドレスの認証
-
質問評価に関するヘルプページの閲覧
質問評価に関するヘルプページの閲覧
checkベストアンサー
+1
これで通りました。
# メモ化再帰でやる
N, A, B = gets.chomp.split.map(&:to_i)
@a_arr, @b_arr, @c_arr = [], [], []
N.times do
a, b, c = gets.chomp.split.map(&:to_i)
@a_arr << a; @b_arr << b; @c_arr << c
end
@memo = Array.new(N).map{Array.new(40*10+1).map{Array.new(40*10+1, -1)}}
def rec(i, a, b, c)
# 見つかった場合は終了
if a*b>0 && a*B == A*b
return c
end
# 探索できなかったら終了
if i==N
return 10**10
end
# 既に探索済みならそれを返す
if @memo[i][a][b] > 0
- return @memo[i][a][b]
+ return @memo[i][a][b] == 10**10 ? @memo[i][a][b] : @memo[i][a][b] + c
end
ret = [rec(i+1, a+@a_arr[i], b+@b_arr[i], c+@c_arr[i]), rec(i+1, a, b, c)].min
- @memo[i][a][b] = ret
+ @memo[i][a][b] = ret == 10**10 ? ret : ret - c
return ret
end
ans = rec(0, 0, 0, 0)
puts ans==10**10 ? -1 : ansある (i, a, b) に至る経路によって蓄積した c の値が異なるのに、それをメモしちゃってるのが原因でした。
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
15分調べてもわからないことは、teratailで質問しよう！
- ただいまの回答率 88.09%
- 質問をまとめることで、思考を整理して素早く解決
- テンプレート機能で、簡単に質問をまとめられる
2019/02/12 23:00
> ある (i, a, b) に至る経路によって蓄積した c の値が異なるのに、それをメモしちゃってるのが原因でした。
確かに....指摘されてみるとものすごい初歩的なミスでした。手癖でそのまま再帰をメモ化すればいい（し、適当に大きな数を返しておけば万事良い）と思い込んでいたようです。ご回答ありがとうございます。助かりました。
2019/02/12 23:09