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

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

ただいまの
回答率

88.09%

atcoder ABC054 DでWAになる原因

解決済

回答 1

投稿

  • 評価
  • クリップ 1
  • VIEW 716

score 13

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

# メモ化再帰でやる
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ページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

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 の値が異なるのに、それをメモしちゃってるのが原因でした。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/02/12 23:00

    ありがとうございます!数日回答がなかったので諦めかけてました。

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

    確かに....指摘されてみるとものすごい初歩的なミスでした。手癖でそのまま再帰をメモ化すればいい(し、適当に大きな数を返しておけば万事良い)と思い込んでいたようです。ご回答ありがとうございます。助かりました。

    キャンセル

  • 2019/02/12 23:09

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

    キャンセル

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

  • ただいまの回答率 88.09%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る